Pavel Klavík, A. Cristiano I. Malossi, et al.
Philos. Trans. R. Soc. A
The model of an online multitape Turing machine is generalized by adding a bounded number of repositioning operations to the shift repertoire. It is proved that any such limited random access Turing machine can be effectively replaced by an equivalent conventional Turing machine which operates in the same time. This result yields simplified proofs and extensions of several results in the literature.
Pavel Klavík, A. Cristiano I. Malossi, et al.
Philos. Trans. R. Soc. A
Erik Altman, Jovan Blanusa, et al.
NeurIPS 2023
Conrad Albrecht, Jannik Schneider, et al.
CVPR 2025
Miao Guo, Yong Tao Pei, et al.
WCITS 2011