Turing machines

15 questions across Phase 4.

1. MCQ · 1 mark

   δ(q, a) = (p, b, L) means:

   1. read b, write a, move left
   2. read a, write b, move left, go to p
   3. read a, push b
   4. read a, move left without writing
2. MSQ · 2 marks

   On a given input, a TM may:

   1. accept
   2. reject
   3. loop
   4. accept and later reject
3. NAT · 1 mark

   tmInc on 1111: number of symbols in the output (no leading blanks)?

   Write your answer before opening the key.

4. MCQ · 2 marks

   The one-tape cross-off TM for aⁿbⁿcⁿ runs in:

   1. O(n)
   2. O(n²)
   3. O(n³)
   4. O(2ⁿ)
5. MSQ · 2 marks

   Which have exactly the power of a TM?

   1. nondeterministic TM
   2. TM with a two-way infinite tape
   3. PDA with two stacks
   4. LBA
6. MCQ · 1 mark

   Which is a CSL but not a CFL?

   1. aⁿbⁿ
   2. wwᴿ
   3. aⁿbⁿcⁿ
   4. (ab)*
7. MCQ · 1 mark

   A language is recursive iff:

   1. some TM accepts it
   2. some TM decides it (halts on all inputs)
   3. it is context-free
   4. it is infinite
8. MSQ · 2 marks

   Which inclusions are strict?

   1. DCFL ⊂ CFL
   2. CFL ⊂ CSL
   3. CSL ⊂ REC
   4. REC ⊂ RE
9. MCQ · 1 mark

   Type 2 grammars correspond to:

   1. finite automata
   2. PDAs
   3. LBAs
   4. TMs
10. MCQ · 2 marks

    L is RE and L̅ is RE. Then L is:

    1. regular
    2. context-free
    3. recursive
    4. possibly not recursive
11. MSQ · 2 marks

    RE languages are closed under:

    1. union
    2. complement
    3. Kleene star
    4. homomorphism
12. MCQ · 1 mark

    Recursive languages are not closed under:

    1. complement
    2. homomorphism
    3. union
    4. intersection
13. MCQ · 2 marks

    L is RE but not recursive. Then L̅ is:

    1. recursive
    2. RE, not recursive
    3. not RE
    4. context-free
14. MCQ · 1 mark

    The universal TM:

    1. decides { ⟨M,w⟩ : M accepts w }
    2. recognizes { ⟨M,w⟩ : M accepts w }
    3. is an LBA
    4. cannot simulate nondeterministic TMs
15. MCQ · 1 mark

    The Church–Turing thesis is:

    1. a proven theorem
    2. a hypothesis that algorithms = TMs
    3. a statement about speed
    4. about context-free grammars