332, Spring 2019
Midterm practice questions
Please note: These are just examples of the type of problem that might be on the exam on Thursday.
Some were part of old exams gibe in past years. I would not worry about answering each one, better
to spend your time on class notes and problems from this semester's class.
1.
Consider
TM M with, states: qo,q1,q2,q3, qa,qr
Input alphabet : 0,1,X,Y Tape alphabet: 0,1,X,Y,B
f(qo, 0) = (q1,X,R)
f(q0, 1) = (qr,-,-)
f(q0, X) = (qr,-,-)
f(q0, Y) = (q3,Y,R)
f(q0, B) = (qr,-,-)
f(q1, 0) = (q1,0,R)
f(q1, 1) = (q2,Y,L)
f(q1, X) = (qr,-,-)
f(q1, Y) = (q1,Y,R)
f(q1, B) = (qr,-,-)
f(q2, 0) = (q2,0,L)
f(q2, 1) = (qr,-,-)
f(q2, X) = (q0,X,R)
f(q2, Y) = (q2,Y,L)
f(q2, B) = (qr,-,-)
f(q2, 0) = (q2,0,L)
f(q2, 1) = (qr,-,-)
f(q2, X) = (q0,X,R)
f(q2, Y) = (q2,Y,L)
f(q2, B) = (qr,-,-)
f(q3, 0) = (qr,-,-)
f(q3, 1) = (qr,-,-)
f(q3, X) = (qr,-,-)
f(q3, Y) = (q3,Y,R)
f(q3, B) = (qa,-,-)
i. Show M's computation om the string 01, 0101, 0011, and on 011,
ii. Is M a decider ? is it an acceptor ? Explain
What is L(M) ? (too long for midterm but a good question.)
2. Prove that any infinite decidable set L has infinitely many decidable, infinite subsets.
3. T or F: If a language L is accepted by some TM T
then the complement of L is either acceptable or decidable.
4. Assume that you know that a set S of natural numbers is acceptable but not decidable.
Show that N-S is neither acceptable nor decidable. Can you decide whether N-S is finite
or infinite ?
EXAMPLES
You need not justify your answers, but you should be precise about the example you are
defining. It may be helpful to use set theory notation or to explain your terms when you
give the example.
5. Give an example of two infinite languages K and L, both subsets of N and whose intersection contains
exactly 5 elements.
7. Give two examples of evidence that Church/Turing's thesis is true.
By evidence I mean some statement which is known to be true and which supports the thesis.
Explain your reasoning.
8. Show that L = {(,x,n) | M is a Turing machine, M(x) halts and n is an even integer }
is undecidable. (Hint: Use the fact that the halting problem is undecidable.)
Is L recognizable ?