Mark your calendar
CS 46 Comprehensive Final Exam
is scheduled for Friday, 8 May 9am-12n in Sci 264.
Due: Wednesday, April 8
Hints and remarks:
5.4.4 hints:
What I want you to think about and maybe solve is: Given a 1-tape DTM,
M, (with possibly lots of states) show how to construct a 1-tape DTM,
M', where M' has about 6 states and L(M') = L(M).
let M=(K,Sigma,delta,s,H) be the TM with lots of
states to be simulated by M'=(K',Sigma',delta',s',H') where K'
has about 6 states. You might want to consider making Sigma'
contain all of Sigma and also all of
K x Sigma (you'll probably need
more but start this way). Then if all
but one of the tape squares of M' contains single elements
of Sigma and one
of the tape squares of M' contains a pair (q,c), this might mean
that M' is currently simulating M in state q looking at input c
at the tape location where the pair is. Changing state and writing
at the same tape location is pretty easy to simulate with few (one??)
state of M'. But simulating a move to the left or right
(with say 5-6 states of M') is
pretty tricky and you'll probably have to increase Sigma' for
this trick. Just do the best you can.
5.4.4 remarks: These remarks are for deterministic, one-tape,
two-way infinite Turing machines that can write and move in a
single step.
Claude Shannon, of Information Theory fame, showed
how to simulate any TM with a 2-state TM. Of course his
alphabet is big.
Marvin Minsky, of AI fame, has shown how to construct a Universal
TM with 7 states and 4 input symbols. This means that the 'size' of
the delta function is 28 = 7 x 4. This result has been around
for about 35 years. Recently (2002), Stephen Wolfram of Mathematica fame
announced a 2-state 5-symbol machine. In October 2007, a disputed
2-state, 3-symbol machine was announced by an undergraduate at the
University of Birmingham, UK. It is disputed because
a respected CS theorist (Vaughn Pratt of Stanford) says there
is a flaw in the proof, yet Wolfram claims
it does work. I have not investigated.
5.5.2 hints: look at
http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fourse7.html
for some ideas but do it in your own words.
for part (b), look at handout I'll give on Monday and remember Thm 3.7.1:
DCFLs are closed under complement.