|
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?
(a) Alan Mathison Turing
(b) N. P. Completeness
(c) E. Post
(d) The halting problem
(e) None of the above
Q2 Which of the following functions has the largest growth rate?
(a) n1/2
(b) n1/10
(c) n100
(d) 2n/2
(e) 2n!
Q3 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
Q4 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
Q5 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
Q6 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
Q7 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
Q8 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
Q9 What did Gödel prove?
(a) no sufficiently powerful formal system can be both consistent and complete
(b) no sufficiently powerful formal system can be both decidable and complete
(c) there is no decision procedure for arithmetic
(d) no sufficiently powerful formal system can be both consistant and decidable
(e) none of the above
Q10 As a direct result of one of Gödel's theorems, we can say that in order to build a pocket calculator that...
(a) never answers incorrectly, it must leave some questions unanswered
(b) can answer all questions, it must contradict itself
(c) never contradicts itself, it must leave some questions unanswered
(d) all of the above
(e) none of the above
Q11 The set of accepting Turing machines coincides with which of the following sets?
(a) the set of halting C++ programs
(b) the set of recursive functions
(c) the set of recursive languages
(d) the set of recursively enumerable languages
(e) none of the above
Q12 The set of recognising Turing machines does not coincide with proper subsets of which of the following sets?
(a) the set of partial functions
(b) the set of recursive functions
(c) the set of partial recursive functions
(d) the set of recursively enumerable languages
(e) none of the above
Q13 The minimum number of symbols we can reduce our set of symbols to without changing the functionality of any possible TM is
(a) 0
(b) 1
(c) 2
(d) greater than 2
(e) no limit
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?
(a) I is finite
(b) if I is finite then T will halt
(c) F is nonempty
(d) if F is nonempty then T will halt
(e) if F is nonempty then T will halt on at least one input
Q15 Consider T from Q14. Which of the following conditions can be true for T to be a valid Turing machine?
(a) S is finite
(b) 2S is finite
(c) s = s' for each tuple in I
(d) all of the above
(e) none of the above