Re: How to write a self-referencial TM?

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

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