4.4.5.1 - Turing machines as a model of computation (VB.NET)

Tape, states and transition rules

A Turing machine is a formal model of computation with a single fixed program, represented by finitely many states and transitions. Its memory is a tape divided into squares, each holding one symbol from a finite alphabet. A sensing read-write head reads and writes its current square and travels one square at a time.

AQA questions use one tape infinite in one direction. Here squares are numbered 0, 1, 2 and so on, with a left boundary at 0 and unlimited squares to the right. B denotes a blank square. An input occupies finitely many squares and all other squares initially contain B. The finite alphabet can therefore represent input symbols plus B; an infinite tape does not require infinitely many different symbols.

One state is the start state. A halting state has no outgoing transitions. A transition is chosen using both the current state and the symbol under the head; it specifies a symbol to write, a move and a next state. Use the following transition-function convention:

For unary increment, represent a non-negative integer by that many consecutive 1 symbols starting at square 0. The program is:

The first rule passes over an existing 1 without changing it. The second writes one more 1 at the first blank and then halts. No rule moves left at the left boundary. The same fixed rules work for every finite unary input.

[DIAGRAM: asset_slug: vbnet_turing_unary_increment; description: Unary increment keeps each existing 1 and moves right, then writes 1 on the first blank and enters the halting state.]

In this diagram an edge label is read / write, move. The source and destination nodes supply the current and next states. Thus q0's self-loop labelled 1 / 1, R is exactly the first function rule. Its edge to qh labelled B / 1, R is exactly the second. qh is drawn with a double outline and labelled halt; its halting property is the absence of outgoing transitions, not an FSM acceptance convention.

To construct a diagram in a notebook, make one node per state, mark the start, and draw one directed labelled edge for every rule. To convert back, read the source state and read-symbol into the left side of δ, and the destination, write-symbol and movement into the right side. The diagram and function are equivalent representations of the program.

Hand-tracing a computation

A hand trace records the machine's configuration: state, head position and tape contents. Apply just one applicable rule at a time, using the symbol under the head before writing or moving.

For the unary-increment machine, begin in q0 with head at square 0 and tape 111BBBB…. The first three rules leave the 1s unchanged. The fourth replaces the first blank.

The output is four 1s and the machine stops. Moving into qh is part of the last transition, so the final head is at square 4, not square 3. For an empty unary input the first square is B: one transition writes 1, moves to square 1 and halts. Thus the zero case is handled by the same rule, without a special program.

A finite computation uses only finitely many tape squares despite the unbounded tape available in the model. If a transition rule is missing for a configuration, state the supplied convention rather than guessing another move. These examples halt only at the explicitly named halt state. Do not confuse a machine revisiting a state with non-termination: q0 is visited many times, but the head progresses to a blank on a finite input.