Re: How to write a self-referencial TM?

Richard Heathfield <rjh@cpax.org.uk> writes:

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.

TM's don't necessarily operate in the Real World.

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'.

Sure.  "Infinite tape" might be more precisely expressed as
"sufficient tape".  But a TM that advances in one direction along
the tape in a loop will require more than any finite length of tape
if you leave it running long enough, though the amount of tape it
consumes in any finite number of steps is still finite.  For that
kind of TM in particular, "infinite tape" is a convenient shorthand.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */