ITEC 420 - Section 3.2 - Variants of Turing Machines

Main Results

• Theorem 3.13: Every multitape Turing machine has an equivalent single-tape Turing machine.


• Theorem 3.16: Every nondeterministic Turing machine has an equivalent deterministic Turing machine.


• Theorem 3.21: A language is Turing-Recognizable IFF some enumerator enumerates it.

Proof Idea for Theorem 3.13

• Theorem 3.13: Every multitape Turing machine has an equivalent single-tape Turing machine.


• Simulate an n-tape machine using a one tape machine:
• Store information on all tapes on the single tape.


• Separate information from different tapes using a new symbol (eg #)


• Use a dotted symbol to represent the location of each tape head
• When the tape head moves to a location, replace the symbol there (eg symbol x) with the equivalent dotted symbol (ie with dotted x)
• When the tape head moves from a location, write a regular (ie non-dotted) symbol at that location
• Requires adding dotted symbols to tape alphabet


• Develop new transition function:
• A step of the n-tape machine will represent steps on all n of the parts of the single tape
• A right movement onto the # results in shifting to the right one symbol all of the symbols that are to the right of the #

Theorem 3.16

• Theorem 3.16: Every nondeterministic Turing machine, N, has an equivalent deterministic Turing machine.


• Transition function for N: δ: Q x Γ → P(Q x Γ x {L,R})


• Machine N accepts w if some branch accepts w

Theorem 3.16: How to Prove?

• Remember: How did we prove DFA and NFA were equivalent:
• Defined an algorithm for creating a DFA that is equivalent to an given NFA
• The states of the DFA were powersets of the NFA states
• The DFA accepted the same strings as the NFA


• How to prove that a Nondeterministic TM has an equivalent deterministic TM?
• Answer: Create a deterministic TM that executes possible computations on the nondeterministic TM

Executing Possible Computations on the Nondeterministic Turing Machine

• Basic Approach:
• Specify possible nondeterminisitc choices made by the NTM


• Continue trying more and more choices
• If the NTM accepts, the DTM will find the accepting computation
• If the NTM rejects, the DTM continues forever, looking for an accepting computation
• If the NTM loops, the DTM will continuing trying computations forever

Representing a Nondeterministic Choices

• Assume that the largest number of choices at any point in the machine is b


• Let Σ_b = {1, 2, ..., b}


• Represent a sequence of n choices with a string from Σ_b of length n


• Example: 534 represents taking choice 5, then the choice 3, then choice 4

Theorem 3.16 Proof: Simulating a Nondeterministic Machine

• : Simulate the nondeterministic machine N with a 3-tape deterministic machine D:


1. Tape 1 of D is initialized with a copy of the input tape for N and never changes after initialization.


2. Tape 2 of D has a copy of what N's tape would be at that point of the computation that is currently specified by tape 3


3. Tape 3 of D successively contains a sequence of numbers that represent every possible path through N.
• Each path represents (part of) a computation in N
• Each number represents a choice at a nondeterministic branch in the ocmputation
• Tape 3 successively contains the numbers in lexicographic order (ie in alphabetic order, shortest first)
• Example: if b=4 (ie 4 is the maximum number of choices), then tape 3 would hold 1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44, 111, ..., 114, 121, 122, 123, 124, ..., 443, 444, 1111, ...

Algorithm for Theorem 3.16: Simulate N on D

1. Intialize Tape 1.


2. Initialize Tape 3 with the number for the first possible computation N


3. Loop
1. Copy Tape 1 to Tape 2


2. Execute N using Tape 2 as input and following the computation choices specified in Tape 3
1. If sequences of choices represents an accepting computation for N (ie N enters an Accept state), then D halts and accepts
2. Else (ie a number represents an infeasible or rejecting computation) continue with the next step


3. Initialize Tape 3 with the string that represents the next possible sequence of choices of N


4. Repeat loop

N and D are Equivalent

• N and D accept the same language


• That is, N accepts L iff D accepts L


• If N accepts w, then D will accept w.


• If N rejects or loops on w, then D will ...

Avoiding Looping

• Can we avoid looping in D?


• If N always accepts or rejects every string, then D can be modified to accept or reject every string


• If N loops on some strings, then D will loop on the strings on which N rejects or loops

Deciders and Recognizers

• If machine M always halts for strings in and out of the language, then M is called a Decider


• If machine M is not guaranteed to halt, then M is called a Recognizer

STOP HERE

• Fall 2010 we will skip enumerators

Enumerators

• An enumerator provides a different way of using a TM to define a language


• Think of an enumerator as a TM with a printer attached
• As the TM runs, it prints strings on the printer
• The printed strings are the language defined by the machine
• The TM starts with a blank tape (since it is does not define a language by accepting input strings)

Theorem 3.21

• Theorem 3.21: A language is Turing-Recognizable IFF some enumerator enumerates it.

Proof Idea for Theorem 3.21

• We must show that enumerator E enumerates language L iff some TM M recognizes L


• Part 1: If enumerator E enumerates language L then there exists TM M that recognizes L
• Use E to define TM M as follows: For input w
• examine each strings enumerated by E
• if w appears, then accept w
• Every string printed by E will be accepted by M
• Strings not printed by E ...


• Part 2: If TM M recognizes language L then there exists an enumerator E that enumerates language L
• Use M to define enumerator E as follows:
• Assume that E prints strings s1, s2, ... si
• For i in 1 ...
• Run M for i steps on strings s1, s2, ... si
• If M enters an accept state, print it
• Every string in L will be printed ?? many times
• Strings not not in L ...