Multitape Nondeterministic Turing Machines

A multitape, nondeterministic Turing machine class contributed to automata, an open-source Python library for automata theory. The MNTM class defines and runs Turing machines with any number of tapes, explores every branch of a nondeterministic computation breadth-first, and can replay a run on a single tape, following the textbook proof that both models are equally powerful.

By: Camilo Martínez

View on GitHub

MNTM is a class for automata, a Python library for finite automata, pushdown automata and Turing machines. It was developed as the final project for the Introduction to the Theory of Computation course lectured by Prof. John Richard Goodrick at Universidad de los Andes during the second semester of 2020, and then contributed to the library together with its tests and its single-tape simulation. The class is documented in the library's API reference, and the library's paper in the Journal of Open Source Software [Evans & Robson, 2023] acknowledges the contribution.

Why Multiple Tapes?

A Turing machine is a finite set of states, an unbounded tape divided into cells and a head that reads and writes one cell at a time. At each step, the current state and the symbol under the head decide what the machine writes, whether the head moves left or right and which state comes next. Simple as it is, the model can carry out any algorithm, which makes it the reference for what computers can and cannot do. A multitape Turing machine has several tapes, each with its own head: it reads the symbols under all its heads at once, then writes on every tape and moves every head independently (Figure 1). The input starts on the first tape and the others start blank. A nondeterministic machine may have several possible moves in the same situation, and it accepts its input if any sequence of choices reaches an accepting state.

Formally, a \(k\)-tape nondeterministic Turing machine is a tuple \((Q, \Sigma, \Gamma, \delta, q_0, \#, F)\) of states, input symbols, tape symbols, transitions, an initial state, a blank symbol and final states. Its transition function maps a state and the \(k\) symbols under the heads to a set of possible moves:

Each move names the next state and, for every tape, the symbol to write and where its head goes: left, right or nowhere (\(N\), which textbooks often write as \(S\), for stay). A deterministic machine has at most one move for each state and symbols, and with \(k = 1\) the definition is the ordinary Turing machine.

Neither extension makes the machine more powerful: every multitape machine has an equivalent single-tape machine, and every nondeterministic machine has an equivalent deterministic one [Sipser, 2012]. What changes is the running time. For a machine that takes \(t(n) \geq n\) steps on inputs of length \(n\):

• a single-tape machine can simulate a multitape one in \(O\left(t(n)^2\right)\) steps;
• a deterministic machine can simulate a nondeterministic one in \(2^{O(t(n))}\) steps.

The quadratic bound cannot be improved in general: a two-tape machine recognizes palindromes in a linear number of steps, while any single-tape machine needs on the order of \(n^2\) steps [Hennie, 1965]. Whether the exponential bound can be brought down to a polynomial one is, in essence, the P versus NP problem. Multiple tapes therefore make machines easier to design, at a cost that is at most quadratic, which is why they are the standard model in complexity theory; nondeterminism is the model behind NP.

Using the MNTM Class

An MNTM is defined like the library's other automata, from its states, input and tape symbols, transitions, initial state, blank symbol and final states, plus the number of tapes. The transitions map each state and the tuple of symbols under the heads to a list of moves, and a list with more than one move makes the machine nondeterministic. The machine below accepts palindromes over \(\{0, 1\}\): it copies the first half of its input onto its second tape, guesses where the middle is, and then reads the second half while walking back over the copy (Figure 2).

from automata.tm.mntm import MNTM

palindromes = MNTM(
    states={"q0", "q1", "q2", "q3"},
    input_symbols={"0", "1"},
    tape_symbols={"0", "1", "$", "#"},
    n_tapes=2,
    transitions={
        "q0": {
            ("0", "#"): [("q1", (("0", "N"), ("$", "R")))],
            ("1", "#"): [("q1", (("1", "N"), ("$", "R")))],
            ("#", "#"): [("q3", (("#", "N"), ("#", "N")))],
        },
        "q1": {
            ("0", "#"): [
                ("q1", (("0", "R"), ("0", "R"))),  # push the 0
                ("q2", (("0", "N"), ("#", "L"))),  # the second half starts here
                ("q2", (("0", "R"), ("#", "L"))),  # this 0 is the middle symbol
            ],
            ("1", "#"): [
                ("q1", (("1", "R"), ("1", "R"))),
                ("q2", (("1", "N"), ("#", "L"))),
                ("q2", (("1", "R"), ("#", "L"))),
            ],
        },
        "q2": {
            ("0", "0"): [("q2", (("0", "R"), ("0", "L")))],
            ("1", "1"): [("q2", (("1", "R"), ("1", "L")))],
            ("#", "$"): [("q3", (("#", "N"), ("$", "N")))],
        },
    },
    initial_state="q0",
    blank_symbol="#",
    final_states={"q3"},
)

The library checks the definition when the machine is created, for example that every transition reads and writes one symbol per tape, and it runs the machine with the same methods as its other automata. read_input_stepwise yields the configurations in the order a breadth-first search visits them, so every branch advances in turn and an accepting branch is found whenever one exists. On 0110, the search visits 17 configurations until the branch that guesses the middle after 01 accepts, and the final configuration prints one line per tape:

palindromes.accepts_input("0110")  # True
palindromes.accepts_input("0111")  # False

(config,) = palindromes.read_input("0110")
config.print()

q3:
> Tape 1: 0110#
              ^
> Tape 2: $01#
          ^

How It Works

Tapes are immutable: every step creates new tapes instead of changing the old ones, so each branch of the search holds its own copy and any configuration can be kept, compared or printed later. A tape grows by one blank cell whenever its head moves past either end. read_input_stepwise keeps a queue of configurations: it takes the next one, yields it and adds one successor for each applicable move. A branch with no applicable move stops there, and it accepts if its state is final; the input is rejected once the queue runs empty. Searching breadth-first rather than depth-first keeps a branch that never halts from blocking the others.

read_input_as_ntm runs the same machine through the single-tape construction from the proof that both models are equivalent [Sipser, 2012]. It writes all the tapes one after another on a single tape, ends each with the separator _ and marks every head with a ^ right after the cell it is on (Figure 3).

Every step of the multitape machine then takes two passes over that tape. The first collects the symbol before each ^, which selects the transition. The second, shown below, rewrites each marked cell and moves its ^ one cell to the right, to the left or not at all. When a head moves onto its tape's separator, a blank cell is inserted before the separator, which is how a tape grows; a real single-tape machine pays for it by shifting everything to the right of that cell. These passes over the whole tape are what makes the single-tape machine quadratically slower.

for move in moves:
    new_head, direction = move
    executing_changes = True

    while executing_changes:
        if new_tape[i] == head_symbol:
            # Update the tape symbol before the head
            new_tape = new_tape[: i - 1] + new_head + new_tape[i:]
            # Remove the old head
            new_tape = new_tape[:i] + "" + new_tape[i + 1 :]

            # Move the head according to direction
            if direction == "R":
                i += 1
            elif direction == "L":
                i -= 1
            # else direction == 'N', i stays the same

            # Handle edge cases with tape separator
            if i > 0 and new_tape[i - 1] == tape_separator_symbol:
                i -= 1
                new_tape = (
                    new_tape[:i]
                    + self.blank_symbol
                    + head_symbol
                    + new_tape[i:]
                )
                i += 1
            else:
                new_tape = new_tape[:i] + head_symbol + new_tape[i:]

        elif new_tape[i] == tape_separator_symbol:
            executing_changes = False

        i += 1

The simulation follows every branch of a nondeterministic machine, as the multitape run does, and the library's tests check that both runs end on the same tapes. On 0110, it starts from the encoded input and ends on the tapes printed above:

run = [config for (config,) in palindromes.read_input_as_ntm("0110")]
for config in (run[0], run[-1]):
    print(config.state, "".join(config.tape.tape))

q0 0^110_#^_
q3 0110#^_$^01#_

One Tape vs. Many

To measure what the second tape buys, two deterministic machines built with the library decide the same language, palindromes over \(\{0, 1\}\) (Figure 4). The single-tape DTM crosses off the first symbol, runs to the end of the input, checks that the last symbol matches, crosses it off and walks back to start again. The two-tape MNTM copies the input onto its second tape, moves the second head back to the start and compares the input read backwards with the copy read forwards.

Each was run with automata-lib 9.2.0 on a palindrome of every length from 0 to 100, counting its steps from read_input_stepwise:

def steps(machine, word):
    return sum(1 for _ in machine.read_input_stepwise(word)) - 1

On a palindrome of length \(n \geq 1\), the single-tape machine takes exactly \((n+1)(n+2)/2\) steps and the two-tape machine \(4n + 3\), which overtakes it at length 6. At length 100 the single-tape machine takes 5,151 steps against 403, almost 13 times as many, and the gap keeps growing with \(n\); by Hennie's bound, no single-tape machine can close it. The two machines are almost the same size, but the two-tape one reads like a program: copy, rewind, compare. The machines, the checks and the code behind every table and figure on this page are in a script in this site's repository.

Perfect Squares

A larger machine decides \(\{0^{n^2} \mid n \geq 1\}\), the strings of 0s whose length is a perfect square. It rests on the identity

so the machine builds the sums 1, 4, 9, … one odd block at a time and compares each with the input. It has three tapes: the input, which starts with a # that marks its left end, a tape of 0s that holds the current sum, and a tape of blocks that alternate between X and Y, the last of which has the current odd length. After each block, the machine compares the tape of 0s with the input (Table 2). If both have the same length, it accepts, and if the tape of 0s is longer, it rejects. Otherwise it writes the next block, two symbols longer than the last, appends as many 0s and compares again. To write a block, it marks the symbols of the last one with S, one at a time, writing a symbol of the other letter for each, then restores the marks and writes two more (Figure 6).

The machine is defined in the library's tests, and as perfect_squares it runs like any other:

perfect_squares.accepts_input("#" + "0" * 9)  # True: 9 = 1 + 3 + 5
perfect_squares.accepts_input("#" + "0" * 10)  # False

Approximate String Matching

Multiple tapes and nondeterminism also make some practical problems short to state as machines. Approximate string matching asks whether a string \(y\) can be obtained from a string \(x\) with at most \(k\) edits, each inserting, deleting or substituting one symbol; the fewest edits that do it is the edit distance between the two. Spell checkers rank their corrections by it, and sequencing tools use it to align DNA reads with a reference genome. The machine below, matcher, answers the question for DNA strings and also returns the edits.

Its input is \(k\) in unary, \(x\) and \(y\), separated by |, such as 11|ACGTACGT|CGTACGTA. It copies the budget onto tape 3 and \(x\) onto tape 2, so that heads 1 and 2 can then walk along \(y\) and \(x\) independently, while tape 4 records the edits. At each step, it chooses one operation: a match (M) when the two symbols agree, which moves both heads, or, while budget is left, a substitution (S), which also moves both heads, a deletion (D) of a symbol of \(x\), which moves head 2 alone, or an insertion (I) of a symbol of \(y\), which moves head 1 alone. Each edit erases one mark from tape 3, and the machine accepts when both strings are used up (Figure 7).

In the machine's definition, this loop builds the transitions of qa:

for budget in "1$":  # head 3 reads an unused edit, or the $ once none is left
    for b in "ACGT#":  # head 1 reads y
        for a in "ACGT#":  # head 2 reads x
            moves = []
            if a == b == "#":  # both strings are used up: accept
                moves.append(("qf", ((b, "N"), (a, "N"), (budget, "N"), ("#", "N"))))
            if a == b != "#":  # match
                moves.append(("qa", ((b, "R"), (a, "R"), (budget, "N"), ("M", "R"))))
            if budget == "1":  # each edit erases one mark from tape 3
                if a != b and "#" not in (a, b):  # substitute
                    moves.append(("qa", ((b, "R"), (a, "R"), ("#", "L"), ("S", "R"))))
                if a != "#":  # delete a symbol of x
                    moves.append(("qa", ((b, "N"), (a, "R"), ("#", "L"), ("D", "R"))))
                if b != "#":  # insert a symbol of y
                    moves.append(("qa", ((b, "R"), (a, "N"), ("#", "L"), ("I", "R"))))
            if moves:
                transitions["qa"][(b, a, budget, "#")] = moves

On the example, the machine accepts with its edits on tape 4: delete the first A, match the next seven symbols and insert an A at the end, which is how a read shifted by one position lines up with its reference.

(config,) = matcher.read_input("11|ACGTACGT|CGTACGTA")
config.print()

qf:
> Tape 1: 11|ACGTACGT|CGTACGTA#
                              ^
> Tape 2: $ACGTACGT#
                   ^
> Tape 3: $###
          ^
> Tape 4: DMMMMMMMI#
                   ^

Running it with \(k = 0, 1, 2, \ldots\) until it accepts finds the edit distance itself. A branch takes at most \(m + n\) steps to align strings of lengths \(m\) and \(n\), so a machine that could guess for free would align them in linear time. The library has to try the branches one after another, though (Table 3). With a budget equal to the edit distance, the search visits fewer configurations than the \((m+1)(n+1)\) cells that the standard dynamic program fills [Wagner & Fischer, 1974], but each extra unit of budget roughly triples it, while the dynamic program does the same work for every \(k\). Nondeterminism makes the problem easy to state; dynamic programming makes it cheap to solve.

Copyright & Credits

© automata was written by Caleb Evans, who maintains it with Eliot W. Robson, and is released under the MIT license. The library is described in [Evans & Robson, 2023] in the Journal of Open Source Software.

For more details, please refer to the project's GitHub repository.