Lec 22: Turing Machine Variants & Cook's Theorem Setup - CSCI 381 - Goldberg

Administrative Updates

Same as that of Lecture 20.

Finite State Automata

An automaton (machine) is a weighted graph. Machine $M$ is over an alphabet $\Sigma$ and is a weighted graph:

M = (V, E, w)

$V$ (vertices) are called States, generally described as $Q$
$E$ (edges) are called Transitions
$w: E \to \Sigma$ - The “weights” associated with each edge are the letters in the string that allow the machine to go from one state to another.
Start State: $Q_0 \in Q$ - All processing starts here.
Final States: Subset $F \subseteq Q$ $F \subseteq Q$ - For a string to be accepted by the machine, the processing must end in a final state.
- Note: Subsets can be empty, so it is possible that a given automaton does not have any final states.

The language of the machine $L(M)$ consists of any strings (over alphabet $\Sigma$ ) that, when starting in the start state $Q_0$ and processing each character of the string according to the “rules” embedded in the weights associated with the transitions (edges), the machine will end up in a final state.

More formally, a machine (automaton) is defined as:

M = (Q, \delta, \Sigma)

$Q$ - States (Vertices)
$\delta$ $δ$ (delta) - Transition function - specifies edges called transitions
- $\delta: Q \times \Sigma \to Q$
$\Sigma$ - Alphabet / Tokens (letters or characters) - weights of the transitions/edges

DFA Example

Consider the following DFA:

$Q$ (States): $\{Q_0, Q_1, Q_2, Q_3\}$
$\Sigma$ (Alphabet): $\{a, b, c\}$
$q_0$ (Start state): $Q_0$
$F$ (Accepting states): $\{Q_2\}$

From	Token	To
$Q_0$	$a$	$Q_1$
$Q_0$	$b$	$Q_3$
$Q_0$	$c$	$Q_2$
$Q_1$	$b$	$Q_0$
$Q_2$	$a$	$Q_0$
$Q_2$	$c$	$Q_1$
$Q_3$	$b$	$Q_1$
$Q_3$	$c$	$Q_2$

$LaTeX diagram$

Processing examples:

ababbcc

Q_0 \xrightarrow{a} Q_1 \xrightarrow{b} Q_0 \xrightarrow{a} Q_1 \xrightarrow{b} Q_0 \xrightarrow{b} Q_3 \xrightarrow{c} \boxed{Q_2} \xrightarrow{c} Q_1

Reject since $Q_1$ is not a final state; the issue of “final” state is only relevant after the complete processing (parsing) of the input string.

ababbc

Q_0 \xrightarrow{a} Q_1 \xrightarrow{b} Q_0 \xrightarrow{a} Q_1 \xrightarrow{b} Q_0 \xrightarrow{b} Q_3 \xrightarrow{c} \boxed{Q_2}

Accept since $Q_2$ is a final state.

bcb

Q_0 \xrightarrow{b} Q_3 \xrightarrow{c} Q_2 \xrightarrow{b} \text{?}

State $Q_2$ with input " $b$ " is not defined (cf. partial nondeterminism); reject even though $Q_2$ is final. cf. Tom Hanks in The Terminal.

Notes and conventions about strings processed by an automaton (machine):

States are vertices and conventionally labeled as $Q$ .
The machine always starts in a specific state (node) termed the start state,
and this state is identified by a ”>” marker next to it.
Conventionally, the start state is labeled $Q_0$ .
The states of this machine are given a status as to whether the state is a final (accepting) state or a nonfinal (rejecting) state. This status is significant when processing a string, determining whether or not the inputted string is a member of the language accepted by this machine (detailed next). Please note that checking whether a state is non/final is ONLY done AFTER processing the entire string.
The processing of an input string $S = S_1 \cdot S_2 \cdots S_n$ (where $S_i$ are alphabet characters and dot is the concatenation operator which simply indicates which character follows in sequence after another character) is based on which state the machine ends up in when following the transitions (edges) of this graph following the characters, one by one, from state to state.
If the machine ends up in a final state, the string is processed and accepted as a word (member) of the language of this machine $L(M)$ . If the machine ends up in a nonfinal state, then the machine rejects (not accepting) this string and does not consider it a member of its language. The rules that govern which state you enter into after exiting a current state because of an inputted character is user-defined by the state transition function $\delta$ . If not defined, then the string is automatically rejected.
This above diagram (purposely) deviates from the typical example that will be first explained in an automata course in the following manner: The alphabet for this machine seems to be $\{a, b, c\}$ since those are the only letters used as weights for the edges. (Character weights on edges are called Tokens.) PRESUMABLY, for each state, the diagram should state (i.e., an edge should exist) for each letter. Yet, for example, $Q_1$ with a token “a” or “c” to be processed does not specify what would happen (i.e., no weighted edge with “a” or “c” exits from state $Q_1$ ). Likewise, no edge exits state $Q_3$ with the letter “a” etc. What does the machine do when it is in a state and the input is a letter that no information (no edge) is provided to tell the machine what to do? The machine simply stops the processing immediately and thereby summarily rejects the entire string. This would be the case EVEN IF the state we are currently in is a Final State. It still will reject the string because it could not effectively process the entire string.
If $Q_0$ with input token “a” had two choices, for example to go to $Q_1$ (as is now) and also to $Q_2$ (which isn’t here), then which state does it go to? One of the two, Both, or None? The answer to this question is based on the concept of “nondeterminism” to determine which is the best pathway to pursue.

Chomsky Hierarchy & Machine Variants

Noam Chomsky (1965) identified four levels of computable languages (not including the Unsolvable/Noncomputable level; although not included in the Chomsky Hierarchy, some textbooks include them as an outermost ring and call them type -1):

$LaTeX diagram$

Type	Name	Machine	Auxiliary Memory	Other Actions	D vs. N
3	Regular	Finite State Automata	None	None	$D = N$
2	Context-Free	Push Down Automata	Stack	Push/Pop	$D \subsetneq N$
1	Context-Sensitive	Linear Bounded Automata	Tape, linear in length	Left/Right/Print	$D \mathrel{?} N$
0	Unrestricted	Turing Machines	Infinite Length Tape	Left/Right/Print	$D = N$

The previous sections describe the essential automata/machine that is at the core of each of the above machines.

Potentially, there can be an additional alphabet (termed output alphabet) for the memory storage, separate from the input alphabet. This is most pronounced for PDA. Thus:

\text{PDA} = (Q, \Sigma, \Gamma, \delta, q_0, F)

where $Q$ , $\Sigma$ , $\delta$ , $q_0$ , $F$ have all been defined by finite state automata, and additionally $\Gamma$ is the stack alphabet - the characters that will be pushed/popped from the stack during the transitions. The stack alphabet can be the input alphabet as well.

Both Context-Sensitive and Unrestricted use a tape, and when using tapes, the input and output are what are on the tape. Thus, for these automata, $\Gamma$ is not a special alphabet but the input alphabet. However, there is a need for $\Gamma$ to contain one or more extra symbols termed markers:

A special blank symbol (not $\lambda$ , the empty string) to indicate that the current tape cell does not contain an alphabet letter. This is the case when purchasing a new tape, for example.
Extra marker symbols which can be used to organize the data better on the tape (Davis tends to avoid using these; Cook uses this extra marker in his paper). A simple example would be if the input/output contained multiple data values - it would be easier to identify the start and end of a given data value storage if it was delimited by special marker symbols: #Input1#Input2#...#Inputn# and likewise #Output1#Output2#...#Outputn#

Although the last machine (Turing machine) has an infinite amount of memory available, one cannot actually use the “infiniteness” of that memory, since that would require an infinite loop, which goes against Turing’s notion of an “effective” computation - the machine MUST halt (stop) before giving any output.

When we say “computer”, the computation model actually used in all of classic computer theory is that of the Turing machine. The Turing machine is an automaton that has an alphabet $\Sigma$ and a graph-based machine termed the transition graph, or stored in a transition table (similar to an adjacency matrix for weighted graphs). The nodes/vertices of this graph/automaton are called States and the arcs/edges are called Transitions. The machine has an auxiliary tape (infinite in both directions) that the input is read from, the processing scans and reads from, and the output is printed to.

The Turing machine is comprised of two components: the state diagram including the transitions, and a separate memory storage device (the “tape”). The state diagram portion is the exact same weighted graph that exists at all levels of languages in the Chomsky Hierarchy. The Hierarchy has the Regular languages at the lowest level and then Context-Free, Context-Sensitive, and Unrestricted. The lowest level (Regular) can be processed by a finite state automaton - precisely the weighted graph we are referring to. What it does not have is memory to store values such as which state the current transition came from and which letter was just processed to get to the current state. This same machine is identical for each machine that processes the higher levels of language as well; the difference between the machines is whether and to what extent there is a separate memory storage.

The finite state automata (for regular languages) does not have a memory storage.
The Pushdown Automata (PDA) that processes Context-Free languages has a single stack as a memory storage.
The Linear Bounded Automata that processes Context-Sensitive languages have a tape as a memory storage, but this tape is “linearly bounded” in size so that the amount of storage on the tape is $O(n)$ where $n$ is the length of the original input.
The Turing machine processes all computable languages and processes the highest level (and therefore certainly the lower levels) of languages. The Turing machine has a tape, infinite in length in both directions, providing as much memory as necessary to process any computable language.

Regarding the state transition graph component of these machines, we only discussed a single variant - deterministic versus nondeterministic: at the lowest (regular) and highest (unrestricted computable) levels of language, deterministic machines solve the exact same languages as their nondeterministic alternatives. Nondeterministic PDA actually process more Context-Free languages than deterministic PDA. For Context-Sensitive languages, it is unknown whether or not nondeterministic linear bounded automata process more languages than their deterministic alternatives. This is all regarding the state transition graph. What about variations in the memory storage?

We will now explore a number of variants of the Turing machine tapes; Martin Davis proves for each such variant that they all compute the same algorithms as the original Turing machine version without the variations. An interesting memory storage variation exists for the Pushdown Automata. Recall that the PDA is a state transition graph with a single extra stack as a memory storage. What if we added one more stack and could independently interact with two stacks? Martin Davis proves that a Pushdown Automata that has two stacks (instead of the one provided by definition of a PDA) is actually equivalent to a Turing Machine!

Push/Popping can simulate moving the tape left/right, and similarly simulate printing. The intuition is that the two stacks represent the left and right halves of a single tape, with the tops of the stacks meeting at the current scanhead position. Moving the scanhead left corresponds to popping from the left stack and pushing onto the right stack, and vice versa for moving right. Printing (overwriting the current cell) is simulated by popping the top symbol off one stack and pushing a new symbol in its place.

Cook-Levin Theorem

Cook (1971) proved that ALL NP-complete problems reduce to Satisfiability. (cf. Karp, who had to prove reductions from Satisfiability and its descendants one by one.) Satisfiability is finding values for the variables involved in a Boolean Predicate that cause the Predicate to evaluate to TRUE on those values. This should sound like “checking a checklist” - verifying that all the conditions have been met. Any nondeterministic program first “guesses” the (correct) solution, but we need to manually verify that the “guessed” solution is TRUE. For NP, this verification process must be computed in a deterministic polynomial amount of time. As long as you have a correct verification procedure for a specific NP-Complete problem, then Satisfiability solves the other problem for you by “guessing” values that will make the verification procedure evaluate to TRUE.

To specify the classic Turing machine, you need to provide a set of rules that govern the transitions of this machine. Originally in the following format:

\langle Q_i,\ A_j,\ \{\text{Left},\ \text{Right},\ \text{Print } A_k\},\ Q_m \rangle \quad \leftarrow \quad \delta \text{ (Transition function)}

The standard $\delta$ transition function is embedded in this quadruple $\langle Q_i, A_j, \{\text{Left}, \text{Right}, \text{Print } A_k\}, Q_m \rangle$ . Since this has four pieces of information, the machine is called a Quadruple Turing Machine:

“If you are in state $Q_i$ and the scanhead pointer is reading from the tape the symbol $A_j$ , then the tape should (either move Left, Right, or print over the symbol $A_j$ with the symbol $A_k$ , all of these depending on how the user defined this rule), and then transition (move) to state $Q_m$ .”

There are other variations of Turing machines that are equally powerful in terms of computability to the original Quadruple Turing machine:

Quintuple Turing Machine: $\langle Q_i, A_j, \text{Print } A_k, \{\text{Left}, \text{Right}\}, Q_m \rangle$ - For the application of each rule, you MUST print and then you MUST move the tape.
One-directional infinite tape: Instead of a tape that is infinite in both directions, use a tape that is infinite in only one direction. There is a definitive index $0$ for the tape; if infinite in two directions there is no index $0$ per se since there cannot be negative indices.
Two-dimensional tape: The tape is two-dimensional and infinite in both dimensions and in all directions (cf. the “professor” in the cartoon Tennessee Tuxedo And His Tales who had such a board to write equations on; analogy is an Excel Worksheet with an infinite number of rows and columns).
Multi-track tape: A tape that allows storing $t$ symbols in any one spot, one in each of the $t$ tracks, and therefore requires $t$ heads to read all of these characters together when scanning the current spot.
Multi-tape machine: A machine with multiple infinite tapes and a scanhead pointer for each tape.

Cook’s proof would be simpler if we used a combination of Variant 1 (quintuple) and Variant 2 (infinite in one direction only). cf. Cook’s original proof, which has no diagrams and relies completely on mathematical notation to represent the tape. The scanhead pointer was simulated by inserting the letter $h$ in the middle of the string representing the tape (on the assumption that $h \notin \Sigma$ ). Likewise, he would have to insert a marker representing the current state. We will store them in separate columns and not with the tape.

To understand what Cook’s proof needs to verify, think of it as “playing computer” - manually simulating the Turing machine’s full execution step by step and recording the complete machine state at each clock cycle in a table. Each row below is a copy of what is on the tape at time $t$ :

Time	Scanhead Pos.	State	Tape Cell $1^{**}$	Tape Cell $2$	$\cdots$	Tape Cell $\text{poly}(n)^{***}$
$0$	$1$	$Q_0$	Input loaded here	$\cdots$	(blank)	(blank)
$1$
$2$			Each row contains the characters printed
$\vdots$
$\text{poly}(n)^*$	$1$	$Q_f$	Output printed here	$\cdots$	(blank)	(blank)

At $t = 0$ : the input is stored at the beginning of the tape; the rest of the tape is blank (Davis convention). At $t = \text{poly}(n)$ : the output is the only content remaining, at the beginning of the tape (Davis convention).

The tape cell indexing starts at $1$ (first cell location); $0$ is reserved for the empty tape. Davis calls a snapshot $(i, \sigma)$ where $i$ is the clock cycle (TIME) and $\sigma$ is the data values of all active memory cells (SPACE), with all inactive cells assumed to be blank. In essence, each row is a Davis snapshot.

Table notes:

$^*$ The number of rows will not be more than $\text{poly}(n)$ since the problems under discussion are NP-Complete, which MUST compute in a polynomial amount of time.
$^{**}$ The reason we can start the first column definitively as “Tape Cell $1$ ” is that we are assuming Variant 2 - the tape is finite on one side and infinite in the other direction.
$^{***}$ The reason we only have to consider $\text{poly}(n)$ cells in Cook’s simulation is that we assumed Variant 1 (the quintuple machine), which can only advance one cell at a time per clock cycle, and NP has at most $\text{poly}(n)$ cycles for time.

(This diagram table is similar to the diagram found in the Wikipedia article on Cook’s theorem.)

Cook also realized these last three points and did so using the original quadruple Turing machine, but we are using the equivalent Turing machine variants to make the proof easier. According to Variant 1, the quintuple machine must move Left/Right at each step of the processing. Since the processing only has $\text{poly}(n)$ amount of time, the machine can move at most $\text{poly}(n)$ cells to the right. Thus, only a $\text{poly}(n)$ number of columns are in the table. Based on this, the table above only requires a $\text{poly}(n)$ amount of space, since there are $\text{poly}(n)+1$ rows (time) and $\text{poly}(n)+3$ columns (tape), and $\text{poly} \cdot \text{poly} = \text{poly}$ .

Consider the row for time $t = 0$ . This is the status of the machine before processing begins. The input is loaded onto the beginning of the tape (the rest is blank by default). The scanhead pointer is set to position $1$ and the initial state is $Q_0$ . Some of the states are designated final states and Turing machine processing must end in one of these. In the above table, " $Q_f$ " appears as the state at the end of processing - this is not necessarily one state; it can be any number of states with the $Q_f$ designated final status. Turing had a convention that when processing is completed, ONLY the output appears on the tape (at the beginning) and the scanhead pointer points to the beginning of the output. The rest of the tape at the end of processing is blank (similar to when the processing starts).

If the nondeterministic Turing machine solved a given NP-Complete problem (such as Job Scheduling), then the above table has ALL the information you would need to understand how that Turing machine processed the input data and obtained the output. How can we verify that the above table documented the correct pathway to obtain a solution?

To verify the initial and final rows is straightforward. The user placed the input, and the solution is by definition whatever is on the tape when the machine enters and remains on a final state. The question is how to verify the rows in between - to verify that given a row at time $i$ , the row at time $i+1$ follows according to the rules of the nondeterministic Turing machine. Equally important is that this verification occurs in a reasonable amount of time. In fact, the transition from row to row can be verified in a linear amount of time. The key to understanding this is that since the Turing machine interacts with one cell per time step, the change from one row to the next is VERY LITTLE.

Consider the tape at times $i$ and $i+1$ . The scanhead position at time $i$ is $j$ . The quintuple machine could only move at most one cell from the current position entering into time $i+1$ . Thus, the window of possible change in tape from time $i$ to time $i+1$ consists of at most 6 cells (cells $j-1$ , $j$ , and $j+1$ across both rows $i$ and $i+1$ ). But it is even simpler than that. Because we are assuming a quintuple machine, the printing of a symbol occurs BEFORE the moving of the scanhead. Therefore, if there is ANY change, it must occur in one place only - at scanhead position $j$ , which can have a different symbol in row $i+1$ than in row $i$ . ALL OTHER SYMBOLS on the tapes for rows $i$ and $i+1$ must be IDENTICAL. To verify this only requires $O(\text{poly}(n))$ time since, as proved above, the table only requires $\text{poly}(n)$ columns for the tape portion.

If $(Q_i, S_k) \to Q_m$ :

$S_k$ may be overwritten with $S'_k$
scanhead moves to $j \pm 1$

All other cells: identical between rows $i$ and $i+1$

$LaTeX diagram$

So, a nondeterministic Turing machine “guesses” what should be in every square in the above table ( $\text{poly}(n)$ “guesses”). Due to nondeterminism, this machine “guesses” correctly, but you need to verify in $\text{poly}(n)$ amount of time. There are only a $\text{poly}(n)$ number of things to check to make sure that the table is consistent with a Turing machine and that each row follows directly from the previous row according to the transition rules. See the Cook-Levin theorem proof on Wikipedia for the exact boolean checklist needed to verify this. This reference indicates that encoding of the Turing machine into a Boolean Predicate requires $O(\log(\text{poly}(n)) \cdot \text{poly}(n)^3)$ time. Further research has shown that one could encode it into an equivalent Boolean Predicate in only $O(\log(\text{poly}(n)) \cdot \text{poly}(n))$ time.

The above table would also be a proof for Savitch’s Theorem (1970) that $\text{NSPACE}(f(n)) \subseteq \text{DSPACE}(f(n)^2)$ , at least for any $f(n) \geq n$ . (Savitch’s own proof extended $f(n)$ to be $\geq \log(n)$ in size.) What is $\text{SPACE}(f(n))$ ? It is the set of all problems that can be solved using memory of size $O(f(n))$ regardless of how much time it takes. $\text{DSPACE}$ says the problems are solved deterministically and $\text{NSPACE}$ means they are solved nondeterministically. Regardless, the above table is size $f(n) \times f(n)$ (or $f(n)^2$ ), and since the quintuple Turing machine must print one cell at a time per clock step, the maximum space required by any given row is $f(n)$ . Any row is representative of a nondeterministic Turing machine step and if one could “guess” the correct value for each cell, then the table as a whole gives a Turing algorithm for solving the problem. Now, since $\text{NSPACE}$ / $\text{DSPACE}$ does NOT care about time, one can brute-force fill in the table by deterministically considering every possible filling of the table (there are exponentially many - up to $|\Sigma|^{f(n)^2}$ possible fillings - but since $\text{NSPACE}$ / $\text{DSPACE}$ does not care about time, this is acceptable) until a valid filling is found: one where the initial row has the correct input, the last row has the correct output, and each row is consistent with the previous/next row according to the rules of the nondeterministic Turing machine. Thus, this table implements $\text{NSPACE}(f(n))$ and can be simulated by $\text{DSPACE}(f(n)^2)$ , at least for any $f(n) \geq n$ .

Having discussed nondeterministic space, a second theorem is worthwhile to mention. The Immerman-Szelepcsényi theorem (1987, for which they shared the Gödel Prize in 1995) states that nondeterministic space complexity classes are closed under complementation. (Recall we have previously pointed out that knowing who is a member can be easier to determine than who is not a member.) They actually proved this independently. Mathematically, the theorem states that:

\text{NSPACE}(s(n)) = \text{co-NSPACE}(s(n)) \quad \text{for any function } s(n) \geq \log n

A specific case of this theorem (when $s(n) = \log n$ ) is that $\text{NL} = \text{co-NL}$ , where $\text{NL} = \text{NSPACE}(\log(n))$ and $\text{co-NL}$ is its complement.