[Math] Designing a turing machine

computer sciencenumber theoryturing-machines

Suppose you have a tape that has a block of $a$ strokes followed by a
space, followed by a block of $b$ strokes, followed by a space,
followed by a block of $c$ strokes, and otherwise blank. Design a
Turing machine that starts on the leftmost stroke and halts, but
neither prints nor erases anything..

a) on the leftmost stroke of the second block.

b) on the leftmost stroke of the third block.

I have an exam tomorrow and I'm trying to prepare for Turing machine questions. Can someone please walk me through one of a) or b) above? How will the Turing machine ultimately look in either case?

Best Answer

First, let's start with a high level description of such a machine. Abstractly, we want to scan to the right across the tape, and test when we've passed from one block into the next. More concretely, we want to count how many spaces we've passed (since spaces are the dividing symbols between blocks). Once we've passed one space, we're going into the second block of strokes; after two spaces, we're going into the third block.

Next, we'll describe the state transition function for our first machine:

From the initial state $q_0$, if the symbol under the tape head is a stroke, move right (without writing to the tape, of course), and stay in the same state. If the symbol is a space, move right and halt (then the tape head will stop directly on the first stroke of the second block). If the symbol is a blank, we have an error.

The precise, low-level definition of the Turing machine now depends on your exact definition. For definiteness, I'll use this definition (Source: http://en.wikipedia.org/wiki/Turing_machine#Formal_definition, paraphrased slightly):

A Turing Machine is a 7-tuple $M = (Q, \Gamma, b, \Sigma, q_0, F, \delta)$, where:
  • $Q$ is a finite, nonempty set (the state set),
  • $\Gamma$ is a finite, nonempty set (the tape alphabet),
  • $b \in \Gamma$ is the blank symbol,
  • $\Sigma \subseteq \Gamma \setminus \{b\}$ is the input alphabet,
  • $q_0 \in Q$ is the initial state,
  • $\varnothing \ne F \subseteq Q$ is the set of final (halting) states, and
  • $\delta: (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L,R\}$ is the state transition function.

We'll do the easy ones first: The tape alphabet $\Gamma$ consists of three symbols, $\Gamma = \{ b, /, \_\}$, where $b$ is the blank symbol, $/$ is the stroke, and $\_$ is the space. $\Sigma = \{ /, \_ \}$ is our input alphabet.

Our state set $Q$ has three elements, say $Q = \{q_0, q_\textrm{HALT}, q_\textrm{ERR}\}$, where $q_0$ is the initial state and $F = \{q_\textrm{HALT}, q_\textrm{ERR}\}$ are the halting states. So, all that's left is to define $\delta$, which we'll do as follows:

$$\begin{align} \delta(q_0, /) &= (q_0, /, R) \\ \delta(q_0, \_) &= (q_\textrm{HALT}, \_, R) \\ \delta(q_0, b) &= (q_\textrm{ERR}, b, R) \\ \end{align}$$

This completes the low-level definition of the first machine.

For the second machine, we need a little bit more complexity. This time, we want to scan right until we find the first space, remember that we've seen it, then scan right again to the second space, and stop on the next stroke. Remember that a Turing machine has only two ways of "remembering" anything: either on the tape, or in its state. Since we aren't allowed to write to the tape, we'll use state. In particular, we'll use two non-final states this time. Our initial state $q_0$ will scan right as before, but once it finds a space, it will transition to state $q_1$ instead. Then, $q_1$ will scan right in the same way until it finds a space; once it finds a space, $q_1$ will transition to $q_\textrm{HALT}$.

Formally, replace $Q$ above by $Q' = \{q_0, q_1, q_\textrm{HALT}, q_\textrm{ERR}\}$, and replace $\delta$ above by $\delta'$ defined as follows:

$$\begin{align} \delta'(q_0, /) &= (q_0, /, R) \\ \delta'(q_0, \_) &= (q_1, \_, R) \\ \delta'(q_0, b) &= (q_\textrm{ERR}, b, R) \\ \\ \delta'(q_1, /) &= (q_1, /, R) \\ \delta'(q_1, \_) &= (q_\textrm{HALT}, \_, R) \\ \delta'(q_1, b) &= (q_\textrm{ERR}, b, R) \end{align}$$

Note that usually, we just give a high-level description of a Turing machine, since that whole low-level description is hard to write, hard to read, and not very enlightening. But, especially when first studying the subject, it's important to keep in mind what the low-level machine actually looks like.

Here are graphical representations of the two machines: First machine Second machine