Theorems · Theorem · logic and foundations
Nat.Partrec.Code.fixed_point
∀ {f : Nat.Partrec.Code → Nat.Partrec.Code}, Computable f → ∃ c, (f c).eval = c.evalRoger's fixed-point theorem: any total, computable f has a fixed point.
That is, under the interpretation given by Nat.Partrec.Code.eval, there is a code c
such that c and f c have the same evaluation.
- Defined in
- Mathlib.Computability.PartrecCode
- Cited by
- 1 results in Mathlib
- Foundations
- Depth 100 from the axioms · uses propext, Classical.choice, Quot.sound
Around this declaration
Dashed lines are statement dependencies; solid lines are citations in proofs.
Cites43
Mathlib declarations this one mentions in its statement or cites explicitly in its proof. Plumbing is filtered out.
- DFunLike.coeproof · cited by 62,936
- Equiv.symmproof · cited by 3,681
- Partproof · cited by 325
- PFunstatement · cited by 207
- Encodable.encodeproof · cited by 118
- Part.someproof · cited by 111
- Computablestatement and proof · cited by 80
- Encodable.decodeproof · cited by 77
- Part.bindproof · cited by 70
- Nat.Partrec.Codestatement and proof · cited by 66
- Part.mapproof · cited by 65
- Nat.pairproof · cited by 62
Cited by1
Results whose statement or proof uses this declaration.
- Nat.Partrec.Code.fixed_point₂proof · cited by 1