AFTD Auto-Formalizing Theoretical Domains

Cslib.Turing.SingleTapeTM.compComputer

defimported Lean

A Turing machine computing the composition of two other Turing machines. If f and g are computed by Turing machines tm1 and tm2 then we can construct a Turing machine which computes g ∘ f by first running tm1 and then, when tm1 halts, transitioning to the start state of tm2 and running tm2.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Cslib Cslib.Turing Cslib.Turing.SingleTapeTM in
open Relation in
open Cslib.Turing.BiTape Cslib.Turing.StackTape in
open _root_.Turing in
variable {Symbol : Type} in
variable [Inhabited Symbol] [Fintype Symbol] in
def Cslib.Turing.SingleTapeTM.compComputer (tm1 tm2 : SingleTapeTM Symbol) : SingleTapeTM Symbol
Defined in
CSLib, `Cslib.Turing.SingleTapeTM.compComputer`
Lean proof
By Bolton Bailey, Pim Spelier, Daan van Gent, from github.com/leanprover/cslib at 3951377e5a3f (Copyright (c) 2026 Bolton Bailey. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.
Verified
08 Oct 2026
Axioms
none listed
Built on 24
Used by 10

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Cslib Cslib.Turing Cslib.Turing.SingleTapeTM in
open Relation in
open Cslib.Turing.BiTape Cslib.Turing.StackTape in
open _root_.Turing in
variable {Symbol : Type} in
variable [Inhabited Symbol] [Fintype Symbol] in
/-- A Turing machine computing the composition of two other Turing machines. If f and g are computed by Turing machines `tm1` and `tm2` then we can construct a Turing machine which computes g ∘ f by first running `tm1` and then, when `tm1` halts, transitioning to the start state of `tm2` and running `tm2`. -/
def Cslib.Turing.SingleTapeTM.compComputer (tm1 tm2 : SingleTapeTM Symbol) : SingleTapeTM Symbol where
  -- The states of the composed machine are the disjoint union of the states of the input machines.
  State := tm1.State ⊕ tm2.State
  -- The start state is the start state of the first input machine.
  q₀ := .inl tm1.q₀
  tr q h :=
    match q with
    -- If we are in the first input machine's states, run that machine ...
    | .inl ql => match tm1.tr ql h with
      | (stmt, state) =>
        -- ... taking the same tape action as the first input machine would.
        (stmt,
          match state with
          -- If it halts, transition to the start state of the second input machine
          | none => some (.inr tm2.q₀)
          -- Otherwise continue as normal
          | _ => Option.map .inl state)
    -- If we are in the second input machine's states, run that machine ...
    | .inr qr =>
      match tm2.tr qr h with
      | (stmt, state) =>
        -- ... taking the same tape action as the second input machine would.
        (stmt,
          match state with
          -- If it halts, transition to the halting state
          | none => none
          -- Otherwise continue as normal
          | _ => Option.map .inr state)
See it in the graphDiscuss this resultChallenge it