PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q4(b)

Theory of Computation · 4 marks

Open in the Padhaiko app

Topic: Turing Machines: Representation, Moves & Computing

Question

Design a Turing machine that can compute a function

Solution

Mathematical Formulation in Unary Representation: In computability theory, non-negative integer functions are represented on a Turing machine tape using unary notation:

Algorithm for Unary Input :

  1. If tape is empty (), halt immediately with empty tape: .
  2. For each original on the tape:
    • Overwrite with temporary marker .
    • Move right past all original 's and previously appended 's to the first blank cell .
    • Write marker (representing the doubled counterpart).
    • Rewind left past 's and 's back to the marked .
  3. Repeat until all original 's have been replaced by 's (tape contains ).
  4. When the head reads in the search state, all original symbols have been processed. Rewind to the left end of the tape and convert every and back to , resulting in on the tape.

Automaton Implementation and Verification: The formal machine definition is:

TM: Compute f(x) = 2xTM
TM: Compute f(x) = 2x X/0,R Y/0,R X/X,L 0/0,L Y/Y,L 0/0,R Y/Y,R B/B,S 0/X,R B/Y,L X/X,R Y/Y,L B/B,R B/B,S q0 q1 q2 q3 q4 q_restore
StateReadNext StateWriteMove
→q0Bq4BS
→q00q1XR
q10q10R
q1Yq1YR
q1Bq2YL
q20q20L
q2Yq2YL
q2Xq0XR
→q0Yq3YL
q3Xq3XL
q3Bq_restoreBR
q_restoreXq_restore0R
q_restoreYq_restore0R
q_restoreBq4BS
  • Machine-checked
  • ✓ 0 → 00
  • ✓ 00 → 0000
  • ✓ 000 → 000000
  • ✓ 0000 → 00000000
Answer:

Using unary representation , the TM marks each as and appends a corresponding at the end of the tape. Once all symbols are marked (), it converts all and markers back into , producing output .

All past exam questions for Theory of Computation