3: Turing machines

Question 1

How do you define a nondeterministic TM?

Answer 1

As a tuple of 7 items (Q, Σ, Γ, δ, q0, qa, qr)
1. Q is a set of states
2. Σ is the input alphabet, not containing the blank symbol, ⏘
3. Γ is the tape alphabet. Must contain at least Σ and ⏘, and usually contains additional symbols too.
4. δ is the transition function, taking the current state and letter in the current cell, and giving the new state, letter to write to the current cell, and movement left or right. δ : (Q \ {qa, qr}) x Γ → P(Q x Γ x {L, R})
P(S) denotes the power set of S; the power set of a set is the set of all subsets of the original set. So this means the transition returns all possible results in a set, since there may now be multiple in number.
5. q0, qa, and qr are the start, accept, and reject states, respectively, where qa ≠ qr

Question 2

How do you define a TM?

Answer 2

As a tuple of 7 items (Q, Σ, Γ, δ, q0, qa, qr)

1. Q is a set of states
2. Σ is the input alphabet, not containing the blank symbol, ⏘
3. Γ is the tape alphabet. Must contain at least Σ and ⏘, and usually contains additional symbols too.
4. δ is the transition function, taking the current state and letter in the current cell, and giving the new state, letter to write to the current cell, and movement left or right. δ : (Q \ {qa, qr}) x Γ → Q x Γ x {L, R}
5. q0, qa, and qr are the start, accept, and reject states, respectively, where qa ≠ qr

Question 3

What is a TM capable of?

Answer 3

A hypothetical model of a machine that can recognise languages that are not (only) context-free and can produce output as well as accepting or rejecting inputs/ It is, therefore, more powerful than a PDA and has more sophisticated memory than a simple stack.

Question 4

How does a TM work?

Answer 4

Given an initial input on a tape, with tape head over first cell in tape and starting at start state. Repeatedly find next state and letter with transition function from current cell and current state to writing a symbol to the current cell, moving tape hear left or right and then moving into a resultant state as part of the transition. The TM can loop infinitely or halt. If it halts in an accepting state, the TM accepts; else, if it halts in a non-accepting state or has no transition mapping for the current state and letter at any point, the TM rejects.

Question 5

How are TMs similar to and different from DFAs and PDAs?

Answer 5

Similarities with DFAs and PDAs
1. The current tape symbol g ∈ Γ is like an input symbol: just like for a DFA, the combination of it and the current state q ∈ Q completely determine what happens next.
2. The input word is the initial word on the tape.
3. The state set Q is finite and contains a single start state q0.
4. The input alphabet Σ is finite.
5. The tape alphabet, Γ, is like the stack alphabet of a PDA, except that it must contain both the input alphabet, Σ, and the ‘blank’ symbol, ⏘.
6. The TM can’t tell when it is at the leftmost end of the tape, just as a PDA can’t tell when the stack is empty. Similarly to pushing $ onto the stack at the beginning of running a PDA, each Turing machine generally starts by marking the first cell, so that it can be identified later.
Differences with DFAs and PDAs
1. Unlike a DFA, a Turing machine can write on the tape, instead of just reading input.
Unlike a PDA, a Turing machine can write anywhere on its tape, once it has moved the read/write head to the desired cell. At each step, a Turing machine must move one cell left or one cell right, unless the read/write head
is at the left-most end, when a “move left” instruction results in staying put.
2. There is a single accept state, qa, and a single reject state, qr, and TMs stop as soon as one of these is entered.

Question 6

What is a TM configuration?

Answer 6

The condition of a TM at any 1 particular time. It is constituted of the state of the machine, the contents of the tape of the TM, and the position of the tape head.

Question 7

How do you define TM configurations?

Answer 7

A word consisting of all the symbols in the tape before the current cell the tape head is pointing to; current state; the tape symbols fro and after the current cell.

Question 8

Consider 2 finite alphabets, A and B, where A ⊂ B and ⏘ ∈ B \ A : A is a proper subset of B and the blank symbol is in B and not in A.
Prove that:
a) There exists a TM that on input w ∈ A* will halt with ww on the tape.
b) For any word u ∈ B, there exists a TM on input w ∈ A that will halt with uw on the tape.

Answer 8

??

Question 9

How do tapes on TMs work?

Answer 9

End at the left side, from which tape is infinite: half-infinite. Consists of symbols or letters in cells. A tape head marks the current symbol. The transition function of the TM describes what to do for each symbol at current cell (cell pointed to by tape head); writes a new letter to the current cell, tape head moves left/right (if at left and end and left move don’t move), and TM goes to a new state.

Question 10

How can you define a TM with tables?

Answer 10

Construct a table of current states against possible inputs; each cell represents a certain symbol being read in a certain state and will describe what to write to the tape, how to move the tape head, and the new state to transition to.

Question 11

True/false: Consider 2 finite alphabets, A and B, where A ⊂ B and ⏘ ∈ B \ A : A is a proper subset of B and the blank symbol is in B and not in A.

a) There exists a TM that on input w ∈ A* will halt with ww on the tape.
b) For any word u ∈ B, there exists a TM on input w ∈ A that will halt with uw on the tape.

Answer 11

True

Question 12

What does A−B mean (give), given that A and B are sets? How is this sometimes alternatively notated?

Answer 12

The difference between sets A and B: returns items in set A that are not in set B. Sometimes notated as A \ B.

Question 13

What is a multi-tape TM?

Answer 13

A TM in which there are multiple tapes and the transition function uses the symbol in the current cell of each (or multiple) cells as input as opposed to just from one tape. One immutable tape is sometimes reserved to just hold input. All tapes share the same tape alphabet (apart from when there’s a dedicated input tape which will take the input alphabet).

Question 14

How do you define a multi-tape TM?

Answer 14

As a tuple of 7 items (Q, Σ, Γ, δ, q0, qa, qr)

1. Q is a set of states
2. Σ is the input alphabet, not containing the blank symbol, ⏘
3. Γ is the tape alphabet. Must contain at least Σ and ⏘, and usually contains additional symbols too.
4. δ is the transition function, taking the current state and letter in the current cell, and giving the new state, letter to write to the current cell, and movement left or right. δ : (Q \ {qa, qr}) x Γ1 x Γ2 .. Γk → Q x Γ1 x Γ2 .. Γk x {L, R}, where there are k tapes
5. q0, qa, and qr are the start, accept, and reject states, respectively, where qa ≠ qr

Question 15

True/false: for every multi-tape TM, there is an equivalent single-tape TM.

Answer 15

True

Question 16

Prove that for every multi-tape TM, there is an equivalent single-tape TM.

Answer 16

We design a single tape Turing machine S with L(S) = L(M). Let k be the number of tapes of M. Then S simulates the k tapes by storing their information on its single tape.
The input alphabet of S is ΣM. The tape alphabet ΓS of S contains ΓM, but will also contain some new symbols. The TM S uses a new symbol, say $ ∉ ΓM, for the very first cell on the tape. It also uses a new symbol, say # ∉ ΓM, to mark the end of the used portion of each of the k tapes. For each a ∈ ΓM, the alphabet ΓS contains both a and a. The s will be used to indicate where each of the k read/write heads of M are at each step.
On input w = w1 … wn, the machine S starts by setting up its tape to simulate all k tapes of M. That is, using the ideas from Lemma 2.1, S modifies the tape so
it contains $w1 w2 … wn # ⏘ # ⏘* # ⏘* … ⏘* # ⏘ ⏘ … with k # signs.
To simulate a single move of M, the TM S reads the tape from the $ to the final #. It goes into a state which depends on the k-tuple of letters that were marked with *s, which is possible since there are only |ΓM| ^ k possible such tuples. It then goes back to the beginning of the tape, and goes through the current word a second time, updating the ith part of the tape according to how δM tells M to act on tape i: it replaces the symbol with a * by whatever M writes there, and puts a * either one cell left or one cell right.
If at any point during this update S moves one of the imaginary read/write heads, say head i, to the right onto a #, this means that M would be moving read/write head i onto a new blank cell of tape i. So, as in Lemma 2.1, S copies all of the rest of the tape one cell further down, to free up a blank cell. Then it continues the simulation as before.

Question 17

What is a nondeterministic TM?

Answer 17

A variant of Turing machines in which the TM can be thought of as being in multiple states simultaneously in different branches of computation that are created at each transition. A nondeterministic TM will accept if at least one of its branches does, otherwise rejecting or looping.

Question 18

What is a certificate?

Answer 18

“A certificate is a deterministically machine-checkable proof that a given input is accepted in a non-deterministic Turing machine”

A word within a set representing all possible configurations of a non-deterministic TM in a deterministic TM that is equivalent to a precomputed branch of computation in the non-deterministic TM in which the current input is accepted (so now it is in the deterministic TM too).

Question 19

True/false: there is not a deterministic TM equivalent to every nondeterministic TM.

Answer 19

False. For each nondeterministic TM there is an equivalent deterministic TM.

Question 20

Prove that for each nondeterministic TM there is an equivalent deterministic TM.

Answer 20

We design a deterministic Turing machine D with L(D) = L(N). To make things easier, we allow D to have three tapes; by Theorem 2.3, the TM D is equivalent to a single-tape machine.
Each output of δN is a subset of QN x ΓN x {L, R}. Order the triples in QN x ΓN x {L, R} (in any way you like), and let b = 2|QN||ΓN | = |QN x ΓN x {L, R}|.
We will describe each possible sequence of configurations that N can produce (and some that it can’t) as a word in {1,…,b}, as follows. A word c = c1 c2 … cm ∈ {1,…,b} means that at step i, we consider the branch of N’s computation given the cith triple from the set of triples returned by δN (using our fixed ordering on
the triples). Whilst working with c, we stop considering these configurations after at most m of them, even if the corresponding state of N is not a halting state:
• If N reaches a halting state before cm then this branch stops when N halts.
• Some words c = c1 … cm ∈ {1,…,b}* may not describe valid computations (for example, we might have c1 = 3, but, in fact, on input w = w1 w2 we find that δN (q0, w1) is a set of size two).
If so, then we ignore the part of c after the last valid step. The empty word corresponds to considering only the start configuration.
The machine D works as follows. Tape 1 holds the input word w, and never changes (except for any marks we need to copy w to other tapes). Tape 2 records N’s tape on the current branch of its nondeterministic computation, with an “end of word” symbol at the end so we can easily erase the tape afterwards. Tape 3 records which branch of N’s nondeterministic computations is currently being explored by D. Tape 3 only uses the symbols in {1, . . . , b, ⏘}. Initially, tapes 2 and 3 contain the empty word.
D repeatedly carries out the following 3 steps:
1. Copy the input word, w, from Tape 1 to Tape 2. Put a symbol to mark the end of the used portion of Tape 2.
2. Use Tape 2 to simulate N with input w on the branch of N’s nondeterministic computation given by the word c = c1 … cm on Tape 3. That is, for i = 1, … ,m do the following:
(a) Find the set T of triples returned by δN at the ith step of N’s calculations.
(b) If ci > |T|, then go to Step 3.
(c) Let (q, x, D) ∈ QN x ΓN x {L, R} be the cith triple returned by δN. Then:
i. If q = qa then accept.
ii. If q = qr then go to Step 3.
iii. Otherwise, do to Tape 2 whatever N would do at this point, according to (q, x, D). Move the end of word symbol one cell down along Tape 2 if necessary.
3. Replace the word c on Tape 3 with the len-lex next word in {1,…,b}* (see Tutorial Sheet 2 for how to do this). Erase Tape 2. Go to Step 1.

Question 21

Why are certificates used?

Answer 21

Used for problems not solvable in poly time in deterministic TMs (=> computers). So precompute results and retrieve to be able to run in poly time on deterministic TMs (again computers), sort of like a HashMap.

Question 22

What does it mean for 2 Turing machines to be equivalent?

Answer 22

We say that a Turing machine M1 is equivalent to a Turing machine M2 if L(M1) = L(M2).