Re: How to write a self-referencial TM?

On 16/05/2025 02:47, wij wrote:

On Fri, 2025-05-16 at 01:40 +0100, Mike Terry wrote:

On 15/05/2025 19:49, wij wrote:

On Thu, 2025-05-15 at 17:08 +0100, Mike Terry wrote:

On 14/05/2025 18:53, wij wrote:

On Wed, 2025-05-14 at 12:24 -0500, olcott wrote:

On 5/14/2025 11:43 AM, wij wrote:

On Wed, 2025-05-14 at 09:51 -0500, olcott wrote:

On 5/14/2025 12:13 AM, wij wrote:

Q: Write a turing machine that performs D function (which calls itself):
>
void D() {
      D();
}
>
Easy?
>
>

>
That is not a TM.

>
It is a C program that exists. Therefore, there must be a equivalent TM.
>

To make a TM that references itself the closest
thing is a UTM that simulates its own TM source-code.

>
How does a UTM simulate its own TM source-code?
>

>
You run a UTM that has its own source-code on its tape.

>
What is exactly the source-code on its tape?
>

>
Every UTM has some scheme which can be applied to a (TM & input tape) that is to be simulated.
The
scheme says how to turn the (TM + input tape) into a string of symbols that represent that
computation.
>
So to answer your question, the "source-code on its tape" is the result of applying the UTM's
particular scheme to the combination (UTM, input tape) that is to be simulated.
>
If you're looking for the exact string symbols, obviously you would need to specify the exact
UTM
being used, because every UTM will have a different answer to your question.
>
>
Mike.

>
People used to say UTM can simulate all TM. I was questing such a UTM.
Because you said "Every UTM ...", so what is the source of such UTM?

>
Yes, a UTM can simulate any TM including itself.  (Nothing magical changes when a UTM simulates
itself, as opposed to some other TM.)

 Supposed UTM exists, and denoted as U(X), X denotes the tape contents of the
encoding of a TM. And, U(X) should function the same like X.
Given instance U(U(f)), it should function like f from the above definition.
But, U(U(f)) would fall into a 'self-reference' trap.

There is no self-reference trap.
In your notation:
-  f represents some computation.
-  U(f) represents U being run with f on its tape.
    Note this is itself a computation, distinct from f of course
    but having the same behaviour.
-  U(U(f)) represents U simulating the previous computation.
There is no reason U(f) cannot be simulated by U.  U will have no knowledge that it is "simulating itself", and will just simulate what it is given.
Mike.