Re: How to write a self-referencial TM?

On 14/05/2025 21:16, Richard Heathfield wrote:

On 14/05/2025 21:00, Keith Thompson wrote:

I presume that one-way and two-way infinite tapes are computationally
equivalent, so the distinction doesn't matter all that much.

Indeed, there are lots of computationally equivalent versions:
  -- two or more tapes [indeed, two-dimensional tapes]
  -- one-way or two-way
  -- "paper" tapes where you can punch holes to change the content but not
       stick the chad back in to "unpunch" the holes
  -- two symbol, three symbol, ...
  -- move two or more spaces at a time
  -- others I've forgotten
Once you've shown they're equivalent, you can use a convenient version to
solve problems and the simplest versions to investigate theoretical limits.
See below for more info.

(Though with a one-way tape, I'm not sure what happens if the TM
runs off the end of the tape.)

It's helpful to have an end-of-tape "marker" [could be a symbol
used only for this purpose].

I should imagine that you could build one hell of a stack on one-way tape.

Yes, but for theoretical purposes you probably need two stacks [or
near equivalents] to hold two arbitrary-length integers.  On the other hand,
the tape can be read as two integers reading outwards from the head position,
and the TM transitions then correspond to fiddling with the least-significant
digits of these integers.  See also below.

Of course, the tape doesn't /have/ to be infinite. It only has to be long
enough so that you /don't/ run off the end. Just how long that is depends
on what problem you're addressing.
In the Real World, tapes can't be infinite, so an implementor has to decide
how long 'long enough' is.

An alternative view is that you can attach a "tape factory" to your
TM, and add a new square or three when you would otherwise run off the end.

If the TM's alphabet consisted of 256 discrete symbols (no reason why not)
a megabyte would give you a disk-based 'tape' a million cells long.

When I was lecturing this stuff, it was common for software to be
delivered as a stack of floppy discs accompanied by instructions such as
"now mount the next disc".  So I used to point out to the students that
this was quite precisely a TM.  The PC was a FSM which could read/write
"squares" consisting of one floppy disc each containing several million
binary digits depending on the state of the PC, from time to time going to
the next or previous floppy.  If you didn't have a next floppy, you went
to a shop and bought some more.
All the material described above is discussed in my lecture notes,
on the Web starting at
   https://www.cuboid.me.uk/anw/G12FCO/header.html
[see especially the last few lectures/problem classes/courseworks, all
linked from the header page].  Of course, there are many other excellent
web pages and books that discuss this stuff with varying degrees of
formality and level of maths/logic required as a pre-requisite.
[May be worth noting that the references to emulation and to self-
referential programs in lecture 18 pre-date musings by Messrs Olcott and
Flibble by years, and they certainly weren't original to me.]
--
Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Heller