General comments:
1-2. Prove that the language L = {d^{n}e^{n+1}f^{n+2}} = {eff, deefff, ddeeeffff, ...} is not context-free.
3. Trace the following Turing machine on the example of the word yn: start, _ → work, R (here, _ means blank); work, y → R; work, n → y, R; work, _ → back, L; back, y → L; back, _ → halt. Explain how each step will be represented if we interpret the Turing machine as a finite automaton with two stacks.
4. Design a Turing machine that adds 10 (binary version of 2) to a binary number. Trace your Turing machine, step-by-step, on the example of the string 11. Why in Turing machines (and in most actual computers) the representation of a binary number starts with the least significant digit?
5. The following finite automaton describes strings with at least two letters y. This automaton has the starting state s, the state 1 meaning that we have letter y, the final state f, and the following transitions:
6. Give the formal definition of a feasible algorithm. Give two examples different from what we had in class:
7. What is P? What is NP? What does it means for a problem to be NP-hard? NP-complete? Give brief definitions. Give an example of an NP-complete problem: explain what is the input, what is the desired output. Is P equal to NP?
8. Prove that the cubic root of 2 is not a rational number.
9. Formulate the halting problem. Prove that it is not possible to check whether a given program halts on given data.
10. Formulate Church-Turing thesis. Is it a mathematical theorem? Is it a statement about the physical world?