Re: How to write a self-referencial TM?

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

I presume that one-way and two-way infinite tapes are computationally
equivalent, so the distinction doesn't matter all that much.
(Though with a one-way tape, I'm not sure what happens if the TM
runs off the end of the tape.)

I should imagine that you could build one hell of a stack on one-way tape.
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.
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.
Ought to be enough for `take one down and pass it around'.
--
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