T Naughton, CS NUIM, Back to CS403 home

Remove everything from your desk except pens/pencils. Paper will be provided. 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. 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.

You may keep this question sheet when finished. Solutions will be provided within one week.

Section A – Turing machine programming (40 marks)

Q1 Write a Turing machine to increment a unary number by three. 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 "111" would be transformed into "111111". Comment every line in your table of behaviour.

Section B – Computability (60 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

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

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

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

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

(a) a subset of S
(b) a proper subset of S₀
(c) countable
(d) uncountably infinite
(e) none of the above

(a) any language over S must be finite
(b) at least one language over S is uncountable
(c) any language over S is countable
(d) each language over S₀ is finite
(e) none of the above

(a) A ¹ 2^X
(b) A = 2^X
(c) (cardinality of A) > (cardinality of 2^X )
(d) if X is not finite then A is not uncountable
(e) none of the above

(a) f is either surjective or injective but not both
(b) f is injective
(c) f (a) is recursively enumerable
(d) f (a) is total over all domains
(e) at least one bÎB does not have an aÎA mapping to it

(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

(a) yes
(b) no
(c) yes, but only if A₀, A₁, A₂, … have different cardinalities (are not equinumerous)
(d) only if a is at the diagonal of an enumeration of the set of sets
(e) none of the above

(a) only one tuple <a, b> exists for each bÎB
(b) f may be written f (b) = a
(c) every bÎB has a corresponding aÎA
(d) every aÎA has a bÎB, but more than one aÎA may map to the same bÎB
(e) none of the above

(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

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