7. Use the general algorithm to transform the following finite
automaton for recognizing possibly signed binary integers to a
Turing machine. This automaton has a starting state s, an
intermediate state i, a final state f, and a sink state k, and the
following transitions:
Show, stepbystep, how your Turing
machine will accept the word +01.
8. Use the general algorithm to transform the following PDA into a
twotape Turing machine. This PDA recognizes words of the type
ww
^{R}, where w is any word, and w
^{R} means the
same word reversed.
For example, if w = ab, then w^{R} = ba, and
ww^{R} = abba.
The pushdown automaton has 4 states:
 the starting state
s,
 the reading state r,
 the checking state c, and

the final state f.
The transitions are as follows:

From s to r, the transition is:
 From r to r, the transitions are:
 From
r to c, we have a jump ε, ε → ε.

From c to c, the transitions are:
 From c to f, the only
transition is:
Show, stepbystep, how the resulting Turing machine will
recognize the sequence
abba.
9. What is NP? What is P? What is NPcomplete? What is NPhard?
Give brief definitions. Give an example of an NPcomplete problem.
Is P equal to NP?
10. Formulate ChurchTuring thesis. Is it a mathematical theorem? Is
it a statement about the physical world?