Re: How to write a self-referencial TM?

On 2025-05-14 21:13:19 +0000, Mr Flibble said:

On Wed, 14 May 2025 13:49:03 -0700, Keith Thompson wrote:
 

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.

 Flibble's Law still applies:
 If a problem permits infinite behavior in its formulation, it permits
infinite analysis of that behavior in its decidability scope.

You cannot pose in finite time a problem that has an infinite behaviour
in its formulation. If the problem will not be posed in a finite time
it will never be solved.
--
Mikko