Lab 3 — Turing Machine

Purpose

Understand the concept of a Turing machine proposed by Alan Turing in 1936 as an abstract universal computing model, and implement two classic problems using the online simulator.

Simulator: turingmachine.io

Theory

A Turing machine consists of an infinite tape, a read/write head, a state register, and a transition table. It is not a physical machine but a logical computing construct used to clarify the concept of an algorithm.

Example 1 — Caesar Cipher (+3)

Input: abba — Output: deed

input: 'abba'
blank: ' '
start state: right
table:
  right:
    a: {write: d, R}
    b: {write: e, R}
    ' ': {L: carry}
  carry:
    [d, e]: L
    ' ': {R: done}
  done:

Example 2 — Card Flip Problem

20 cards lie face-down. On each move, a face-down card is flipped and simultaneously the card to its right is also flipped.

Input: '11011011111110111101'

blank: ' '
start state: right
table:
  right:
    1: {write: 0, R: yes}
    0: {R}
    ' ': {L: carry}
  yes:
    1: {write: 0, L: right}
    0: {write: 1, L: right}
  carry:
    [1, 0]: L
    ' ': {R: done}
  done:

Live Demo — Caesar Cipher (+3)

Enter a lowercase string (letters a-w, so shifting by +3 stays within a-z) and watch the Turing machine shift each letter, step by step.

Code-behind (C#)

// Lab 3 - Turing Machine (Caesar cipher, shift +3)
protected void btnRun_Click(object sender, EventArgs e)
{
    string input = txtInput.Text.ToLower();

    var tape = new List<char>(input);
    tape.Add(' '); // blank to the right of input

    int head = 0;
    string state = "right";

    // Phase 1: shift each letter by +3, move right until blank
    while (state == "right")
    {
        char c = tape[head];
        if (c == ' ')
        {
            state = "carry";
            head--;
        }
        else
        {
            tape[head] = (char)(c + 3); // a->d, b->e, ...
            head++;
        }
    }

    // Phase 2: move left back to start
    while (state == "carry")
    {
        if (head < 0 || tape[head] == ' ')
        {
            state = "done";
            head++;
        }
        else
        {
            head--;
        }
    }

    string result = new string(tape.Where(c => c != ' ').ToArray());
}

Tasks

1. Implement Example 2 (card flip) in the Turing machine simulator.
2. Complete your assigned option:
   • Option 1: Replace 0 with 1 and 1 with 0, with carriage return.
   • Option 2: Replace 1 with 'e', 0 with 'n', with carriage return.
   • Option 3: Replace 'n' with 0, 'e' with 1.

Conclusion

The Turing machine demonstrates that any computable algorithm can be expressed as a finite set of state transitions. The Caesar cipher example shows how character substitution can be implemented as state-based symbol rewriting.