Re: How to write a self-referencial TM?

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.

Your question "what is the source of such UTM?" seems to be asking to be pointed to some sample
source code for a UTM?  I don't have any!  But I'm sure someone somewhere will have gone to all the
trouble of coding an actual UTM, and will have made that available online somewhere.  Note that a
UTM is a firstly a TM, but TMs can be described as text "source code" and someone could have made
that available online.
 
Perhaps someone else here knows of useful sources for this?  Otherwise you would need to search for
it with Google or whatever.   IF THIS IS WHAT YOU REALLY WANT, which seems unlikely to me.
 
Most people aren't interested in specific source code for an actual UTM, because the role of a UTM
is /theoretical/, and most people can /see/ what a UTM needs to do, and how it can do it, so there
is no doubt in their mind that such a UTM /could/ be written.  I daresay that most programmers could
easily write one themselves, were it not for the huge burden of having to work within the TM
architecture with only the low level facilities TMs provide.  So they consider it a lot of work, and
at the end they would have a UTM source code, but /what would they plan to do with it/ ??  You would
only do all this work if you needed to actually /use/ the UTM, but TMs are not /intended/ as a
practical programming tool.
 
So... Do you /really/ need an actual UTM source code? I wonder.  What do you intend to use it for?
 
If you need to develop/test/debug your own TMs, rather than a UTM source code you need some kind of
TM development environment.  I don't know if such a thing exists for serious use!
 
If you're just playing/learning about TMs then probably you really just want a very basic TM
emulator (NOT a UTM) that can take a TM description and output for you the successive steps of its
execution, showing the tape contents and position of the tape head.  Loads of (most?) CS students
will have done this themselves at some point, using their own favourite language - you could use
Python, C++, Java, whatever you like.  I once wrote myself one of these as a play thing in C++ and
it took a few hours perhaps.  (Most of the time was fiddling with output formats to make the output
appear in a way I liked.  I got bored eventually!)  You could do this yourself...
 
Or... is it that you don't /understand/ something about UTMs and need convincing?  I think just
explaining what is confusing you and asking questions would be a better way to go!
 
Mike.

No need to make things such complicated and thus unnecessary long comments. 
We can simply assume the 'source-code' is machine code, the debuger in every OS is already a 'UTM'
except it cannot simulate itself....  No UTM exists that can simulate any TM including itself.