The worksheetDownload the PDF
Answers

A6.9 Turing machines

Theory of computation · A level · AQA 7517 4.4.5.1 · about 25 min

BugBotLab

What this lesson is about

Tape, head, states and transition functions; tracing a Turing machine; the universal Turing machine and why it matters.

Questions 6 marks in all

  1. [1 mark]Which are parts of a Turing machine?

    Tick every answer that is true.

    1. AA tape that is infinitely long
    2. BA read/write head
    3. CA finite set of states including a start state
    4. DAn unlimited number of states
    5. EA transition function
    Answer: A, B, C, E. The tape is unlimited but the states and alphabet are finite. That is what separates it from an FSM with a fixed memory.

  2. [1 mark]What does δ(S2, 0) = (S3, 1, ←) mean?

    1. AIn S3 reading 1, write 0, move left and go to S2
    2. BIn S2 reading 0, write 1, move left and go to S3
    3. CIn S2 reading 1, write 0, move right and go to S3
    4. DIn S2 reading 0, write 0, move left and go to S3
    Answer: B. The left side is the current state and the symbol read; the right side is the next state, the symbol written and the move.

  3. [1 mark]The parity Turing machine adds an even parity bit to a binary string. What is on the tape when it halts, if the input is 10110?

    Answer: 101101. 10110 has three 1s, an odd number, so the machine writes 1 at the end.

  4. [1 mark]What is a universal Turing machine?

    1. AA Turing machine with an infinite number of states
    2. BA Turing machine that can simulate any other Turing machine, given its description and input on the tape
    3. CA Turing machine that solves the Halting problem
    4. DA real computer built by Turing
    Answer: B. Reading another machine's rules as data is the stored program concept, the basis of general-purpose computers.

  5. [1 mark]Why are Turing machines important to computer science?

    1. AThey are faster than modern computers
    2. BThey give a definition of what is computable: anything a computer can compute, a Turing machine can too
    3. CThey can solve the Halting problem
    4. DThey need no states
    Answer: B. A problem that no Turing machine can solve cannot be solved by any computer.

  6. [1 mark]What does this program print?

    table = {("S0", "1"): ("S0", "0", "R"), ("S0", "0"): ("S0", "1", "R"), ("S0", "_"): ("SH", "_", "R")}
tape = dict(enumerate("1100"))
head, state = 0, "S0"
while state != "SH":
    state, write, move = table[(state, tape.get(head, "_"))]
    tape[head] = write
    head = head + 1 if move == "R" else head - 1
print("".join(tape[i] for i in sorted(tape)).strip("_"), head)
    Answer:
    0011 5

    The machine flips every bit moving right, then halts on the blank, moving one more cell to position 5.

The task: add one in binary

Write the transition table for a Turing machine that adds 1 to a binary number, and run it with run. - run(table, text) is written for you. The head starts on the first (leftmost) symbol in state "S0", the machine halts when it reaches state "SH", blanks are "_", and run returns what is left on the tape with the blanks at either end removed. It gives up and returns None after 1000 steps. - Write table: each key is (state, symbol) with symbol one of "0", "1", "_", and each value is (next_state, write, move) with move either "L" or "R". Use as many states as you need, with "S0" as the start state. - The arithmetic must be done by the machine: no int, bin or format. - For each string in tests, in order, print it, -> , then the result of running your machine on it. For example 1011 -> 1100. Four lines in all. Think about how you add 1 by hand: where do you start, and what happens to a run of 1s at the end?

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

tests = ["1011", "111", "0", "1001"]

def run(table, text):
    tape = dict(enumerate(text))
    head = 0
    state = "S0"
    for steps in range(1000):
        if state == "SH":
            return "".join(tape[i] for i in sorted(tape)).strip("_")
        symbol = tape.get(head, "_")
        state, write, move = table[(state, symbol)]
        tape[head] = write
        head = head + 1 if move == "R" else head - 1
    return None

table = {}

The hint students can ask for: Adding 1 starts at the rightmost digit, but the head starts at the left, so the first state's job is to move right until it finds the blank, then step back. A second state then works leftwards: a 1 becomes 0 and the carry moves on; a 0, or a blank past the left end, becomes 1 and the machine halts.

A solution

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

tests = ["1011", "111", "0", "1001"]

def run(table, text):
    tape = dict(enumerate(text))
    head = 0
    state = "S0"
    for steps in range(1000):
        if state == "SH":
            return "".join(tape[i] for i in sorted(tape)).strip("_")
        symbol = tape.get(head, "_")
        state, write, move = table[(state, symbol)]
        tape[head] = write
        head = head + 1 if move == "R" else head - 1
    return None

table = {
    ("S0", "0"): ("S0", "0", "R"),
    ("S0", "1"): ("S0", "1", "R"),
    ("S0", "_"): ("S1", "_", "L"),
    ("S1", "1"): ("S1", "0", "L"),
    ("S1", "0"): ("SH", "1", "L"),
    ("S1", "_"): ("SH", "1", "L"),
}
for text in tests:
    print(text, "->", run(table, text))

Any program that meets the task's checks is marked correct in the simulator; this is one way, not the only way.