Question 1: Turing Machines
(a) Give exactly three differences between Turing machines and NFAs. [6]
(b) The following is the state diagram of a Turing machine M1 with input
alphabet {0, 1} and accept state q3. (Missing transition arrows are assumed to lead to a reject state, not shown.)
1
(i) Give the sequence of configurations of M1 on the input string
01101, starting with initial configuration q001101. [7]
(ii) In general, given any input string w, what will the tape contents
of M1 look like after halting? [2]
(c) Consider a Turing machine M2, with input alphabet {a, b} and accept
state qa, that has the following behaviour:
Given any input string w ∈ {a, b}∗, M2 halts in an accepting
state in the configuration qax|w|

wR, where wR is the reverse

of w.
For example, on input abb, M2 halts in an accepting configuration
qaxxx#bba, while on input baaaba it halts in an accepting configuration qaxxxxxx#abaaab.
(i) Create a state diagram in JFLAP for M2, using the fewest states
possible. You may assume a two-way infinite tape, and the reject
state may be omitted from your diagram. You must include a
screenshot of your diagram in your submitted pdf and a separately
submitted JFLAP .jff file containing your diagram (zero marks
awarded without either of these). [4]
(ii) Give a high-level (i.e., plain English) description of how M2 should
work given an input string w ∈ {a, b}∗. [5]
(iii) Discuss the time complexity of the specific implementation of M2
that you have given in your state diagram in part c(i) above. In
particular, does it run in O(n) steps? O(n2) steps? Or O(nk)
steps for some k > 2? Justify your answer. (You may make free
use of mathematical formulas for calculating arithmetic series in
your answer). [6]
2
Question 2: Logic and Computational Complexity
(a) Let p, q, r be propositional variables such that the value assigned to
p is T, the value assigned to q is F, and the value assigned to r is T.
Give the truth-values of the following sentences:
(i) p → q [1]
(ii) (p ∧ ¬q) ∨ ¬p [1]
(iii) (¬r → ¬(p ∧ q)) ∧ (r → ¬q) [1]
(b) For the following three parts, consider the sentence (p → q) ∧ (p → r).
(i) Write down a truth-table for the above sentence. [4]
(ii) Give a Boolean circuit that will function in the same way as the
above sentence. The only Boolean circuit gates you may use in
your answer are NOT, AND and OR. [4]
(iii) Is the following a valid inference?
(p → q) ∧ (p → r) |= (q ∧ r)
Explain your answer. [4]
(c) Consider the following language:
X = {〈A, B〉 | A and B are logically equivalent propositional sentences}
Is X decidable? Justify your answer. [6]
(d) Consider the following two functions f1(n) and f2(n):
f1(n) = 8n2 + 12n + 5, f2(n) = n3
.
From the formal definition of Big-O notation f(n) = O(g(n)), show
that f1(n) = O(f2(n)). [4]
(e) Answer each of the following three parts true or false:
(i) n3 + 800n4 = O(n4) [1]
(ii) 2n6 + 6n9 = O(n5) [1]
(iii) 60n2 + 4n3 + 5n10 = O(n2) [1]
(f) Let B be NP-complete and let C be in NP. What would we need to
prove about C in order to be able to prove that C is NP-complete? [2]
3