Re: How to write a self-referencial TM?

On 14/05/2025 19:01, wij wrote:

On Wed, 2025-05-14 at 18:49 +0100, Richard Heathfield wrote:

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

On Wed, 2025-05-14 at 18:14 +0100, Richard Heathfield wrote:

On 14/05/2025 17:43, wij wrote:

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

>
<snip>
>

>

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?

>
It doesn't have to simulate anything. All it has to do is to
restore the state into which the programmer wishes to recurse.

>
So, when you say "A UTM simulates X", it means 'the UTM' doesn't have to do
anything. So, 'UTM' is human (e.g. you), not a real TM?

>
No, it doesn't mean that.

 You said "It doesn't have to simulate anything. All it has to do is to
restore the state into which the programmer wishes to recurse."

Yes.

 Then, what is it?

It's my answer to your question:
Q: Write a turing machine that performs D function (which calls itself):
void D() {
  D();
}

I've already shown how this can be done.

Here's the gist of that article...
>
Here's the tape:
[0]
>
current state: 0
content of the square being scanned: 0
new content of the square: 0
move left, right, or stay: stay
next state: 0
>
This TM functions by returning the state of the machine to its
starting state.
>
The only functional difference between this code and yours is
that yours will blow the stack. (Mine doesn't have a stack to blow.)
>

 1. Apparently your TM (one single symbol '0') is not what you say.

[0] is the *tape*.
TMs have a tape, a read/write head, a single-stepping tape motor, and a finite state machine.
See <https://plato.stanford.edu/entries/turing-machine/>
where you can read this:
"A Turing machine then, or a computing machine as Turing called it, in Turing’s original definition is a machine capable of a finite set of configurations q1,…,qn (the states of the machine, called m-configurations by Turing). It is supplied with a one-way infinite and one-dimensional tape divided into squares each capable of carrying exactly one symbol. At any moment, the machine is scanning the content of one square r which is either blank (symbolized by S0) or contains a symbol S1,…,Sm with S1=0 and S2=1."
There's more to TMs than tapes.

2. D() should have at least one final state

Yours doesn't, so why should mine?
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within