Answer
exactly three of the five questions presented below. Make sure you
answer briefly but clearly. Extraneous incorrect information will
cause the score for otherwise correct answers to be lowered.
No aid other than your textbook is allowed on this examination.
Pledge (Must be signed according to UF Honor Code)
On my honor, I have neither given nor received unauthorized aid in doing this assignment.
________________________________ (signature)
Examination Questions
- In homework problem 3.19, you could have replaced the question
``Does God exist?'' by any other single question. In effect, you
showed that any decision problem (one that has a yes/no answer)
having a single instance (that is, no parameters) is decidable.
Now demonstrate that any problem having a finite number of
instances (that is a finite collection of assignments of values
to parameters) is decidable.
- Give an implementation-level description of a machine to accept
the language 0p such that p is
a prime number.
- Say that a write-once Turing machine is a single-tape TM that
can alter each tape square at most once (including the input
portion of the tape). Show that this variant Turing machine model is
equivalent to the ordinary Turing machine model. (Wilson's hint:
Use even more tape than the write-twice Turing machine.)
- Show that every unrecognizable language has a decidable
subset.
- Show that any Turing Machine having input alphabet {0,1} can be
simulated by a Turing Machine having input alphabet {1}. In other
words, give a high-level description of how to encode an input
over {0,1} as an input over {1}, and explain how a Turing
Machine can decode such an input into a string over {0,1} and
then simulate another machine's behavior.
This document is copyright 1998 by Joseph N. Wilson.