Let us take a hypothetical machine i which halts on the ith day of the month if it rains on the ith day of the month. Basically it describes the present.

If we put this machine in a Halting Machine it should say whether the machine would halt. i.e. whether it would rain on the ith day of the month.

Since the Halting Machine is not possible, a time machine is not possible.

Is there any fault in my reasoning?

  • $\begingroup$ I suggest an introductory book to computability theory. Popular descriptions are apparently not good enough. $\endgroup$ Feb 25 '17 at 2:31

When we say that no Turing machine decides the halting problem, we mean just that – the mathematical model of a Turing machine has a certain limitation, not being able to compute the halting problem. Turing machines are supposed to model what is computable in the physical world, but this is not a mathematical fact. If the physical world turns out to be richer, all results on Turing machines will still hold, it's just that their real-world interpretation will be weaker.

What you show in your question is that if time travel is possible, then Turing machines are not a good model for the notion of computation. The fact that Turing machines cannot solve the halting problem has absolutely no bearing on the reality of time travel.

Moreover, you misrepresent the Turing machine model. A Turing machine has no access to the real world, so it cannot halt if it rains on a specific day. All it has access to is its (potentially infinite) tape. In fact, Turing machines cannot be realized in full generality in the real world (since their tape is potentially infinite) – they are abstract machines which are supposed to model some features of reality.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.