NUIMCrest CS403 - Computational Complexity Theory
Class Test 1 (repeat)
Thursday 7 February 2002, 14:00, Lab 5A

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 50 minutes in total.

Use the MCQ answer sheet for Section B. Write both your name and student id. number the MCQ sheet. 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 down). 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, q0, F) = ({00,01,02,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 (1,-) 01 (1,-) (R,S)
00 (0,-) 01 (0,-) (R,S)
00 (0,1) 01 (0,1) (R,S)
00 (1,1) 01 (1,1) (R,S)
00 (-,-) 09 (-,-) (S,S)
01 (0,-) 02 (0,-) (S,S)
01 (1,-) 02 (1,-) (S,S)
02 (1,-) 00 (1,1) (R,R)
02 (0,-) 00 (0,0) (R,R)

(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?

Q2 Which of the following functions has the largest growth rate?

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

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

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

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

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

Q8 Which of the following languages is not recursive?

Q9 What did Gödel prove?
Q10 As a direct result of one of Gödel's theorems, we can say that in order to build a pocket calculator that...
Q11 The set of accepting Turing machines coincides with which of the following sets? Q12 The set of recognising Turing machines does not coincide with proper subsets of which of the following sets?

Q13 The minimum number of symbols we can reduce our set of symbols to without changing the functionality of any possible TM is

Q14 Consider Turing machine T of the form (Q, S, I, q0, F), where I is a set of tuples of the form (q, s, q', s', m), and where all symbols have their usual meaning. Which of the following conditions must be true for T to be a valid Turing machine? Q15 Consider T from Q14. Which of the following conditions can be true for T to be a valid Turing machine?