50.002 Computation Structures
Information Systems Technology and Design
Singapore University of Technology and Design

Turing Machine

Each topic’s questions are grouped into three categories: basic, intermediate, and challenging. You are recommended to do all basic problem set before advancing further.

The amount of practice problems in this set is smaller than usual because the topics learned this week is mainly to set up the knowledge required for the following week. Please head to the next problem set for more practice problem.

Ben’s Turing Machine (Basic)

Ben Bitdiddle’s proposed Ph.D. thesis involves writing a program to compute a function $f(x)$ on a Cray supercomputer. Ben’s advisor points out that $f$ cannot be computed on any Turing machine. Should Ben care? Why?

Show Answer

Church's thesis says that if the function can't be computed on any Turing machine, then it can't be computed on any physically realizable machine that we know of. So Ben is out of luck... a Cray supercomputer isn't "super" in that sense.

Discouraged by your answer to the last question, Ben has turned his attention to an alternative thesis topic. He now proposes to invent the universal FSM, which will be to FSMs what a universal Turing machine is to Turing machines. Ben’s idea is to build an FSM that can fed a sequence of inputs describing any other FSM and the inputs to that FSM. The universal FSM would then emulate the behavior of the described FSM on the specified inputs. Is Ben’s idea workable Why or why not?

Show Answer

Unfortunately, the Universal FSM will have some fixed number (N) of states built into its design. So it won't have enough states to emulate machines with more than N states. Ben's idea isn't workable, and there's no such thing as "Universal FSM" as he proposed.

FSM in TM (Intermediate)

We encode the state of a Turing machine into 2 bits, the value that is read (input) from and written (output) onto the infinite tape into 2 bits, and the output move on the tape (left or right) into 1 bit. How many different finite state machines are there to control such a Turing machine?

Video Explanation here.

Show Answer

From the explanation above, we have:

`s = 2`
`i = 2`
`o = 3`

We can enumerate this many FSMs given s, o, and i bits: $$2^{(s+o)2^{s+i}}$$ Hence the answer to this question is: $$2^{80}$$

Running a Turing Machine (Basic)

You are given a Turing machine (TM) with three states (S0, S1, S2) and a HALT state and the following state transition diagram and state table. The TM operates by reading and then moving either left (L) or right (R) on an infinite tape. Note that the question defined it as we move the machine here (move the arrow), and not move the tape.

The tape is used to encode a binary number with three symbols, 0, 1 and _, where _ is used to signal the beginning and end of the number. For instance, the binary number 1011 is represented on the tape as _,1,0,1,1,_ (most significant bit on the left).

If the tape is in the initial configuration _,1,0,1,1,_:

The Turing machine starts in state S0,
And it is currently reading (pointing to) the tape containing the 0,

What is the state transition sequence that the machine is going to execute (including the start state S0) until it meets a HALT?

Show Answer

Answering this is none other than executing the Turing Machine with the given tape _,1,0,1,1,_ and initial state `S0`, with the machine reading the tape at the 0.

The sequences of the states until HALT is met is: S0, S0, S0, S0, S1, S1, S1, S2, S2, S2, HALT

What is the final configuration of the tape after the TM has halted and what does the TM do?

Show Answer

The final tape configuration is: _,1,1,0,0,_ It is obvious that the TM adds 1 to the input number.

Edge Detector Machine (Intermediate)

The figure below shows a particular tape state before and after a Turing Machine that does edge detection is executed for 12 steps (12 clock cycles).

Indicate which of the following Turing Machine specification: [A], [B], [C], [D], [E] shown below is/are able to produce the tape state after exactly 12 cycles.

Specification [A]:

$\begin{matrix} S_i & \text{Input} & S_{i+1} & \text{Output} & \text{Move Tape}\\ \hline S_0 & 0 & S_0 & 0 & L\\ S_0 & 1 & S_1 & 1 & L\\ S_1 & 0 & S_0 & 0 & L\\ S_1 & 1 & S_2 & 0 & L\\ S_2 & 0 & S_0 & 0 & L\\ S_2 & 1 & S_2 & 0 & L\\ \hline \end{matrix}$
Specification [B]:

$\begin{matrix} S_i & \text{Input} & S_{i+1} & \text{Output} & \text{Move Tape}\\ \hline S_0 & 0 & S_0 & 0 & L\\ S_0 & 1 & S_1 & 1 & L\\ S_1 & 0 & S_0 & 0 & L\\ S_1 & 1 & S_1 & 1 & L\\ \hline \end{matrix}$
Specification [C]:

$\begin{matrix} S_i & \text{Input} & S_{i+1} & \text{Output} & \text{Move Tape}\\ \hline S_0 & 0 & S_0 & 0 & L\\ S_0 & 1 & S_1 & 1 & L\\ S_1 & 0 & S_0 & 0 & L\\ S_1 & 1 & S_1 & 0 & L\\ \hline \end{matrix}$
Specification [D]:

$\begin{matrix} S_i & \text{Input} & S_{i+1} & \text{Output} & \text{Move Tape}\\ \hline S_0 & 0 & S_0 & 0 & L\\ S_0 & 1 & S_1 & 1 & L\\ S_1 & 0 & S_0 & 0 & L\\ S_1 & 1 & S_2 & 1 & L\\ S_2 & 0 & S_0 & 0 & L\\ S_2 & 1 & S_2 & 1 & L\\ \hline \end{matrix}$
Specification [E]:

$\begin{matrix} S_i & \text{Input} & S_{i+1} & \text{Output} & \text{Move Tape}\\ \hline S_0 & 0 & S_0 & 0 & L\\ S_0 & 1 & S_1 & 1 & R\\ S_1 & 0 & S_0 & 0 & L\\ S_1 & 1 & S_2 & 0 & R\\ S_2 & 0 & S_0 & 0 & L\\ S_2 & 1 & S_2 & 0 & R\\ \hline \end{matrix}$

Show Answer

Specification `[A]` and Specification `[C]` produces the **same** output tape as shown above, given the initial tape content and the Turing Machine's start state (and location). We can run the machine five times with each specifications to obtain the answer, but the faster way is to observe them based on the functionality:

To detect an edge, there's no need to "re-read" previous input. Therefore Specification `[E]` is definitely wrong (we only need to move the tape in one direction).
We only output 1 once on the occurence of an edge, so the specification shall not output too many 1s. You can then start to suspect whether Specification `[B]` and `[D]` are true, and quickly eliminate them from the pool of possible answers.