On the definition of a Turing Machine as stated in Soare

Question

I am currently reading R. Soare's book Turing Computability. At page 7 the author gives the definition of a Turing Machine for the first time he writes,

Definition. A Turing machine (automatic machine, a- machine) $M$ includes a two-way infinite tape divided into cells, a reading head which scans one cell of the tape at a time, and a finite set of internal states $Q = \{q_0,q_1,\ldots,q_n\}$, $n \ge 1$. Each cell is either blank ($B$) or has written on it the symbol $1$. In a single step the machine may simultaneously: (1) change from one state to another; (2) change the scanned symbol $s$ to another symbol $s' \in S =\{1,B\}$; and (3) move the reading head one cell to the right ($R$) or left ($L$). The operation of $M$ is controlled by a partial map $\delta: Q\times S \to Q\times S\times \{R,L\}$ (which may be undefined for some arguments).

Now in this definition a lot of things are not made precise enough. They are as follows,

• What is the precise mathematical definition of "a two-way infinite tape"?

• What is the precise mathematical definition of a "cell"?

• What exactly is a "reading head"?

• What exactly is a "scanned symbol"? What are the differences between a scanned symbol and an ordinary symbol?

Next in the book it is written that,

We begin with $M$ in the starting state $q_1$ scanning the leftmost cell containing a $1$, called the starting cell.

My questions are,

• What is meant by "scanning" here?

• How can we precisely define "the leftmost cell"?

The notion of a "tape" and all these things is probably pretty intuitive to the computer science students but for a student coming from pure mathematics background, they are not at all intuitive to me and I don't understand the definition of a Turing Machine at all unless it is expressed in a precise form.

Answer 1

Part of Soare's point with this description is that Turing machines should match our intuitive conception of computing, so he's deliberately avoiding full formality. Other texts approach the topic with more formality; if memory serves, Sipser's book is quite formal on this point.

That said, here's one way reframe things precisely.

The key point is that we're going to replace "two-way tape" with $\mathbb{Z}$, and replace the collection of symbols in the various cells by a function $$f: \mathbb{Z}\rightarrow\{1,B\}$$ (where we interpret "$f(x)=\sigma$" as "the symbol in cell $x$ is $\sigma$"). Finally, we replace "the cell being scanned" by ... well, just an integer, and $L$ and $R$ with positive and negative incrementation.

The "data" of a Turing machine - what's on all the cells of the tape, what cell we're looking at, and what state we're in - is thus coded by a tuple $$(f,z,\alpha)$$ where $f:\mathbb{Z}\rightarrow\{1,B\}$, $z\in\mathbb{Z}$, and $\alpha\in Q$. This isn't the complete definition, but it's a good starting point.

---

Here's the complete definition:

• A Turing machine is a triple $M=(Q,\delta, q_0)$ where $Q$ is some finite set, $q_0\in Q$ (the "start state"), and $\delta$ is a partial function from $Q\times\{1,B\}$ to $Q\times \{1,B\}\times\{L,R\}$.

• For $M$ a Turing machine, an $M$-configuration is a triple $(f,z,q)$ where $f:\mathbb{Z}\rightarrow\{1,B\}$, $z\in\mathbb{Z}$, and $q\in Q$.

• Given a Turing machine $M=(Q,\delta, q_0)$ and an $M$-configuration $(f,z,q)$, if $\delta(q,f(z))$ is defined then we get a new $M$-configuration $M[f, z, q]=(f',z',q')$ given by:

  • If $\delta(q, f(z))=(p, a, L)$ then $q'=p$, $f'$ is given by $f'(z)=a$ and $f'(w)=f(w)$ for $w\not=z$, and $z'=z-1$.

  • If $\delta(q, f(z))=(p, a, R)$ then $q'=p$, $f'$ is given by $f'(z)=a$ and $f'(w)=f(w)$ for $w\not=z$, and $z'=z+1$.

Given a machine $M=(Q,\delta, q_0)$ and a map $f:\mathbb{Z}\rightarrow\{1,B\}$, we get the run of $M$ on $f$: this is the (possibly finite) sequence $$\gamma^M_0(f), \gamma^M_1(f), \gamma^M_2(f),...$$ where $\gamma^M_0(f)=(f,0, q_0)$ and $\gamma^M_{i+1}(f)=M[\gamma^M_i(f)]$ (assuming $\delta$ is appropriately defined; otherwise, the sequence stops at $\gamma^M_i(f)$).

---

There are various alternate presentations which result in an equivalent (in a precise sense) computability theory, so various texts use various different definitions. Some obvious changes include: insisting that $\delta$ be total (and adding an explicit "halting state" to compensate), allowing arbitrary finite symbol sets, using $\mathbb{N}$ instead of $\mathbb{Z}$ ("one-way infinite tape"), using $\mathbb{Z}\times\{1,2\}$ instead of $\mathbb{Z}$ and replacing $\mathbb{Z}\rightarrow\{1,B\}$ by $\mathbb{Z}\times \{1,2\}\rightarrow \{1,B\}\times \{1,2\}$ ("two two-way infinite tapes"), and so forth.

• That last one actually winds up being somewhat important once we talk about oracle machines. But at that point your understanding of classical Turing machines should be solid enough that the vagueness is palatable (alternatively, so that whipping up a precise definition is a good exercise).

Answer 2

Two-way infinite tape and cells:

Think of an unrolled roll of toilet paper that is infinitely long, and extends to the left and to the right infinitely far. There is a one-to-one map between cells and the integers, $\mathbb{Z}$. Each cell sits in one-to-one relation with an integer.

Cells are the square pieces of toilet paper. You can write a $1$ or a $B$ on each one. The reading head is just a device that can determine if a given cell has a $1$ or a $B$ written on it.

A scanned symbol is simply the $1$ or $B$ written in a cell. A cell might exist somewhere on the tape, but if it hasn't been read (scanned) it cannot be used to change the state of the Turing machine.

Scanning means reading successive squares of the toilet paper.

Answer 3

The missing bit of this definition is that it doesn't tell you about the state of a Turing machine - with that bit of information, the definition looks a lot more rigorous. In essence, the definition tells you how to define a Turing machine (which is not that useful alone), but not how to run it.

A Turing machine can be said to consist of the following information:

• A finite set $Q$ of states.

• A finite set $S$ of symbols.

• A partial map $\delta:Q\times S \rightarrow Q\times S \times \{R,L\}.$

The state of the Turing machine can be thought of in a number of ways; most conveniently, you can consider a tape as a map $t:\mathbb Z\rightarrow S$ and the reading head as some $n\in \mathbb Z$ and the machine's internal state to be an element $q\in Q$. The "scanned symbol" is the term under the reading head - i.e. $t(n)$. Then, a single step of the Turing machine transforms a state $(t,n,q)$ to $(t',n',q')$ as follows:

1. Compute the tuple $(q',s,d)=\delta(q,t(n))$.

2. Define $t'(m)$ as being equal to $t(m)$ if $m\neq n$ and equal to the computed $s$ at $n$ - i.e. $t'$ is just $t$ with the term under the reading head changed.

3. Define $n'$ as being $n+1$ if $d=R$ and $n-1$ if $d=L$ - this is how the reading head moves.

4. The value $q'$ is already read as part of the tuple.

So, essentially, the Turing machine always has this "tape" which is really just a function and some position on that tape, which is really just an integer, and some state, which is some element of a given finite set.

The rest refers to which state one begins a Turing machine in; in particular, to represent algorithms, we imagine that the tape $t:\mathbb Z\rightarrow S$ is constant outside of some interval $[0,n]$; in that interval, we write some arbitrary string of symbols representing the input (and, apparently, this book wants the first symbol to be $1$, but this is not really necessary) - this is a detail that matters less how it is handled. Then, we start updating the Turing machine's state according to the above rules.

One can also simplify the definition by taking the state to just be a map $t:\mathbb Z\rightarrow S$ and imagining that the reading head is always at $0$, but the output element of $\{R,L\}$ shifts the whole function (by precomposing $t$ with $x\mapsto x\pm 1$) either left or right after writing the new value at $0$.