Theoretical computer science
Research Article
Complexity of Computations with Time Travel
Milad Joudakizadeh1, Anatoly Petrovich Beltiukov2
| 1,2 | Udmurt State University, Izhevsk, Russia. |
| 2 |
belt.udsu@mail.ru |
Abstract. This paper explores a mathematical model of computation that can be interpreted as a computer capable of receiving data from future states of its own computational process. Under certain combinations of input data and programs, such computations may become infeasible due to emerging contradictions or lead to ambiguous outcomes. We investigate programs for which this process is always feasible and yields a unique result.
It is demonstrated that, in the absence of computational complexity constraints, such machines can output the value of any recursively decidable predicate within a fixed time after the computation begins—referred to as the response delay time—while the computation process must continue even after the result is produced. When the total runtime of these machines is bounded by a polynomial function of the input size, they precisely recognize languages belonging to the intersection of the NP and co-NP complexity classes, with the same constant response delay time in the aforementioned sense.
Possible practical implementations of such a computer are examined, including an analysis of operational protocols leveraging quantum annealing to select the appropriate computational process. It is shown that, with parallelization of the computational process, the class of problems solvable by these machines in polynomial time corresponds to the PSPACE complexity class.
Additionally, a mode of operation is studied in which these machines have direct access to input data. In this case, if the runtime is limited to a logarithmic function of the input size, the class of problems solvable by such a parallelized computer encompasses LOGSPACE
The findings of this study can be applied to develop new programming principles for nondeterministic computational machines, where data transmission from the future is employed instead of nondeterministic choices. (Linked article texts in English and in Russian).
Keywords: Turing Machine, Computational Complexity, Recursive Sets, Nondeterministic Computation, Quantum Annealing, Time Machine, Artificial Intelligence
MSC-2020
68Q09; 68Q10, 68Q15
For citation: Milad Joudakizadeh, Anatoly P. Beltiukov. Complexity of Computations with Time Travel. Program Systems: Theory and Applications, 2025, 16:2, pp. 3–54. (in Engl. In Russ.). https://psta.psiras.ru/2025/2_3-54.
Full text of bilingual article (PDF): https://psta.psiras.ru/read/psta2025_2_3-54.pdf (Clicking on the flag in the header switches the page language).
The article was submitted 15.03.2025; approved after reviewing 02.04.2025; accepted for publication 02.04.2025; published online 21.04.2025.
