Re: No TM exists that can simulate all TM.

Am Sun, 27 Oct 2024 17:05:52 +0800 schrieb wij:

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?
 

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.

lolwut? The transition function is not modified, that would make it
a different machine. The tape of course needs to be modified.

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