Class 31 - Turing Machines


To be eligible for automatic Red Belt promotion, you need to complete Project 6 (including a good answer to its bonus Problem 8) by Friday, 22 April, and have also completed Project 5 (including Problem 8). Otherwise, you may qualify for the Red Belt exam by completing Problems 1-7 of both Project 5 and Problem 6. If you do this by Friday, 22 April, you will be able to take the Red Belt exam starting Monday, 25 April (and have an opportunity to ensure at least an A- in the course before the end of the semester).


Finite State Machines

A Finite State Machine is a very simple model of a machine that has a finite amount of memory (unlike the Turing Machine model which has an infinite amount of memory since the tape is infinitely long).

A Finite State Machine consists of:

  1. A finite alphabet of symbols (Σ). There is a finite set of symbols that can be written into squares on the tape.

  2. A finite set of states (Q). Some of the states may be distinguished as accepting states (for the FSM for a Turing Machine, we typically have a distinguished state called “Halt” where the machine stops if that state is reached). One of the states, q0Q, is designated the start state.

  3. A set of decision rules (δ: Q × Σ → Q). Each rule is a triple of the form: (state, symbol) → nextstate. If the machine is currently in state and the next input symbol is symbol, after reading the symbol the state is now in nextstate.

A Finite State Machine processes its input in order, starting in the start state, q0, seeing each input symbol only once and following the state rules. You can think of it as a machine that starts with the input on a finite tape, and process that input from left to right, reading one square at a time. An input string is accepted by a finite state machine if the state machine ends in an accepting state after processing that input string to the end.

Draw the machine described below and explain what language it recognizes (that is, the set of all strings it accepts):

Q = { A, B }
Σ = { 0, 1 }
q0 = A
Accepting states: { B }


(A, 0) → A
(A, 1) → B
(B, 0) → B
(B, 1) → A

Can you make a finite statement machine that recognizes the language of balanced parentheses?

S ::= ( S )
S ::= ε

Turing Machine

A Turing Machine is an abstract model of a digital computer devised by Alan Turing in 1936.

It consists of:

What does this Turing Machine do?

(S, 1) → (S, 0, R)
(S, 0) → (S, 1, R)
(S, #) → Halt

Go Outcome Turing Machine. Design a Turing Machine that starts with an input tape that starts with a #, is followed by a series of X and O symbols, followed by a # at the end. The output should be 1 if there are more X symbols than O symbols on the input take, and 0 otherwise (they are equal, or more O symbols). For example, if the input tape is #XOXXOOX# the output tape should be #1#.