Changes since the initial port

The following section lists changes to this file in mathlib3 and mathlib4 that occured after the initial port. Most recent changes are shown first. Hovering over a commit will show all commits associated with the same mathlib3 commit.

Changes in mathlib3

6f9cb03e

(last sync)

Changes in mathlib3port

mathlib3

mathlib3port

8eb9c42d

bump to nightly-2024-04-07-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/65a1391a0106c9204fe45bc73a039f056558cb83

b03b8656

Diff

@@ -5,8 +5,8 @@ Authors: Pim Spelier, Daan van Gent
 -/
 import Computability.Encoding
 import Computability.TuringMachine
-import Data.Polynomial.Basic
-import Data.Polynomial.Eval
+import Algebra.Polynomial.Basic
+import Algebra.Polynomial.Eval
 
 #align_import computability.tm_computable from "leanprover-community/mathlib"@"8eb9c42d4d34c77f6ee84ea766ae4070233a973c"

8eb9c42d

bump to nightly-2023-09-24-06

mathlib commit https://github.com/leanprover-community/mathlib/commit/ce64cd319bb6b3e82f31c2d38e79080d377be451

5655435f

Diff

@@ -3,10 +3,10 @@ Copyright (c) 2020 Pim Spelier, Daan van Gent. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Pim Spelier, Daan van Gent
 -/
-import Mathbin.Computability.Encoding
-import Mathbin.Computability.TuringMachine
-import Mathbin.Data.Polynomial.Basic
-import Mathbin.Data.Polynomial.Eval
+import Computability.Encoding
+import Computability.TuringMachine
+import Data.Polynomial.Basic
+import Data.Polynomial.Eval
 
 #align_import computability.tm_computable from "leanprover-community/mathlib"@"8eb9c42d4d34c77f6ee84ea766ae4070233a973c"

8eb9c42d

bump to nightly-2023-07-20-09

mathlib commit https://github.com/leanprover-community/mathlib/commit/8ea5598db6caeddde6cb734aa179cc2408dbd345

9c56d0dd

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2020 Pim Spelier, Daan van Gent. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Pim Spelier, Daan van Gent
-
-! This file was ported from Lean 3 source module computability.tm_computable
-! leanprover-community/mathlib commit 8eb9c42d4d34c77f6ee84ea766ae4070233a973c
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathbin.Computability.Encoding
 import Mathbin.Computability.TuringMachine
 import Mathbin.Data.Polynomial.Basic
 import Mathbin.Data.Polynomial.Eval
 
+#align_import computability.tm_computable from "leanprover-community/mathlib"@"8eb9c42d4d34c77f6ee84ea766ae4070233a973c"
+
 /-!
 # Computable functions

8eb9c42d

bump to nightly-2023-06-01-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/cca40788df1b8755d5baf17ab2f27dacc2e17acb

b9c87c70

Diff

@@ -85,7 +85,8 @@ instance : Inhabited tm.σ :=
 #print Turing.FinTM2.Stmt /-
 /-- The type of statements (functions) corresponding to this TM. -/
 def Stmt : Type :=
-  Turing.TM2.Stmt tm.Γ tm.Λ tm.σ deriving Inhabited
+  Turing.TM2.Stmt tm.Γ tm.Λ tm.σ
+deriving Inhabited
 #align turing.fin_tm2.stmt Turing.FinTM2.Stmt
 -/
 
@@ -154,7 +155,7 @@ structure EvalsTo {σ : Type _} (f : σ → Option σ) (a : σ) (b : Option σ)
 /-- 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. -/
 structure EvalsToInTime {σ : Type _} (f : σ → Option σ) (a : σ) (b : Option σ) (m : ℕ) extends
-  EvalsTo f a b where
+    EvalsTo f a b where
   steps_le_m : steps ≤ m
 #align turing.evals_to_in_time Turing.EvalsToInTime
 -/
@@ -230,7 +231,7 @@ structure TM2ComputableAux (Γ₀ Γ₁ : Type) where
 #print Turing.TM2Computable /-
 /-- A Turing machine + a proof it outputs f. -/
 structure TM2Computable {α β : Type} (ea : FinEncoding α) (eb : FinEncoding β) (f : α → β) extends
-  TM2ComputableAux ea.Γ eb.Γ where
+    TM2ComputableAux ea.Γ eb.Γ where
   outputsFun :
     ∀ a,
       TM2Outputs tm (List.map input_alphabet.invFun (ea.encode a))
@@ -241,7 +242,7 @@ structure TM2Computable {α β : Type} (ea : FinEncoding α) (eb : FinEncoding 
 #print Turing.TM2ComputableInTime /-
 /-- A Turing machine + a time function + a proof it outputs f in at most time(len(input)) steps. -/
 structure TM2ComputableInTime {α β : Type} (ea : FinEncoding α) (eb : FinEncoding β)
-  (f : α → β) extends TM2ComputableAux ea.Γ eb.Γ where
+    (f : α → β) extends TM2ComputableAux ea.Γ eb.Γ where
   time : ℕ → ℕ
   outputsFun :
     ∀ a,
@@ -255,7 +256,7 @@ structure TM2ComputableInTime {α β : Type} (ea : FinEncoding α) (eb : FinEnco
 /-- A Turing machine + a polynomial time function + a proof it outputs f in at most time(len(input))
 steps. -/
 structure TM2ComputableInPolyTime {α β : Type} (ea : FinEncoding α) (eb : FinEncoding β)
-  (f : α → β) extends TM2ComputableAux ea.Γ eb.Γ where
+    (f : α → β) extends TM2ComputableAux ea.Γ eb.Γ where
   time : Polynomial ℕ
   outputsFun :
     ∀ a,

8eb9c42d

bump to nightly-2023-04-20-02

mathlib commit https://github.com/leanprover-community/mathlib/commit/730c6d4cab72b9d84fcfb9e95e8796e9cd8f40ba

70125a69

Diff

@@ -4,7 +4,7 @@ Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Pim Spelier, Daan van Gent
 
 ! This file was ported from Lean 3 source module computability.tm_computable
-! leanprover-community/mathlib commit 6f9cb03e8a39ea345796a13c6639cb330e50869b
+! leanprover-community/mathlib commit 8eb9c42d4d34c77f6ee84ea766ae4070233a973c
 ! Please do not edit these lines, except to modify the commit id
 ! if you have ported upstream changes.
 -/
@@ -16,6 +16,9 @@ import Mathbin.Data.Polynomial.Eval
 /-!
 # Computable functions
 
+> THIS FILE IS SYNCHRONIZED WITH MATHLIB4.
+> Any changes to this file require a corresponding PR to mathlib4.
+
 This file contains the definition of a Turing machine with some finiteness conditions
 (bundling the definition of TM2 in turing_machine.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)

6f9cb03e

bump to nightly-2023-04-18-08

mathlib commit https://github.com/leanprover-community/mathlib/commit/49b7f94aab3a3bdca1f9f34c5d818afb253b3993

bba1f0fa

Diff

@@ -40,10 +40,11 @@ open Computability
 
 namespace Turing
 
+#print Turing.FinTM2 /-
 /-- A bundled TM2 (an equivalent of the classical Turing machine, defined starting from
 the namespace `turing.TM2` in `turing_machine.lean`), with an input and output stack,
  a main function, an initial state and some finiteness guarantees. -/
-structure FinTm2 where
+structure FinTM2 where
   {K : Type}
   [kDecidableEq : DecidableEq K]
   [kFin : Fintype K]
@@ -62,14 +63,15 @@ structure FinTm2 where
   [σFin : Fintype σ]
   [Γk₀Fin : Fintype (Γ k₀)]
   m : Λ → Turing.TM2.Stmt Γ Λ σ
-#align turing.fin_tm2 Turing.FinTm2
+#align turing.fin_tm2 Turing.FinTM2
+-/
 
 -- the program itself, i.e. one function for every function label
 namespace FinTm2
 
 section
 
-variable (tm : FinTm2)
+variable (tm : FinTM2)
 
 instance : DecidableEq tm.K :=
   tm.kDecidableEq
@@ -77,32 +79,41 @@ instance : DecidableEq tm.K :=
 instance : Inhabited tm.σ :=
   ⟨tm.initialState⟩
 
+#print Turing.FinTM2.Stmt /-
 /-- The type of statements (functions) corresponding to this TM. -/
 def Stmt : Type :=
   Turing.TM2.Stmt tm.Γ tm.Λ tm.σ deriving Inhabited
-#align turing.fin_tm2.stmt Turing.FinTm2.Stmt
+#align turing.fin_tm2.stmt Turing.FinTM2.Stmt
+-/
 
+#print Turing.FinTM2.Cfg /-
 /-- The type of configurations (functions) corresponding to this TM. -/
 def Cfg : Type :=
   Turing.TM2.Cfg tm.Γ tm.Λ tm.σ
-#align turing.fin_tm2.cfg Turing.FinTm2.Cfg
+#align turing.fin_tm2.cfg Turing.FinTM2.Cfg
+-/
 
+#print Turing.FinTM2.inhabitedCfg /-
 instance inhabitedCfg : Inhabited (Cfg tm) :=
   Turing.TM2.Cfg.inhabited _ _ _
-#align turing.fin_tm2.inhabited_cfg Turing.FinTm2.inhabitedCfg
+#align turing.fin_tm2.inhabited_cfg Turing.FinTM2.inhabitedCfg
+-/
 
+#print Turing.FinTM2.step /-
 /-- The step function corresponding to this TM. -/
 @[simp]
 def step : tm.Cfg → Option tm.Cfg :=
   Turing.TM2.step tm.m
-#align turing.fin_tm2.step Turing.FinTm2.step
+#align turing.fin_tm2.step Turing.FinTM2.step
+-/
 
 end
 
 end FinTm2
 
+#print Turing.initList /-
 /-- The initial configuration corresponding to a list in the input alphabet. -/
-def initList (tm : FinTm2) (s : List (tm.Γ tm.k₀)) : tm.Cfg
+def initList (tm : FinTM2) (s : List (tm.Γ tm.k₀)) : tm.Cfg
     where
   l := Option.some tm.main
   var := tm.initialState
@@ -110,9 +121,11 @@ def initList (tm : FinTm2) (s : List (tm.Γ tm.k₀)) : tm.Cfg
     @dite (List (tm.Γ k)) (k = tm.k₀) (tm.kDecidableEq k tm.k₀) (fun h => by rw [h]; exact s)
       fun _ => []
 #align turing.init_list Turing.initList
+-/
 
+#print Turing.haltList /-
 /-- The final configuration corresponding to a list in the output alphabet. -/
-def haltList (tm : FinTm2) (s : List (tm.Γ tm.k₁)) : tm.Cfg
+def haltList (tm : FinTM2) (s : List (tm.Γ tm.k₁)) : tm.Cfg
     where
   l := Option.none
   var := tm.initialState
@@ -120,14 +133,18 @@ def haltList (tm : FinTm2) (s : List (tm.Γ tm.k₁)) : tm.Cfg
     @dite (List (tm.Γ k)) (k = tm.k₁) (tm.kDecidableEq k tm.k₁) (fun h => by rw [h]; exact s)
       fun _ => []
 #align turing.halt_list Turing.haltList
+-/
 
+#print Turing.EvalsTo /-
 /-- A "proof" of the fact that f eventually reaches b when repeatedly evaluated on a,
 remembering the number of steps it takes. -/
 structure EvalsTo {σ : Type _} (f : σ → Option σ) (a : σ) (b : Option σ) where
   steps : ℕ
   evals_in_steps : (flip bind f^[steps]) a = b
 #align turing.evals_to Turing.EvalsTo
+-/
 
+#print Turing.EvalsToInTime /-
 -- note: this cannot currently be used in `calc`, as the last two arguments must be `a` and `b`.
 -- If this is desired, this argument order can be changed, but this spelling is I think the most
 -- natural, so there is a trade-off that needs to be made here. A notation can get around this.
@@ -137,26 +154,34 @@ structure EvalsToInTime {σ : Type _} (f : σ → Option σ) (a : σ) (b : Optio
   EvalsTo f a b where
   steps_le_m : steps ≤ m
 #align turing.evals_to_in_time Turing.EvalsToInTime
+-/
 
+#print Turing.EvalsTo.refl /-
 /-- Reflexivity of `evals_to` in 0 steps. -/
 @[refl]
 def EvalsTo.refl {σ : Type _} (f : σ → Option σ) (a : σ) : EvalsTo f a a :=
   ⟨0, rfl⟩
 #align turing.evals_to.refl Turing.EvalsTo.refl
+-/
 
+#print Turing.EvalsTo.trans /-
 /-- Transitivity of `evals_to` in the sum of the numbers of steps. -/
 @[trans]
 def EvalsTo.trans {σ : Type _} (f : σ → Option σ) (a : σ) (b : σ) (c : Option σ)
     (h₁ : EvalsTo f a b) (h₂ : EvalsTo f b c) : EvalsTo f a c :=
   ⟨h₂.steps + h₁.steps, by rw [Function.iterate_add_apply, h₁.evals_in_steps, h₂.evals_in_steps]⟩
 #align turing.evals_to.trans Turing.EvalsTo.trans
+-/
 
+#print Turing.EvalsToInTime.refl /-
 /-- Reflexivity of `evals_to_in_time` in 0 steps. -/
 @[refl]
 def EvalsToInTime.refl {σ : Type _} (f : σ → Option σ) (a : σ) : EvalsToInTime f a a 0 :=
   ⟨EvalsTo.refl f a, le_refl 0⟩
 #align turing.evals_to_in_time.refl Turing.EvalsToInTime.refl
+-/
 
+#print Turing.EvalsToInTime.trans /-
 /-- Transitivity of `evals_to_in_time` in the sum of the numbers of steps. -/
 @[trans]
 def EvalsToInTime.trans {σ : Type _} (f : σ → Option σ) (m₁ : ℕ) (m₂ : ℕ) (a : σ) (b : σ)
@@ -164,81 +189,101 @@ def EvalsToInTime.trans {σ : Type _} (f : σ → Option σ) (m₁ : ℕ) (m₂
     EvalsToInTime f a c (m₂ + m₁) :=
   ⟨EvalsTo.trans f a b c h₁.toEvalsTo h₂.toEvalsTo, add_le_add h₂.steps_le_m h₁.steps_le_m⟩
 #align turing.evals_to_in_time.trans Turing.EvalsToInTime.trans
+-/
 
+#print Turing.TM2Outputs /-
 /-- A proof of tm outputting l' when given l. -/
-def Tm2Outputs (tm : FinTm2) (l : List (tm.Γ tm.k₀)) (l' : Option (List (tm.Γ tm.k₁))) :=
+def TM2Outputs (tm : FinTM2) (l : List (tm.Γ tm.k₀)) (l' : Option (List (tm.Γ tm.k₁))) :=
   EvalsTo tm.step (initList tm l) ((Option.map (haltList tm)) l')
-#align turing.tm2_outputs Turing.Tm2Outputs
+#align turing.tm2_outputs Turing.TM2Outputs
+-/
 
+#print Turing.TM2OutputsInTime /-
 /-- A proof of tm outputting l' when given l in at most m steps. -/
-def Tm2OutputsInTime (tm : FinTm2) (l : List (tm.Γ tm.k₀)) (l' : Option (List (tm.Γ tm.k₁)))
+def TM2OutputsInTime (tm : FinTM2) (l : List (tm.Γ tm.k₀)) (l' : Option (List (tm.Γ tm.k₁)))
     (m : ℕ) :=
   EvalsToInTime tm.step (initList tm l) ((Option.map (haltList tm)) l') m
-#align turing.tm2_outputs_in_time Turing.Tm2OutputsInTime
+#align turing.tm2_outputs_in_time Turing.TM2OutputsInTime
+-/
 
+#print Turing.TM2OutputsInTime.toTM2Outputs /-
 /-- The forgetful map, forgetting the upper bound on the number of steps. -/
-def Tm2OutputsInTime.toTm2Outputs {tm : FinTm2} {l : List (tm.Γ tm.k₀)}
-    {l' : Option (List (tm.Γ tm.k₁))} {m : ℕ} (h : Tm2OutputsInTime tm l l' m) :
-    Tm2Outputs tm l l' :=
+def TM2OutputsInTime.toTM2Outputs {tm : FinTM2} {l : List (tm.Γ tm.k₀)}
+    {l' : Option (List (tm.Γ tm.k₁))} {m : ℕ} (h : TM2OutputsInTime tm l l' m) :
+    TM2Outputs tm l l' :=
   h.toEvalsTo
-#align turing.tm2_outputs_in_time.to_tm2_outputs Turing.Tm2OutputsInTime.toTm2Outputs
+#align turing.tm2_outputs_in_time.to_tm2_outputs Turing.TM2OutputsInTime.toTM2Outputs
+-/
 
+#print Turing.TM2ComputableAux /-
 /-- A Turing machine with input alphabet equivalent to Γ₀ and output alphabet equivalent to Γ₁. -/
-structure Tm2ComputableAux (Γ₀ Γ₁ : Type) where
-  tm : FinTm2
+structure TM2ComputableAux (Γ₀ Γ₁ : Type) where
+  tm : FinTM2
   inputAlphabet : tm.Γ tm.k₀ ≃ Γ₀
   outputAlphabet : tm.Γ tm.k₁ ≃ Γ₁
-#align turing.tm2_computable_aux Turing.Tm2ComputableAux
+#align turing.tm2_computable_aux Turing.TM2ComputableAux
+-/
 
+#print Turing.TM2Computable /-
 /-- A Turing machine + a proof it outputs f. -/
-structure Tm2Computable {α β : Type} (ea : FinEncoding α) (eb : FinEncoding β) (f : α → β) extends
-  Tm2ComputableAux ea.Γ eb.Γ where
+structure TM2Computable {α β : Type} (ea : FinEncoding α) (eb : FinEncoding β) (f : α → β) extends
+  TM2ComputableAux ea.Γ eb.Γ where
   outputsFun :
     ∀ a,
-      Tm2Outputs tm (List.map input_alphabet.invFun (ea.encode a))
+      TM2Outputs tm (List.map input_alphabet.invFun (ea.encode a))
         (Option.some ((List.map output_alphabet.invFun) (eb.encode (f a))))
-#align turing.tm2_computable Turing.Tm2Computable
+#align turing.tm2_computable Turing.TM2Computable
+-/
 
+#print Turing.TM2ComputableInTime /-
 /-- A Turing machine + a time function + a proof it outputs f in at most time(len(input)) steps. -/
-structure Tm2ComputableInTime {α β : Type} (ea : FinEncoding α) (eb : FinEncoding β)
-  (f : α → β) extends Tm2ComputableAux ea.Γ eb.Γ where
+structure TM2ComputableInTime {α β : Type} (ea : FinEncoding α) (eb : FinEncoding β)
+  (f : α → β) extends TM2ComputableAux ea.Γ eb.Γ where
   time : ℕ → ℕ
   outputsFun :
     ∀ a,
-      Tm2OutputsInTime tm (List.map input_alphabet.invFun (ea.encode a))
+      TM2OutputsInTime tm (List.map input_alphabet.invFun (ea.encode a))
         (Option.some ((List.map output_alphabet.invFun) (eb.encode (f a))))
         (time (ea.encode a).length)
-#align turing.tm2_computable_in_time Turing.Tm2ComputableInTime
+#align turing.tm2_computable_in_time Turing.TM2ComputableInTime
+-/
 
+#print Turing.TM2ComputableInPolyTime /-
 /-- A Turing machine + a polynomial time function + a proof it outputs f in at most time(len(input))
 steps. -/
-structure Tm2ComputableInPolyTime {α β : Type} (ea : FinEncoding α) (eb : FinEncoding β)
-  (f : α → β) extends Tm2ComputableAux ea.Γ eb.Γ where
+structure TM2ComputableInPolyTime {α β : Type} (ea : FinEncoding α) (eb : FinEncoding β)
+  (f : α → β) extends TM2ComputableAux ea.Γ eb.Γ where
   time : Polynomial ℕ
   outputsFun :
     ∀ a,
-      Tm2OutputsInTime tm (List.map input_alphabet.invFun (ea.encode a))
+      TM2OutputsInTime tm (List.map input_alphabet.invFun (ea.encode a))
         (Option.some ((List.map output_alphabet.invFun) (eb.encode (f a))))
         (time.eval (ea.encode a).length)
-#align turing.tm2_computable_in_poly_time Turing.Tm2ComputableInPolyTime
+#align turing.tm2_computable_in_poly_time Turing.TM2ComputableInPolyTime
+-/
 
+#print Turing.TM2ComputableInTime.toTM2Computable /-
 /-- A forgetful map, forgetting the time bound on the number of steps. -/
-def Tm2ComputableInTime.toTm2Computable {α β : Type} {ea : FinEncoding α} {eb : FinEncoding β}
-    {f : α → β} (h : Tm2ComputableInTime ea eb f) : Tm2Computable ea eb f :=
-  ⟨h.toTm2ComputableAux, fun a => Tm2OutputsInTime.toTm2Outputs (h.outputsFun a)⟩
-#align turing.tm2_computable_in_time.to_tm2_computable Turing.Tm2ComputableInTime.toTm2Computable
+def TM2ComputableInTime.toTM2Computable {α β : Type} {ea : FinEncoding α} {eb : FinEncoding β}
+    {f : α → β} (h : TM2ComputableInTime ea eb f) : TM2Computable ea eb f :=
+  ⟨h.toTm2ComputableAux, fun a => TM2OutputsInTime.toTM2Outputs (h.outputsFun a)⟩
+#align turing.tm2_computable_in_time.to_tm2_computable Turing.TM2ComputableInTime.toTM2Computable
+-/
 
+#print Turing.TM2ComputableInPolyTime.toTM2ComputableInTime /-
 /-- A forgetful map, forgetting that the time function is polynomial. -/
-def Tm2ComputableInPolyTime.toTm2ComputableInTime {α β : Type} {ea : FinEncoding α}
-    {eb : FinEncoding β} {f : α → β} (h : Tm2ComputableInPolyTime ea eb f) :
-    Tm2ComputableInTime ea eb f :=
+def TM2ComputableInPolyTime.toTM2ComputableInTime {α β : Type} {ea : FinEncoding α}
+    {eb : FinEncoding β} {f : α → β} (h : TM2ComputableInPolyTime ea eb f) :
+    TM2ComputableInTime ea eb f :=
   ⟨h.toTm2ComputableAux, fun n => h.time.eval n, h.outputsFun⟩
-#align turing.tm2_computable_in_poly_time.to_tm2_computable_in_time Turing.Tm2ComputableInPolyTime.toTm2ComputableInTime
+#align turing.tm2_computable_in_poly_time.to_tm2_computable_in_time Turing.TM2ComputableInPolyTime.toTM2ComputableInTime
+-/
 
 open Turing.TM2.Stmt
 
+#print Turing.idComputer /-
 /-- A Turing machine computing the identity on α. -/
-def idComputer {α : Type} (ea : FinEncoding α) : FinTm2
+def idComputer {α : Type} (ea : FinEncoding α) : FinTM2
     where
   K := Unit
   k₀ := ⟨⟩
@@ -251,15 +296,19 @@ def idComputer {α : Type} (ea : FinEncoding α) : FinTm2
   Γk₀Fin := ea.ΓFin
   m _ := halt
 #align turing.id_computer Turing.idComputer
+-/
 
-instance inhabitedFinTm2 : Inhabited FinTm2 :=
+#print Turing.inhabitedFinTM2 /-
+instance inhabitedFinTM2 : Inhabited FinTM2 :=
   ⟨idComputer Computability.inhabitedFinEncoding.default⟩
-#align turing.inhabited_fin_tm2 Turing.inhabitedFinTm2
+#align turing.inhabited_fin_tm2 Turing.inhabitedFinTM2
+-/
 
 noncomputable section
 
+#print Turing.idComputableInPolyTime /-
 /-- A proof that the identity map on α is computable in polytime. -/
-def idComputableInPolyTime {α : Type} (ea : FinEncoding α) : @Tm2ComputableInPolyTime α α ea ea id
+def idComputableInPolyTime {α : Type} (ea : FinEncoding α) : @TM2ComputableInPolyTime α α ea ea id
     where
   tm := idComputer ea
   inputAlphabet := Equiv.cast rfl
@@ -270,58 +319,79 @@ def idComputableInPolyTime {α : Type} (ea : FinEncoding α) : @Tm2ComputableInP
       evals_in_steps := rfl
       steps_le_m := by simp only [Polynomial.eval_one] }
 #align turing.id_computable_in_poly_time Turing.idComputableInPolyTime
+-/
 
-instance inhabitedTm2ComputableInPolyTime :
-    Inhabited (Tm2ComputableInPolyTime (default : FinEncoding Bool) default id) :=
+#print Turing.inhabitedTM2ComputableInPolyTime /-
+instance inhabitedTM2ComputableInPolyTime :
+    Inhabited (TM2ComputableInPolyTime (default : FinEncoding Bool) default id) :=
   ⟨idComputableInPolyTime Computability.inhabitedFinEncoding.default⟩
-#align turing.inhabited_tm2_computable_in_poly_time Turing.inhabitedTm2ComputableInPolyTime
+#align turing.inhabited_tm2_computable_in_poly_time Turing.inhabitedTM2ComputableInPolyTime
+-/
 
-instance inhabitedTm2OutputsInTime :
+#print Turing.inhabitedTM2OutputsInTime /-
+instance inhabitedTM2OutputsInTime :
     Inhabited
-      (Tm2OutputsInTime (idComputer finEncodingBoolBool) (List.map (Equiv.cast rfl).invFun [false])
+      (TM2OutputsInTime (idComputer finEncodingBoolBool) (List.map (Equiv.cast rfl).invFun [false])
         (some (List.map (Equiv.cast rfl).invFun [false])) _) :=
   ⟨(idComputableInPolyTime finEncodingBoolBool).outputsFun false⟩
-#align turing.inhabited_tm2_outputs_in_time Turing.inhabitedTm2OutputsInTime
+#align turing.inhabited_tm2_outputs_in_time Turing.inhabitedTM2OutputsInTime
+-/
 
-instance inhabitedTm2Outputs :
+#print Turing.inhabitedTM2Outputs /-
+instance inhabitedTM2Outputs :
     Inhabited
-      (Tm2Outputs (idComputer finEncodingBoolBool) (List.map (Equiv.cast rfl).invFun [false])
+      (TM2Outputs (idComputer finEncodingBoolBool) (List.map (Equiv.cast rfl).invFun [false])
         (some (List.map (Equiv.cast rfl).invFun [false]))) :=
-  ⟨Tm2OutputsInTime.toTm2Outputs Turing.inhabitedTm2OutputsInTime.default⟩
-#align turing.inhabited_tm2_outputs Turing.inhabitedTm2Outputs
+  ⟨TM2OutputsInTime.toTM2Outputs Turing.inhabitedTM2OutputsInTime.default⟩
+#align turing.inhabited_tm2_outputs Turing.inhabitedTM2Outputs
+-/
 
+#print Turing.inhabitedEvalsToInTime /-
 instance inhabitedEvalsToInTime :
     Inhabited (EvalsToInTime (fun _ : Unit => some ⟨⟩) ⟨⟩ (some ⟨⟩) 0) :=
   ⟨EvalsToInTime.refl _ _⟩
 #align turing.inhabited_evals_to_in_time Turing.inhabitedEvalsToInTime
+-/
 
-instance inhabitedTm2EvalsTo : Inhabited (EvalsTo (fun _ : Unit => some ⟨⟩) ⟨⟩ (some ⟨⟩)) :=
+#print Turing.inhabitedTM2EvalsTo /-
+instance inhabitedTM2EvalsTo : Inhabited (EvalsTo (fun _ : Unit => some ⟨⟩) ⟨⟩ (some ⟨⟩)) :=
   ⟨EvalsTo.refl _ _⟩
-#align turing.inhabited_tm2_evals_to Turing.inhabitedTm2EvalsTo
+#align turing.inhabited_tm2_evals_to Turing.inhabitedTM2EvalsTo
+-/
 
+#print Turing.idComputableInTime /-
 /-- A proof that the identity map on α is computable in time. -/
-def idComputableInTime {α : Type} (ea : FinEncoding α) : @Tm2ComputableInTime α α ea ea id :=
-  Tm2ComputableInPolyTime.toTm2ComputableInTime <| idComputableInPolyTime ea
+def idComputableInTime {α : Type} (ea : FinEncoding α) : @TM2ComputableInTime α α ea ea id :=
+  TM2ComputableInPolyTime.toTM2ComputableInTime <| idComputableInPolyTime ea
 #align turing.id_computable_in_time Turing.idComputableInTime
+-/
 
-instance inhabitedTm2ComputableInTime :
-    Inhabited (Tm2ComputableInTime finEncodingBoolBool finEncodingBoolBool id) :=
+#print Turing.inhabitedTM2ComputableInTime /-
+instance inhabitedTM2ComputableInTime :
+    Inhabited (TM2ComputableInTime finEncodingBoolBool finEncodingBoolBool id) :=
   ⟨idComputableInTime Computability.inhabitedFinEncoding.default⟩
-#align turing.inhabited_tm2_computable_in_time Turing.inhabitedTm2ComputableInTime
+#align turing.inhabited_tm2_computable_in_time Turing.inhabitedTM2ComputableInTime
+-/
 
+#print Turing.idComputable /-
 /-- A proof that the identity map on α is computable. -/
-def idComputable {α : Type} (ea : FinEncoding α) : @Tm2Computable α α ea ea id :=
-  Tm2ComputableInTime.toTm2Computable <| idComputableInTime ea
+def idComputable {α : Type} (ea : FinEncoding α) : @TM2Computable α α ea ea id :=
+  TM2ComputableInTime.toTM2Computable <| idComputableInTime ea
 #align turing.id_computable Turing.idComputable
+-/
 
-instance inhabitedTm2Computable :
-    Inhabited (Tm2Computable finEncodingBoolBool finEncodingBoolBool id) :=
+#print Turing.inhabitedTM2Computable /-
+instance inhabitedTM2Computable :
+    Inhabited (TM2Computable finEncodingBoolBool finEncodingBoolBool id) :=
   ⟨idComputable Computability.inhabitedFinEncoding.default⟩
-#align turing.inhabited_tm2_computable Turing.inhabitedTm2Computable
+#align turing.inhabited_tm2_computable Turing.inhabitedTM2Computable
+-/
 
-instance inhabitedTm2ComputableAux : Inhabited (Tm2ComputableAux Bool Bool) :=
-  ⟨(default : Tm2Computable finEncodingBoolBool finEncodingBoolBool id).toTm2ComputableAux⟩
-#align turing.inhabited_tm2_computable_aux Turing.inhabitedTm2ComputableAux
+#print Turing.inhabitedTM2ComputableAux /-
+instance inhabitedTM2ComputableAux : Inhabited (TM2ComputableAux Bool Bool) :=
+  ⟨(default : TM2Computable finEncodingBoolBool finEncodingBoolBool id).toTm2ComputableAux⟩
+#align turing.inhabited_tm2_computable_aux Turing.inhabitedTM2ComputableAux
+-/
 
 end Turing

6f9cb03e

bump to nightly-2023-02-21-16

mathlib commit https://github.com/leanprover-community/mathlib/commit/bd9851ca476957ea4549eb19b40e7b5ade9428cc

1107b979

Changes in mathlib4

mathlib3

mathlib4

6f9cb03e

move(Polynomial): Move out of Data (#11751)

Polynomial and MvPolynomial are algebraic objects, hence should be under Algebra (or at least not under Data)

56e439ec

Diff

@@ -3,10 +3,10 @@ Copyright (c) 2020 Pim Spelier, Daan van Gent. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Pim Spelier, Daan van Gent
 -/
+import Mathlib.Algebra.Polynomial.Basic
+import Mathlib.Algebra.Polynomial.Eval
 import Mathlib.Computability.Encoding
 import Mathlib.Computability.TuringMachine
-import Mathlib.Data.Polynomial.Basic
-import Mathlib.Data.Polynomial.Eval
 
 #align_import computability.tm_computable from "leanprover-community/mathlib"@"6f9cb03e8a39ea345796a13c6639cb330e50869b"

6f9cb03e

chore: bump to v4.3.0-rc2 (#8366)

PR contents

This is the supremum of

#8284
#8056
#8023
#8332
#8226 (already approved)
#7834 (already approved)

along with some minor fixes from failures on nightly-testing as Mathlib master is merged into it.

Note that some PRs for changes that are already compatible with the current toolchain and will be necessary have already been split out: #8380.

I am hopeful that in future we will be able to progressively merge adaptation PRs into a bump/v4.X.0 branch, so we never end up with a "big merge" like this. However one of these adaptation PRs (#8056) predates my new scheme for combined CI, and it wasn't possible to keep that PR viable in the meantime.

Lean PRs involved in this bump

In particular this includes adjustments for the Lean PRs

leanprover/lean4#2778

We can get rid of all the

local macro_rules | `($x ^ $y) => `(HPow.hPow $x $y) -- Porting note: See issue [lean4#2220](https://github.com/leanprover/lean4/pull/2220)

macros across Mathlib (and in any projects that want to write natural number powers of reals).

leanprover/lean4#2722

Changes the default behaviour of simp to (config := {decide := false}). This makes simp (and consequentially norm_num) less powerful, but also more consistent, and less likely to blow up in long failures. This requires a variety of changes: changing some previously by simp or norm_num to decide or rfl, or adding (config := {decide := true}).

leanprover/lean4#2783

This changed the behaviour of simp so that simp [f] will only unfold "fully applied" occurrences of f. The old behaviour can be recovered with simp (config := { unfoldPartialApp := true }). We may in future add a syntax for this, e.g. simp [!f]; please provide feedback! In the meantime, we have made the following changes:

switching to using explicit lemmas that have the intended level of application
(config := { unfoldPartialApp := true }) in some places, to recover the old behaviour
Using @[eqns] to manually adjust the equation lemmas for a particular definition, recovering the old behaviour just for that definition. See #8371, where we do this for Function.comp and Function.flip.

This change in Lean may require further changes down the line (e.g. adding the !f syntax, and/or upstreaming the special treatment for Function.comp and Function.flip, and/or removing this special treatment). Please keep an open and skeptical mind about these changes!

Co-authored-by: leanprover-community-mathlib4-bot <leanprover-community-mathlib4-bot@users.noreply.github.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com> Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Mauricio Collares <mauricio@collares.org>

40b64f79

Diff

@@ -260,7 +260,7 @@ def idComputableInPolyTime {α : Type} (ea : FinEncoding α) :
   outputsFun _ :=
     { steps := 1
       evals_in_steps := rfl
-      steps_le_m := by simp only [Polynomial.eval_one] }
+      steps_le_m := by simp only [Polynomial.eval_one, le_refl] }
 #align turing.id_computable_in_poly_time Turing.idComputableInPolyTime
 
 instance inhabitedTM2ComputableInPolyTime :

6f9cb03e

chore: banish Type _ and Sort _ (#6499)

We remove all possible occurences of Type _ and Sort _ in favor of Type* and Sort*.

This has nice performance benefits.

32de3f67

Diff

@@ -116,7 +116,7 @@ def haltList (tm : FinTM2) (s : List (tm.Γ tm.k₁)) : tm.Cfg where
 
 /-- A "proof" of the fact that f eventually reaches b when repeatedly evaluated on a,
 remembering the number of steps it takes. -/
-structure EvalsTo {σ : Type _} (f : σ → Option σ) (a : σ) (b : Option σ) where
+structure EvalsTo {σ : Type*} (f : σ → Option σ) (a : σ) (b : Option σ) where
   steps : ℕ
   evals_in_steps : (flip bind f)^[steps] a = b
 #align turing.evals_to Turing.EvalsTo
@@ -126,33 +126,33 @@ structure EvalsTo {σ : Type _} (f : σ → Option σ) (a : σ) (b : Option σ)
 -- natural, so there is a trade-off that needs to be made here. A notation can get around this.
 /-- 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. -/
-structure EvalsToInTime {σ : Type _} (f : σ → Option σ) (a : σ) (b : Option σ) (m : ℕ) extends
+structure EvalsToInTime {σ : Type*} (f : σ → Option σ) (a : σ) (b : Option σ) (m : ℕ) extends
   EvalsTo f a b where
   steps_le_m : steps ≤ m
 #align turing.evals_to_in_time Turing.EvalsToInTime
 
 /-- Reflexivity of `EvalsTo` in 0 steps. -/
 -- @[refl] -- Porting note: `@[refl]` attribute only applies to lemmas proving `x ∼ x` in Lean4.
-def EvalsTo.refl {σ : Type _} (f : σ → Option σ) (a : σ) : EvalsTo f a a :=
+def EvalsTo.refl {σ : Type*} (f : σ → Option σ) (a : σ) : EvalsTo f a a :=
   ⟨0, rfl⟩
 #align turing.evals_to.refl Turing.EvalsTo.refl
 
 /-- Transitivity of `EvalsTo` in the sum of the numbers of steps. -/
 @[trans]
-def EvalsTo.trans {σ : Type _} (f : σ → Option σ) (a : σ) (b : σ) (c : Option σ)
+def EvalsTo.trans {σ : Type*} (f : σ → Option σ) (a : σ) (b : σ) (c : Option σ)
     (h₁ : EvalsTo f a b) (h₂ : EvalsTo f b c) : EvalsTo f a c :=
   ⟨h₂.steps + h₁.steps, by rw [Function.iterate_add_apply, h₁.evals_in_steps, h₂.evals_in_steps]⟩
 #align turing.evals_to.trans Turing.EvalsTo.trans
 
 /-- Reflexivity of `EvalsToInTime` in 0 steps. -/
 -- @[refl] -- Porting note: `@[refl]` attribute only applies to lemmas proving `x ∼ x` in Lean4.
-def EvalsToInTime.refl {σ : Type _} (f : σ → Option σ) (a : σ) : EvalsToInTime f a a 0 :=
+def EvalsToInTime.refl {σ : Type*} (f : σ → Option σ) (a : σ) : EvalsToInTime f a a 0 :=
   ⟨EvalsTo.refl f a, le_refl 0⟩
 #align turing.evals_to_in_time.refl Turing.EvalsToInTime.refl
 
 /-- Transitivity of `EvalsToInTime` in the sum of the numbers of steps. -/
 @[trans]
-def EvalsToInTime.trans {σ : Type _} (f : σ → Option σ) (m₁ : ℕ) (m₂ : ℕ) (a : σ) (b : σ)
+def EvalsToInTime.trans {σ : Type*} (f : σ → Option σ) (m₁ : ℕ) (m₂ : ℕ) (a : σ) (b : σ)
     (c : Option σ) (h₁ : EvalsToInTime f a b m₁) (h₂ : EvalsToInTime f b c m₂) :
     EvalsToInTime f a c (m₂ + m₁) :=
   ⟨EvalsTo.trans f a b c h₁.toEvalsTo h₂.toEvalsTo, add_le_add h₂.steps_le_m h₁.steps_le_m⟩

6f9cb03e

chore: script to replace headers with #align_import statements (#5979)

depends on: #5966

Co-authored-by: Eric Wieser <wieser.eric@gmail.com> Co-authored-by: Scott Morrison <scott.morrison@gmail.com>

89aa3a3b

Diff

@@ -2,17 +2,14 @@
 Copyright (c) 2020 Pim Spelier, Daan van Gent. All rights reserved.
 Released under Apache 2.0 license as described in the file LICENSE.
 Authors: Pim Spelier, Daan van Gent
-
-! This file was ported from Lean 3 source module computability.tm_computable
-! leanprover-community/mathlib commit 6f9cb03e8a39ea345796a13c6639cb330e50869b
-! Please do not edit these lines, except to modify the commit id
-! if you have ported upstream changes.
 -/
 import Mathlib.Computability.Encoding
 import Mathlib.Computability.TuringMachine
 import Mathlib.Data.Polynomial.Basic
 import Mathlib.Data.Polynomial.Eval
 
+#align_import computability.tm_computable from "leanprover-community/mathlib"@"6f9cb03e8a39ea345796a13c6639cb330e50869b"
+
 /-!
 # Computable functions

6f9cb03e

fix precedence of Nat.iterate (#5589)

bd2fff86

Diff

@@ -121,7 +121,7 @@ def haltList (tm : FinTM2) (s : List (tm.Γ tm.k₁)) : tm.Cfg where
 remembering the number of steps it takes. -/
 structure EvalsTo {σ : Type _} (f : σ → Option σ) (a : σ) (b : Option σ) where
   steps : ℕ
-  evals_in_steps : (flip bind f^[steps]) a = b
+  evals_in_steps : (flip bind f)^[steps] a = b
 #align turing.evals_to Turing.EvalsTo
 
 -- note: this cannot currently be used in `calc`, as the last two arguments must be `a` and `b`.

6f9cb03e

feat: port Computability.TMComputable (#2800)

Co-authored-by: Jeremy Tan Jie Rui <e0191785@u.nus.edu> Co-authored-by: Pol_tta <65514131+Ruben-VandeVelde@users.noreply.github.com> Co-authored-by: EmilieUthaiwat <emiliepathum@gmail.com> Co-authored-by: Jeremy Tan Jie Rui <reddeloostw@gmail.com> Co-authored-by: Scott Morrison <scott@tqft.net>

bb3869b8

`computability.tm_computable` ⟷ `Mathlib.Computability.TMComputable`

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

PR contents

Lean PRs involved in this bump

leanprover/lean4#2778

leanprover/lean4#2722

leanprover/lean4#2783

Dependencies 8 + 432

computability.tm_computable ⟷ Mathlib.Computability.TMComputable

Changes since the initial port

Changes in mathlib3

Changes in mathlib3port

Changes in mathlib4

PR contents

Lean PRs involved in this bump

leanprover/lean4#2778

leanprover/lean4#2722

leanprover/lean4#2783

Dependencies 8 + 432

`computability.tm_computable` ⟷ `Mathlib.Computability.TMComputable`