Partial recursive functions are Turing-computable
ProvedFamousTheorems.partrec_turing_computable_7aPartial recursive functions are Turing-computable. For every code of a partial recursive function on lists of natural numbers and every input list , the multi-stack Turing machine started in the configuration encoding halts exactly when is defined, and it halts in the configuration encoding the output .
This is the half of the Church–Turing correspondence stating that everything recursive is computable by a Turing machine. Together with the converse it shows that Turing machines and partial recursive functions define the same class of functions. The machine here is a single fixed universal machine, with the code given as part of its input.
Formalization note. Mathlib's Turing.PartrecToTM2.tr_eval. Turing.ToPartrec.Code is a code language for partial recursive functions on List ℕ. Turing.PartrecToTM2.tr is the transition function of a TM2 machine, which has finitely many stacks. StateTransition.eval runs a machine until it halts. init c v and halt encode the initial and final configurations, and <$> maps halt over the partial result.
import Mathlib
namespace FamousTheorems
theorem partrec_turing_computable_7a (c : Turing.ToPartrec.Code) (v : List ℕ) :
StateTransition.eval (Turing.TM2.step Turing.PartrecToTM2.tr) (Turing.PartrecToTM2.init c v) =
Turing.PartrecToTM2.halt <$> c.eval v := by sorry
end FamousTheorems