Re: How to write a self-referencial TM?

Keith Thompson <Keith.S.Thompson+u@gmail.com> writes:

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 don't think it's explicit, but the paper does refer to input being "on
the beginning" of the tape.

I've always assumed that a TM tape is two-way infinite.

That is by far the more usual presentation these days.  A lot about
Turing's presentation has been tidied up over the years.

I presume that one-way and two-way infinite tapes are computationally
equivalent, so the distinction doesn't matter all that much.

Yes.  That's often presented as an "exercise to the reader".  There are
also multi-tape TMs, non-deterministic TMs and random TMs that can
access a tape of randomly chosen symbols.

(Though with a one-way tape, I'm not sure what happens if the TM
runs off the end of the tape.)

The usual presentation just says that TM stops if the action can't be
taken.  It need be no different to what happens if the state transition
function does not include the current state/input pair in its domain.

--
Ben.