Skills101
← All practice quizzes

Quiz: Turing Machine Traces

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Learn to trace a Turing machine exactly the way exam questions ask — one instantaneous description per move. Build and trace a unary adder and a palindrome checker, read a transition table, count steps to see why simple TMs are slow, and check every trace with a Python simulator.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    In the ID 1 1 [q0] + 1 1, which symbol is under the head?

  2. Question 2

    The rule δ(q0, +) = (q1, 1, R) is applied to 1 1 [q0] + 1 1. What is the next ID?

  3. Question 3

    How many moves does the unary adder make on 111+11?

  4. Question 4

    What does this print?

    add = {("q0", "1"): ("q0", "1", "R"), ("q0", "+"): ("q1", "1", "R"),
           ("q1", "1"): ("q1", "1", "R"), ("q1", "_"): ("q2", "_", "L"),
           ("q2", "1"): ("acc", "_", "L")}
    cells, head, state = dict(enumerate("11+1")), 0, "q0"
    while state != "acc":
        state, cells[head], move = add[(state, cells.get(head, "_"))]
        head += 1 if move == "R" else -1
    print("".join(cells.values()).strip("_"))
    
  5. Question 5

    Why can the palindrome language not be recognised by a DFA, but can by a Turing machine?

🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →