Re: How to write a self-referencial TM?

On 2025-05-14 20:00:13 +0000, Keith Thompson said:

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.

Post found that Turing's original machine could be simplified so that
every computation possible with the original machie is possible with
the simplified machine but reasoning about the simpified macnies is
simpler and easier than about the original machines. One of the
simplifications is that the tape has no beginning.
--
Mikko