Re: No TM exists that can simulate all TM.

On 10/26/24 10:08 AM, wij wrote:

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?
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.

 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?
 

So, what does utm() do, one good definition is just halt.
thus utm(utm) would emulate utm() which would just see it doesn't have an input and halt.
UTMs are given a "description" of the Turing Machne and of its input, expressed in the "language" of the UTM.
A simple (to understand,complicated to build) would be one where you give as an input listing of every possible state the machine could be in and every possible input character, and lists the resulting state, character to put on the tape, and tape motion, and the starting state, Then you put the contents of the tape that machine is to process with the current pointer of the starting point.
The UTM then just applies the rules described in the first part, to the tape described in the second part, and when it gets to a state marked as a final state (perhaps one of the tape operations is "Halt", or states are marked as terminal) it stops and returns the results.
This means that the UTM just "zimulates" the execution process of a Turing Machine, where one "step" takes the current state, and the contents of the tape at its current position, and updates the tape to the new value and move the current location of the tape, and updates the current state.
The "proof" of the existance of a UTM was the proof that a Turing Machine could be programmed to do that set of transformations.