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 = {(<M>,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 ?