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.
Best Answer
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.