T Naughton, CS NUIM, Back to SE307 home

Remove everything from your desk except pens/pencils. Paper will be provided. Turn off all computer monitors. Answer all questions. You have 60 minutes in total.

Use the MCQ answer sheet for Section B. Write both your name and student id. number the MCQ sheet. Each MCQ question has only one fully correct option. Negative marking will be enforced: +1 for a correct answer, -0.25 for an incorrect answer, 0 for a non attempt. This means that randomly guessing answers will average a mark of zero.

Section A – Turing machine programming (50% of total test marks)

Q1 Write a Turing machine to increment an arbitrary natural number written as a binary string. Initially the TM head will be at the beginning of the input. At halt, the TM head must be at the beginning of the output. For example, input "11" would be transformed into "100", and input "0101" would be transformed into "0110".

Q2 You are given a 2-tape Turing machine T = (Q, S, I, q₀, F) = ({00,01,02,03,04}, {1,-}, I, 00, {04}) that operates on unary strings. The head of each tape will be positioned at the beginning of its input string. I is

q   s    q'  s'    m
00 (1,1) 00 (1,1) (R,S)
00 (1,-) 00 (1,-) (R,S)
00 (-,1) 01 (1,-) (R,R)
00 (-,-) 02 (-,-) (L,S)
01 (1,1) 03 (-,-) (R,R)
01 (-,1) 01 (1,-) (R,R)
01 (-,-) 02 (-,-) (L,S)
02 (1,-) 02 (1,-) (L,S)
02 (-,1) 01 (1,-) (R,R)
02 (-,-) 04 (-,-) (R,S)

(a) What does T do? Give as concise an explanation as you can.

(b) Convert T into a functionally-identical Turing machine that requires as few states as possible.

Section B – Computability (50% of total test marks)

Q1 Who invented the Turing machine?

(a) Alan Mathison Turing
(b) N. P. Completeness
(c) E. Post
(d) The halting problem
(e) None of the above

Q2 Who did not invent the Turing machine?

(a) Alan Turing
(b) A. M. Turing
(c) Turing
(d) Alan Mathison Turing
(e) None of the above

Q3 "In order to ensure that a machine would be able to answer every question from some formal system (say, arithmetic) we would have to permit it to give incorrect answers some of the time." This statement is

(a) provably true
(b) provably false
(c) a direct result of Church's thesis
(d) a direct result of Turing's thesis
(e) none of the above

Q4 "All machines have equal power (in terms of computability)." This statement is

(a) provably true
(b) provably false
(c) a direct result of Church's thesis
(d) a direct result of Turing's thesis
(e) none of the above

Q5 Which of the following is necessary to describe the global state of a 1-tape deterministic Turing machine?

(a) the current line `executed' in the table of behaviour
(b) the current symbol being scanned
(c) the infinite tape
(d) the position of the tape head
(e) all of the above

Q6 Which of the following is not necessary to describe the global state of a 1-tape deterministic Turing machine?

(a) the finite number of symbols on the tape
(b) the current state
(c) the current symbol being scanned
(d) the position of the tape head
(e) all of the above are necessary

Q7 Any two infinite sets A and B are equinumerous if

(a) a bijection exists between one of them and the natural numbers
(b) a bijection exists between one of them and a proper subset of the other
(c) both are finite
(d) a bijection exists between them
(e) both sets can be enumerated or ordered

Q8 The `strongest' of the following statements we can make about the summation 1 + 2 + 3 + ... + n is

(a) = O(n²)
(b) = ½ n² + O(n)
(c) = O(n²) + O(n)
(d) = O(n²) - n
(e) = n² + O(n)

Q9 Given that a k-tape deterministic Turing machine T with k³1 can be defined by the tuple á Q, S, I, q₀, Fñ, which of the following is false?

(a) Q is always finite
(b) Q is a set of states
(c) S is always finite
(d) I is always finite
(e) none of the above

Q10 Given that a k-tape deterministic Turing machine T with k³1 can be defined by the tuple á Q, S, I, q₀, Fñ, which of the following is always true?

(a) |F| ³ 2
(b) if |F|> 2 the TM is guaranteed to halt
(c) if |F|< 2 the TM might halt
(d) if |F|=1 the TM is guaranteed to halt
(e) if |F|=1 the TM will never halt

Q11 Which of the following languages is not recursively enumerable?

(a) {a, b, c}
(b) the odd integers
(c) the prime numbers
(d) the halting Turing machines
(e) none of the above

Q12 Which of the following languages is not recursive?

(a) {a, b, c}
(b) the odd integers
(c) the prime numbers
(d) the halting Turing machines
(e) none of the above

Q13 The set of accepting Turing machines does not coincide with which of the following sets?

(a) the set of random access machines
(b) the set of recursive functions
(c) the set of partial recursive functions
(d) the set of recursively enumerable languages
(e) the set of C++ programs

Q14 Given an alphabet S, a language over S is a

(a) superset of 2^S
(b) subset of S*
(c) superset of S*
(d) proper subset of S₀*
(e) none of the above

Q15 If the power set of a set X, written as 2^X, is countable then X must

(a) be countably infinite
(b) be finite
(c) have a bijection with the natural numbers
(d) all of the above
(e) none of the above