Re: No TM exists that can simulate all TM.

On 10/27/24 5:05 AM, wij wrote:

On Sat, 2024-10-26 at 11:35 -0400, Richard Damon wrote:

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

 That's right. You need to REPROGRAM. You need to modify the transition function and
the symbols, and the tape contents.
Therefore, "No real UTM exists". "An Univeral TM" is a false idea.
 

No, the PROGRAM of the Turing Machine that is a UTM, is the single program that interprests those codes and transforms them. It can be one single program. The one slight, but solvable, difficulty is that we don't know how many states or characters are used by the target machine, so we encode those in the description tape with a method to encode arbitrary precision numbers, a solved problem.
Note, one good example that is very close to the idealized UTM (except for having only a finite memory, not an infinte tape) is a "modern" single core CPU chip. We can encode any program we want, and put it into the memory of the chip (which is its version of the "tape") and the CPU will run that progtram, and we don't need to change the CPU for each different program.