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:
- Tape 1 of D is initialized with a copy of the input tape for
N and never changes after initialization.
- 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
- 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
- Intialize Tape 1.
- Initialize Tape 3 with the number for the first possible computation N
- Loop
- Copy Tape 1 to Tape 2
- Execute N using Tape 2 as input and
following the computation choices specified in Tape 3
- If sequences of choices represents an accepting computation
for N (ie N enters an Accept state), then
D halts and accepts
- Else (ie a number represents an infeasible or rejecting
computation) continue with the next step
- Initialize Tape 3 with the string that represents the next
possible sequence of choices of N
- 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 ...