Re: No TM exists that can simulate all TM.

On 10/25/24 1:12 PM, wij wrote:

Proof: Simulating self is not possible (from all real programs, every one can verify).
 This also implies UTM does not exist.
 Did Turing made a mistake?
https://en.wikipedia.org/wiki/Universal_Turing_machine
 

The key point you are missing is that if the UTM emulating a program like H^ (without the contrary nature at the end), so that we can get the infinite chain of UTM emulating that UTM emulating that UTM ..., it just ends up being a non-halting computation, and thus the non-halting emulation of that computation is exactly right.
The problem is if you want it to be a UTM and also a decider, then you run into the problem.
The UTM chain *IS* an infinite deep recursive simulation, which is just like the infinite-recursion, which is non-halting.
When you change the UTM to be a decider (and thus no longer a UTM) it finds it can't know the answer for the behavior of the UTM it was previously.