Re: How to write a self-referencial TM?

On 2025-05-18 23:54:17 +0000, wij said:

On Sun, 2025-05-18 at 19:09 -0400, Richard Damon wrote:

On 5/18/25 6:09 PM, olcott wrote:

On 5/18/2025 4:46 PM, wij wrote:

On Sun, 2025-05-18 at 15:57 -0500, olcott wrote:

On 5/18/2025 3:35 PM, wij wrote:

On Sat, 2025-05-17 at 14:39 -0500, olcott wrote:

On 5/17/2025 2:26 PM, wij wrote:

On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:

On 17/05/2025 04:01, wij wrote:

On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:

On 16/05/2025 20:35, wij wrote:

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

On 16/05/2025 12:40, wij wrote:

On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wrote:

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.

 Sorry for not being clear on the UTM issue (I wanted to mean> > > > > >

several things in one

post).
You are right there is no self-reference.
I mean 'UTM' is not a complete, qualified TM because the> > > > > > > >

contents of the tape

would not be defined. Saying "UTM can simulate any TM" is> > > > > > >

misleading because

no such TM (UTM as TM) exists.

 What do you mean "the contents of the tape would not be> > > > > > > >

defined"?  A TM is

/equipped/
with
an
infinite tape, but the /contents/ of that tape are not a part> > > > >

of that TM's

definition.
 For example we could build a TM P that decides whether a> > > > > > > >

number is prime.  Given a

number n,
we
convert n into the input tape representation of n, and run P> > > > > >

with that tape as

input.
 It's essentially no different for UTMs.  Such a UTM certainly> > > > >

is a "complete TM",

equipped
with
its
own input tape.  Of course we don't know what's on the input> > > > > >

tape because nobody has

said
yet
what
computation we are asking it to simulate!  [Similarly we> > > > > > > >

don't know what's on P's

input
tape,
until
we know what n we want it to test for primeness.]  Once you> > > > > >

say what computation you

want
the
UTM to
simulate we can build a tape string to perform that> > > > > > > > > >

particular simulation.  That is

the
case
/whatever/ computation we come up with, so it is simply the> > > > > >

case [not misleading]

that
the
UTM
can
simulate any computation.
  Mike.

 TM has no I/O mechanism. 'Computation' always means the> > > > > > > >

contents of the tape

is defined (fixed before run).
 

 Correct, and correct.
 So... What do you mean "the contents of the tape would not be> > > > >

defined"?

  Mike.

 In "UTM simulates itself", denoted as U(U(f)), the f would not> > > > >

be defined.

 Eh?  The f was something /you/ introduced!  You said it> > > > > > > > represents some computation which
UTM U
simulates.  How can f suddenly become undefined after you defined> > >

it?

 Do you mean that f would not be on the input tape for (outer)U? > > > >

That's not the case at

all.  In
U(f), the input tape for U contains a representation of f.  When> > > >

(outer)U simulates (inner)U

simulating f, (outer)U's tape contains a representation of> > > > > > >

computation U(f), which

internally
contains the original representation of f.  The f is still there> > > >

and equally well defined in

U(U(f)).
 I think you would benefit from being more explicit and generally> > > >

more careful in your

notation!
 Using notation <P,I> to mean U's input tape representation of "TM> > >

P, running with input I":

        Your U(f)      is U(<fp,fi>)        // fp = TM(f),> > > > > > >

fi=InputTape(f)

       Your U(U(f))   is U((<U,<fp,fi>>)
 f is still there!  It has not become "undefined".
 You gloss over the details and become confused - just think it> > > > >

through step by step.

  Mike.

 It seems you are addressing notational problems.
You introduced angle bracket and one more variable, and seemingly> > >

attacking

that a variable cannot be undefined because it is there. And said> > >

I should

not gloss over the detail and should think it through step by step.
No idea what you are talking about.
 

 U(<U>)    is the most conventional notation

 U is not a complete TM. U(<U>) is worst, also not a TM.
 

 It is stipulated that U is a UTM that
has its own source-code as its input.

 UTM is not a complete TM.> >> > Textbooks define a UTM as a complete TM.

 

 As I pointed out, there are two definitions of what a Turing Macine is.
 It can be just the algorithm part, or the combination of the Algorithm> and Input.
 In either case
 "U <U>" isn't a valid computation, as in the TM is just tha algoritm> case, where <U> is a valid string for the representation of the TM, a> UTM needs as its input the combination of the representation of the> input program and the representation of its input (if it takes any), so,> since the program is a UTM, and that needs an input, you need to add it.

 Note that TM cannot *read* input as external information, everything is fixed.
I have no problem with the 'two definition' saying, you just have to make 
it clear (but as usual in your real number, you invent your own stuff, you 
are not following your 'standard' and condemn others not following it).
However this 'other' definition of TM if exists will have no computation 
(nothing in the tape). You cannot talk about 'computation'.

The term "computation" has been used for efforts like to detemine the
first million digitl of pi. No input.
--
Mikko