Computable functions

This file contains the definition of a Turing machine with some finiteness conditions (bundling the definition of TM2 in TuringMachine.lean), a definition of when a TM gives a certain output (in a certain time), and the definition of computability (in polytime or any time function) of a function between two types that have an encoding (as in Encoding.lean).

Main theorems

• idComputableInPolyTime : a TM + a proof it computes the identity on a type in polytime.
• idComputable : a TM + a proof it computes the identity on a type.

Implementation notes

To count the execution time of a Turing machine, we have decided to count the number of times the step function is used. Each step executes a statement (of type stmt); this is a function, and generally contains multiple "fundamental" steps (pushing, popping, so on). However, as functions only contain a finite number of executions and each one is executed at most once, this execution time is up to multiplication by a constant the amount of fundamental steps.

structure Turing.FinTM2 : Type 1

A bundled TM2 (an equivalent of the classical Turing machine, defined starting from the namespace Turing.TM2 in TuringMachine.lean), with an input and output stack, a main function, an initial state and some finiteness guarantees.

• K : Type
• kDecidableEq : DecidableEq self.K
• kFin : Fintype self.K
• k₀ : self.K
• k₁ : self.K
• Γ : self.K → Type
• Λ : Type
• main : self.Λ
• ΛFin : Fintype self.Λ
• σ : Type
• initialState : self.σ
• σFin : Fintype self.σ
• Γk₀Fin : Fintype (self.Γ self.k₀)
• m : self.Λ → Turing.TM2.Stmt self.Γ self.Λ self.σ

instance Turing.FinTM2.decidableEqK (tm : Turing.FinTM2) : DecidableEq tm.K

Equations

• Turing.FinTM2.decidableEqK tm = tm.kDecidableEq

instance Turing.FinTM2.inhabitedσ (tm : Turing.FinTM2) : Inhabited tm.σ

Equations

• Turing.FinTM2.inhabitedσ tm = { default := tm.initialState }

def Turing.FinTM2.Stmt (tm : Turing.FinTM2) : Type

The type of statements (functions) corresponding to this TM.

Equations

• Turing.FinTM2.Stmt tm = Turing.TM2.Stmt tm.Γ tm.Λ tm.σ

instance Turing.FinTM2.inhabitedStmt (tm : Turing.FinTM2) : Inhabited (Turing.FinTM2.Stmt tm)

Equations

• Turing.FinTM2.inhabitedStmt tm = inferInstanceAs (Inhabited (Turing.TM2.Stmt tm.Γ tm.Λ tm.σ))

def Turing.FinTM2.Cfg (tm : Turing.FinTM2) : Type

The type of configurations (functions) corresponding to this TM.

Equations

• Turing.FinTM2.Cfg tm = Turing.TM2.Cfg tm.Γ tm.Λ tm.σ

instance Turing.FinTM2.inhabitedCfg (tm : Turing.FinTM2) : Inhabited (Turing.FinTM2.Cfg tm)

Equations

• Turing.FinTM2.inhabitedCfg tm = Turing.TM2.Cfg.inhabited tm.Γ tm.Λ tm.σ

def Turing.FinTM2.step (tm : Turing.FinTM2) : Turing.FinTM2.Cfg tm → Option (Turing.FinTM2.Cfg tm)

The step function corresponding to this TM.

Equations

• Turing.FinTM2.step tm = Turing.TM2.step tm.m

def Turing.initList (tm : Turing.FinTM2) (s : List (tm.Γ tm.k₀)) : Turing.FinTM2.Cfg tm

The initial configuration corresponding to a list in the input alphabet.

Equations

• Turing.initList tm s = { l := some tm.main, var := tm.initialState, stk := fun (k : tm.K) => if h : k = tm.k₀ then Eq.mpr (_ : List (tm.Γ k) = List (tm.Γ tm.k₀)) s else [] }

def Turing.haltList (tm : Turing.FinTM2) (s : List (tm.Γ tm.k₁)) : Turing.FinTM2.Cfg tm

The final configuration corresponding to a list in the output alphabet.

Equations

• Turing.haltList tm s = { l := none, var := tm.initialState, stk := fun (k : tm.K) => if h : k = tm.k₁ then Eq.mpr (_ : List (tm.Γ k) = List (tm.Γ tm.k₁)) s else [] }

structure Turing.EvalsTo {σ : Type u_1} (f : σ → Option σ) (a : σ) (b : Option σ) : Type

A "proof" of the fact that f eventually reaches b when repeatedly evaluated on a, remembering the number of steps it takes.

• steps : ℕ
• evals_in_steps : (flip bind f)^[self.steps] (some a) = b

structure Turing.EvalsToInTime {σ : Type u_1} (f : σ → Option σ) (a : σ) (b : Option σ) (m : ℕ) extends Turing.EvalsTo : Type

A "proof" of the fact that f eventually reaches b in at most m steps when repeatedly evaluated on a, remembering the number of steps it takes.

• steps : ℕ
• evals_in_steps : (flip bind f)^[self.steps] (some a) = b
• steps_le_m : self.steps ≤ m

def Turing.EvalsTo.refl {σ : Type u_1} (f : σ → Option σ) (a : σ) : Turing.EvalsTo f a (some a)

Reflexivity of EvalsTo in 0 steps.

Equations

• Turing.EvalsTo.refl f a = { steps := 0, evals_in_steps := (_ : (flip bind f)^[0] (some a) = (flip bind f)^[0] (some a)) }

def Turing.EvalsTo.trans {σ : Type u_1} (f : σ → Option σ) (a : σ) (b : σ) (c : Option σ) (h₁ : Turing.EvalsTo f a (some b)) (h₂ : Turing.EvalsTo f b c) : Turing.EvalsTo f a c

Transitivity of EvalsTo in the sum of the numbers of steps.

Equations

• Turing.EvalsTo.trans f a b c h₁ h₂ = { steps := h₂.steps + h₁.steps, evals_in_steps := (_ : (flip bind f)^[h₂.steps + h₁.steps] (some a) = c) }

def Turing.EvalsToInTime.refl {σ : Type u_1} (f : σ → Option σ) (a : σ) : Turing.EvalsToInTime f a (some a) 0

Reflexivity of EvalsToInTime in 0 steps.

Equations

• Turing.EvalsToInTime.refl f a = { toEvalsTo := Turing.EvalsTo.refl f a, steps_le_m := Turing.EvalsToInTime.refl.proof_1 }

def Turing.EvalsToInTime.trans {σ : Type u_1} (f : σ → Option σ) (m₁ : ℕ) (m₂ : ℕ) (a : σ) (b : σ) (c : Option σ) (h₁ : Turing.EvalsToInTime f a (some b) m₁) (h₂ : Turing.EvalsToInTime f b c m₂) : Turing.EvalsToInTime f a c (m₂ + m₁)

Transitivity of EvalsToInTime in the sum of the numbers of steps.

Equations

• Turing.EvalsToInTime.trans f m₁ m₂ a b c h₁ h₂ = { toEvalsTo := Turing.EvalsTo.trans f a b c h₁.toEvalsTo h₂.toEvalsTo, steps_le_m := (_ : h₂.steps + h₁.steps ≤ m₂ + m₁) }

def Turing.TM2Outputs (tm : Turing.FinTM2) (l : List (tm.Γ tm.k₀)) (l' : Option (List (tm.Γ tm.k₁))) : Type

A proof of tm outputting l' when given l.

Equations

• Turing.TM2Outputs tm l l' = Turing.EvalsTo (Turing.FinTM2.step tm) (Turing.initList tm l) (Option.map (Turing.haltList tm) l')

def Turing.TM2OutputsInTime (tm : Turing.FinTM2) (l : List (tm.Γ tm.k₀)) (l' : Option (List (tm.Γ tm.k₁))) (m : ℕ) : Type

A proof of tm outputting l' when given l in at most m steps.

Equations

• Turing.TM2OutputsInTime tm l l' m = Turing.EvalsToInTime (Turing.FinTM2.step tm) (Turing.initList tm l) (Option.map (Turing.haltList tm) l') m

def Turing.TM2OutputsInTime.toTM2Outputs {tm : Turing.FinTM2} {l : List (tm.Γ tm.k₀)} {l' : Option (List (tm.Γ tm.k₁))} {m : ℕ} (h : Turing.TM2OutputsInTime tm l l' m) : Turing.TM2Outputs tm l l'

The forgetful map, forgetting the upper bound on the number of steps.

Equations

• Turing.TM2OutputsInTime.toTM2Outputs h = h.toEvalsTo

structure Turing.TM2ComputableAux (Γ₀ : Type) (Γ₁ : Type) : Type 1

A Turing machine with input alphabet equivalent to Γ₀ and output alphabet equivalent to Γ₁.

• tm : Turing.FinTM2
• inputAlphabet : self.tm.Γ self.tm.k₀ ≃ Γ₀
• outputAlphabet : self.tm.Γ self.tm.k₁ ≃ Γ₁

structure Turing.TM2Computable {α : Type} {β : Type} (ea : Computability.FinEncoding α) (eb : Computability.FinEncoding β) (f : α → β) extends Turing.TM2ComputableAux : Type 1

A Turing machine + a proof it outputs f.

• tm : Turing.FinTM2
• inputAlphabet : self.tm.Γ self.tm.k₀ ≃ ea.Γ
• outputAlphabet : self.tm.Γ self.tm.k₁ ≃ eb.Γ
• outputsFun : (a : α) → Turing.TM2Outputs self.tm (List.map self.inputAlphabet.invFun (ea.toEncoding.encode a)) (some (List.map self.outputAlphabet.invFun (eb.toEncoding.encode (f a))))

structure Turing.TM2ComputableInTime {α : Type} {β : Type} (ea : Computability.FinEncoding α) (eb : Computability.FinEncoding β) (f : α → β) extends Turing.TM2ComputableAux : Type 1

A Turing machine + a time function + a proof it outputs f in at most time(len(input)) steps.

• tm : Turing.FinTM2
• inputAlphabet : self.tm.Γ self.tm.k₀ ≃ ea.Γ
• outputAlphabet : self.tm.Γ self.tm.k₁ ≃ eb.Γ
• time : ℕ → ℕ
• outputsFun : (a : α) → Turing.TM2OutputsInTime self.tm (List.map self.inputAlphabet.invFun (ea.toEncoding.encode a)) (some (List.map self.outputAlphabet.invFun (eb.toEncoding.encode (f a)))) (self.time (List.length (ea.toEncoding.encode a)))

structure Turing.TM2ComputableInPolyTime {α : Type} {β : Type} (ea : Computability.FinEncoding α) (eb : Computability.FinEncoding β) (f : α → β) extends Turing.TM2ComputableAux : Type 1

A Turing machine + a polynomial time function + a proof it outputs f in at most time(len(input)) steps.

• tm : Turing.FinTM2
• inputAlphabet : self.tm.Γ self.tm.k₀ ≃ ea.Γ
• outputAlphabet : self.tm.Γ self.tm.k₁ ≃ eb.Γ
• time : Polynomial ℕ
• outputsFun : (a : α) → Turing.TM2OutputsInTime self.tm (List.map self.inputAlphabet.invFun (ea.toEncoding.encode a)) (some (List.map self.outputAlphabet.invFun (eb.toEncoding.encode (f a)))) (Polynomial.eval (List.length (ea.toEncoding.encode a)) self.time)

def Turing.TM2ComputableInTime.toTM2Computable {α : Type} {β : Type} {ea : Computability.FinEncoding α} {eb : Computability.FinEncoding β} {f : α → β} (h : Turing.TM2ComputableInTime ea eb f) : Turing.TM2Computable ea eb f

A forgetful map, forgetting the time bound on the number of steps.

Equations

• Turing.TM2ComputableInTime.toTM2Computable h = { toTM2ComputableAux := h.toTM2ComputableAux, outputsFun := fun (a : α) => Turing.TM2OutputsInTime.toTM2Outputs (h.outputsFun a) }

def Turing.TM2ComputableInPolyTime.toTM2ComputableInTime {α : Type} {β : Type} {ea : Computability.FinEncoding α} {eb : Computability.FinEncoding β} {f : α → β} (h : Turing.TM2ComputableInPolyTime ea eb f) : Turing.TM2ComputableInTime ea eb f

A forgetful map, forgetting that the time function is polynomial.

Equations

• Turing.TM2ComputableInPolyTime.toTM2ComputableInTime h = { toTM2ComputableAux := h.toTM2ComputableAux, time := fun (n : ℕ) => Polynomial.eval n h.time, outputsFun := h.outputsFun }

def Turing.idComputer {α : Type} (ea : Computability.FinEncoding α) : Turing.FinTM2

A Turing machine computing the identity on α.

Equations

• Turing.idComputer ea = Turing.FinTM2.mk PUnit.unit PUnit.unit (fun (x : Unit) => ea.Γ) Unit PUnit.unit Unit PUnit.unit fun (x : Unit) => Turing.TM2.Stmt.halt

instance Turing.inhabitedFinTM2 : Inhabited Turing.FinTM2

Equations

• Turing.inhabitedFinTM2 = { default := Turing.idComputer default }

def Turing.idComputableInPolyTime {α : Type} (ea : Computability.FinEncoding α) : Turing.TM2ComputableInPolyTime ea ea id

A proof that the identity map on α is computable in polytime.

Equations

• One or more equations did not get rendered due to their size.

instance Turing.inhabitedTM2ComputableInPolyTime : Inhabited (Turing.TM2ComputableInPolyTime default default id)

Equations

• Turing.inhabitedTM2ComputableInPolyTime = { default := Turing.idComputableInPolyTime default }

instance Turing.inhabitedTM2OutputsInTime : Inhabited (Turing.TM2OutputsInTime (Turing.idComputer Computability.finEncodingBoolBool) (List.map (Equiv.cast (_ : (Turing.idComputer Computability.finEncodingBoolBool).Γ (Turing.idComputer Computability.finEncodingBoolBool).k₀ = (Turing.idComputer Computability.finEncodingBoolBool).Γ (Turing.idComputer Computability.finEncodingBoolBool).k₀)).invFun [false]) (some (List.map (Equiv.cast (_ : (Turing.idComputer Computability.finEncodingBoolBool).Γ (Turing.idComputer Computability.finEncodingBoolBool).k₁ = (Turing.idComputer Computability.finEncodingBoolBool).Γ (Turing.idComputer Computability.finEncodingBoolBool).k₁)).invFun [false])) (Polynomial.eval 1 1))

Equations

• Turing.inhabitedTM2OutputsInTime = { default := (Turing.idComputableInPolyTime Computability.finEncodingBoolBool).outputsFun false }

instance Turing.inhabitedTM2Outputs : Inhabited (Turing.TM2Outputs (Turing.idComputer Computability.finEncodingBoolBool) (List.map (Equiv.cast (_ : (Turing.idComputer Computability.finEncodingBoolBool).Γ (Turing.idComputer Computability.finEncodingBoolBool).k₀ = (Turing.idComputer Computability.finEncodingBoolBool).Γ (Turing.idComputer Computability.finEncodingBoolBool).k₀)).invFun [false]) (some (List.map (Equiv.cast (_ : (Turing.idComputer Computability.finEncodingBoolBool).Γ (Turing.idComputer Computability.finEncodingBoolBool).k₁ = (Turing.idComputer Computability.finEncodingBoolBool).Γ (Turing.idComputer Computability.finEncodingBoolBool).k₁)).invFun [false])))

Equations

• Turing.inhabitedTM2Outputs = { default := Turing.TM2OutputsInTime.toTM2Outputs default }

instance Turing.inhabitedEvalsToInTime : Inhabited (Turing.EvalsToInTime (fun (x : Unit) => some PUnit.unit) PUnit.unit (some PUnit.unit) 0)

Equations

• Turing.inhabitedEvalsToInTime = { default := Turing.EvalsToInTime.refl (fun (x : Unit) => some PUnit.unit) PUnit.unit }

instance Turing.inhabitedTM2EvalsTo : Inhabited (Turing.EvalsTo (fun (x : Unit) => some PUnit.unit) PUnit.unit (some PUnit.unit))

Equations

• Turing.inhabitedTM2EvalsTo = { default := Turing.EvalsTo.refl (fun (x : Unit) => some PUnit.unit) PUnit.unit }

def Turing.idComputableInTime {α : Type} (ea : Computability.FinEncoding α) : Turing.TM2ComputableInTime ea ea id

A proof that the identity map on α is computable in time.

Equations

• Turing.idComputableInTime ea = Turing.TM2ComputableInPolyTime.toTM2ComputableInTime (Turing.idComputableInPolyTime ea)

instance Turing.inhabitedTM2ComputableInTime : Inhabited (Turing.TM2ComputableInTime Computability.finEncodingBoolBool Computability.finEncodingBoolBool id)

Equations

• Turing.inhabitedTM2ComputableInTime = { default := Turing.idComputableInTime default }

def Turing.idComputable {α : Type} (ea : Computability.FinEncoding α) : Turing.TM2Computable ea ea id

A proof that the identity map on α is computable.

Equations

• Turing.idComputable ea = Turing.TM2ComputableInTime.toTM2Computable (Turing.idComputableInTime ea)

instance Turing.inhabitedTM2Computable : Inhabited (Turing.TM2Computable Computability.finEncodingBoolBool Computability.finEncodingBoolBool id)

Equations

• Turing.inhabitedTM2Computable = { default := Turing.idComputable default }

instance Turing.inhabitedTM2ComputableAux : Inhabited (Turing.TM2ComputableAux Bool Bool)

Equations

• Turing.inhabitedTM2ComputableAux = { default := default.toTM2ComputableAux }