← All topics
Quiz: Turing Machine Traces: questions with answers
10 questions, each with the answer and a short explanation.
Take the timed quiz + get a certificate →- Q1. In the ID 1 1 [q0] + 1 1, which symbol is under the head?
- Q2. The rule δ(q0, +) = (q1, 1, R) is applied to 1 1 [q0] + 1 1. What is the next ID?
- Q3. How many moves does the unary adder make on 111+11?
- Q4. What does this print? (code)
- Q5. Why can the palindrome language not be recognised by a DFA, but can by a Turing machine?
- Q6. In the palindrome machine, state q2a reads a blank. What does that mean?
- Q7. On input abb, why does the palindrome machine reject?
- Q8. The palindrome TM takes about how many moves on an input of length n?
- Q9. What happens if a Turing machine reaches a (state, symbol) pair with no transition?
- Q10. Which machine could check palindromes in O(n) moves?