Turing Machines

Maheshwari & Smid · Ch. 6 · Introduction to Theory of Computation

A Turing machine has an infinite tape, a read/write head, and a finite set of states. It can move left or right, write symbols, and loop forever. This is the standard model of general computation. The Church-Turing thesis says that anything we'd call "computable" can be computed by a Turing machine.

Definition

A Turing machine is a 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject):

Γ — tape alphabet (includes blank symbol □)
δ — Q × Γ → Q × Γ × {L, R}
The machine halts when it enters q_accept or q_reject
Or it may loop forever (never halt)

Simulating a Turing machine

This TM recognizes aⁿbⁿcⁿ: cross off one a, one b, one c per pass. If all are crossed off evenly, accept.

Scheme

; Turing machine for a^n b^n c^n
; Strategy: repeatedly cross off one a, one b, one c.
; Accept if all symbols are crossed off.

(define (tm-anbncn input)
  (define tape (make-vector (+ (string-length input) 1) "_"))
  (let init ((i 0))
    (when (< i (string-length input))
      (vector-set! tape i (substring input i (+ i 1)))
      (init (+ i 1))))

  (define (find-and-cross ch start)
    (let loop ((i start))
      (cond
        ((>= i (vector-length tape)) #f)
        ((equal? (vector-ref tape i) ch)
         (vector-set! tape i "x") i)
        ((equal? (vector-ref tape i) "_") #f)
        (else (loop (+ i 1))))))

  (define (all-crossed?)
    (let loop ((i 0))
      (cond
        ((>= i (vector-length tape)) #t)
        ((equal? (vector-ref tape i) "x") (loop (+ i 1)))
        ((equal? (vector-ref tape i) "_") #t)
        (else #f))))

  (let outer ()
    (let ((a-pos (find-and-cross "a" 0)))
      (if (not a-pos)
          (all-crossed?)
          (let ((b-pos (find-and-cross "b" (+ a-pos 1))))
            (if (not b-pos) #f
                (let ((c-pos (find-and-cross "c" (+ b-pos 1))))
                  (if (not c-pos) #f
                      (outer)))))))))

(display "abc:       ") (display (tm-anbncn "abc")) (newline)
(display "aabbcc:    ") (display (tm-anbncn "aabbcc")) (newline)
(display "aaabbbccc: ") (display (tm-anbncn "aaabbbccc")) (newline)
(display "aabbc:     ") (display (tm-anbncn "aabbc")) (newline)
(display "ab:        ") (display (tm-anbncn "ab"))

; Turing machine for a^n b^n c^n
; Strategy: repeatedly cross off one a, one b, one c.
; Accept if all symbols are crossed off.

(define (tm-anbncn input)
  (define tape (make-vector (+ (string-length input) 1) "_"))
  (let init ((i 0))
    (when (< i (string-length input))
      (vector-set! tape i (substring input i (+ i 1)))
      (init (+ i 1))))

(define (find-and-cross ch start)
    (let loop ((i start))
      (cond
        ((>= i (vector-length tape)) #f)
        ((equal? (vector-ref tape i) ch)
         (vector-set! tape i "x") i)
        ((equal? (vector-ref tape i) "_") #f)
        (else (loop (+ i 1))))))

(define (all-crossed?)
    (let loop ((i 0))
      (cond
        ((>= i (vector-length tape)) #t)
        ((equal? (vector-ref tape i) "x") (loop (+ i 1)))
        ((equal? (vector-ref tape i) "_") #t)
        (else #f))))

(let outer ()
    (let ((a-pos (find-and-cross "a" 0)))
      (if (not a-pos)
          (all-crossed?)
          (let ((b-pos (find-and-cross "b" (+ a-pos 1))))
            (if (not b-pos) #f
                (let ((c-pos (find-and-cross "c" (+ b-pos 1))))
                  (if (not c-pos) #f
                      (outer)))))))))

(display "abc:       ") (display (tm-anbncn "abc")) (newline)
(display "aabbcc:    ") (display (tm-anbncn "aabbcc")) (newline)
(display "aaabbbccc: ") (display (tm-anbncn "aaabbbccc")) (newline)
(display "aabbc:     ") (display (tm-anbncn "aabbc")) (newline)
(display "ab:        ") (display (tm-anbncn "ab"))

The Church-Turing thesis

Every model of computation that has been proposed (lambda calculus, recursive functions, register machines, your laptop) computes exactly the same class of functions as a Turing machine. This is not a theorem but a thesis: it cannot be proved because "computable" has no prior formal definition. It has never been refuted.

Neighbors

🪄 SICP Ch.4 — the metacircular evaluator is a universal Turing machine in disguise
🪄 Programming Ch.18 — register machines are an implementation of Turing machines
🔑 Logic Ch.10 — Turing's halting problem and Gödel's incompleteness are equivalent
✏️ Hoare/Core.lean — Hoare logic reasons about programs that Turing machines compute

← Pushdown Automata by june.kim Decidability →