A6.9 Turing machines worksheet

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

Questions 6 marks in all

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

Tick every answer that is true.

AA tape that is infinitely long
BA read/write head
CA finite set of states including a start state
DAn unlimited number of states
EA transition function

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

AIn S3 reading 1, write 0, move left and go to S2
BIn S2 reading 0, write 1, move left and go to S3
CIn S2 reading 1, write 0, move right and go to S3
DIn S2 reading 0, write 0, move left and go to S3

[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?

[1 mark]What is a universal Turing machine?

AA Turing machine with an infinite number of states
BA Turing machine that can simulate any other Turing machine, given its description and input on the tape
CA Turing machine that solves the Halting problem
DA real computer built by Turing

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

AThey are faster than modern computers
BThey give a definition of what is computable: anything a computer can compute, a Turing machine can too
CThey can solve the Halting problem
DThey need no states

[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)

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 = {}

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/a6-9-turing-machines/
The simulator checks it and tells you when it passes. Nothing to install, no account.

A6.9 Turing machines

What this lesson is about

Questions 6 marks in all

The task: add one in binary

Challenges