Re: No TM exists that can simulate all TM.

Am Sat, 26 Oct 2024 22:08:23 +0800 schrieb wij:

On Fri, 2024-10-25 at 18:17 -0400, Richard Damon wrote:

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?
 

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.

 
Simulator::= A TM (utm) that performs the same function as its argument
TM (f).
             IOW, utm(f)=f  (or utm(f,arg)=f(arg))
In case of self-simulation "utm(utm)" ... well, the argument utm has no
argument (empty tape?) to define its behavior. What is the outer utm
supposed to 'simulate'?
How do you define 'simulator'? What exactly does UTM simulate?

You also need an input for the simulated machine. I suppose you would
want an infinite chain of UTMs simulating themselves simulating
themselves (sic).

--
Am Sat, 20 Jul 2024 12:35:31 +0000 schrieb WM in sci.math:
It is not guaranteed that n+1 exists for every n.