Re: How to write a self-referencial TM?

On 5/14/2025 3:00 PM, Keith Thompson wrote:

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

See <https://plato.stanford.edu/entries/turing-machine/>
>
where you can read this:
>
"A Turing machine then, or a computing machine as Turing called it, in
Turing’s original definition is a machine capable of a finite set of
configurations q1,…,qn (the states of the machine, called
m-configurations by Turing). It is supplied with a one-way infinite
and one-dimensional tape divided into squares each capable of carrying
exactly one symbol. At any moment, the machine is scanning the content
of one square r which is either blank (symbolized by S0) or contains a
symbol S1,…,Sm with S1=0 and S2=1."
>
There's more to TMs than tapes.

[...]
>
Interesting.  The phrase "one-way infinite" implies that the tape
is infinite in only one direction, so the cells can be indexed by
non-negative integers.  Elsewhere on that web page, it acknowledges
that there are variations in Turing machines, including one-way
vs. two-way infinite tapes.  It's implied that Turings original
concept had a one-way infinite tape.  I wasn't able to confirm or
deny that in a very quick look through Turings original paper.
>
I've always assumed that a TM tape is two-way infinite.
>
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 don't think that is precisely accurate.
A unlimited tape is not an infinite tape
it merely has all of the space that it needs.