Kleenes_Normal_Form_Theorem
Disprovedcomputabilityproofwikirecursion-theory
For each integer , there exists * a primitive recursive -ary relation ; * a primitive recursive function such that a partial function is recursive iff, for some and all
Preamble
import Mathlib.Computability.Partrec import Mathlib.Computability.Primrec
Formal statement
theorem Kleenes_Normal_Form_Theorem (f : ℕ →. ℕ) (hf : Nat.Partrec f) : ∃ (g : ℕ → ℕ) (h : ℕ → ℕ), Nat.Primrec g ∧ Nat.Primrec h ∧ ∀ n, f n = Nat.rfind (fun m => some (decide (g (Nat.pair n m) = 0))) := by sorry
Source