Re: How to write a self-referencial TM?

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

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

<snip>

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

Of course. HP is a thought experiment, not an exercise for hardware engineers (or indeed software engineers). I just can't help turning my thoughts in that direction.

 

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

Quite so.

 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.

All acknowledged, all agreed.
Using a highly questionable collection of approximations about the physical properties of 4mm mylar tape and the number of atoms in the universe, I calculated that by devoting /everything/ to this tape we could make it
5285412262156448202959830866807610993657505285
lightyears long (exACtly, of course).
It's still a long way off infinite, but I think it could possibly qualify as 'long enough'.
--
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