Turing Machines Equipped with CTC in Physical Universes

01/27/2023
by   Sara Babaee Khanehsar, et al.
0

We study the paradoxical aspects of closed time-like curves and their impact on the theory of computation. After introducing the TM_CTC, a classical Turing machine benefiting CTCs for backward time travel, Aaronson et al. proved that P = PSPACE and the Δ_2 sets, such as the halting problem, are computable within this computational model. Our critical view is the physical consistency of this model, which leads to proposing the strong axiom, explaining that every particle rounding on a CTC will be destroyed before returning to its starting time, and the weak axiom, describing the same notion, particularly for Turing machines. We claim that in a universe containing CTCs, the two axioms must be true; otherwise, there will be an infinite number of any particle rounding on a CTC in the universe. An immediate result of the weak axiom is the incapability of Turing machines to convey information for a full round on a CTC, leading to the proposed TM_CTC programs for the aforementioned corollaries failing to function. We suggest our solution for this problem as the data transferring hypothesis, which applies another TM_CTC as a means for storing data. A prerequisite for it is the existence of the concept of Turing machines throughout time, which makes it appear infeasible in our universe. Then, we discuss possible physical conditions that can be held for a universe containing CTCs and conclude that if returning to an approximately equivalent universe by a CTC was conceivable, the above corollaries would be valid.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset