Re: How to write a self-referencial TM?

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

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

It's still not long enough for a TM that repeatedly advances its
position in one direction while indefinitely repeating the same state.

In C terms, there is no real world output device that can hold the
output of `while (1) putchar('x');`.

It's the unboundedness of the tape that makes the halting problem
unsolvable.  It's what allows the combined internal (finite state)
and external (unbounded tape) state of a TM to be unbounded.  If we
considered only TMs that consume less than N tape cells, for any
finite N, the halting problem *for such TMs* would be theoretically
solvable by detecting or not detecting a repeated state.

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