T Naughton, CS NUIM, Back to CS403 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. Answer Section A first. After 30 minutes you will be given the Section B questions.

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 divide a unary number by two (rounding up). 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 "1111" would be transformed into "11", and input "111" would be transformed into "11".

Q2 You are given a 2-tape Turing machine T = (Q, S, I, q₀, F) = ({00,01,02,03,09}, {0,1,-}, I, 00, {09}) that operates on binary strings. As usual, the head of the first tape will be positioned at the beginning of the input and the second tape will be blank. I is

q   s    q'  s'    m
00 (0,-) 00 (0,-) (R,S)
00 (1,-) 01 (1,-) (R,S)
00 (-,-) 02 (-,-) (L,S)
01 (0,-) 00 (0,-) (R,S)
01 (1,-) 01 (1,-) (R,S)
01 (-,-) 03 (-,-) (L,S)
02 (0,-) 09 (0,0) (S,S)
02 (1,-) 09 (1,0) (S,S)
02 (-,-) 09 (-,-) (R,S)
03 (0,-) 09 (0,1) (S,S)
03 (1,-) 09 (1,1) (S,S)
03 (-,-) 09 (-,-) (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 at least one less state than T.

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 Which of the following functions has the largest growth rate?

(a) n^1/2
(b) n^1/10
(c) n¹⁰⁰
(d) 2^n/2
(e) 2^n!

Q4 We can reduce our number of unique tape symbols in a TM table of behaviour by

(a) increasing the size of the set of symbols
(b) writing more symbols on the tape
(c) increasing the number of states of mind
(d) a method requiring both (b) and (c)
(e) either (b) or (c)

Q5 Which of the following are not one of the unrestricted models of computation?

(a) TMs with only one tape
(b) k-tape TMs with a finite set of symbols
(c) k-tape TMs whose tapes are infinite in one direction only
(d) RAMs with fixed sized registers
(e) none of the above

Q6 Which of the following is an unrestricted model of computation?

(a) any C++ program
(b) the subset of Java programs that do not use `for' loops
(c) k-tape TMs with finite length tapes and an infinite set of states
(d) all of the above
(e) none of the above

Q7 ``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

Q8 The hypothesis that there is a notion of effective calculability independent of any particular formalism is

(a) provably true
(b) provably false
(c) a direct result of Church's thesis
(d) a direct result of Gödel's Incompleteness theorem
(e) a direct result of Turing's thesis

Q9 If every mathematical statement in a formal system can be either proved or disproved (i.e. proved false) then the system is

(a) consistent
(b) complete
(c) provably decidable
(d) complete or consistent but not both
(e) undefined because no sufficiently formal system can have such a property

Q10 Given that I is the set of quintuples of the form (q, s, s', m, q') of a k-tape deterministic Turing machine T (with k³1 and defined by the tuple (Q, S, I, q₀, F) ) which of the following is false?

(a) s Î S^k
(b) q ¹ q' for all quintuples
(c) m Î {L, R, S}^k
(d) no pair of quintuples has the same first two elements
(e) none of the above

Q11 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

Q12 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

Q13 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

Q14 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

Q15 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