Proof of Thm A.4, p. A:42 — is decidable
ProvedObfImpossibility.RiceNoSize.Pi_decidablecomputabilityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1promise-problemsrice-theorem
The promise problem of the proof of Theorem A.4 is decidable: there is a program , run on canonical descriptions of machines, such that
Outside nothing is required of ; it may diverge.
This is the second property that makes an instance of the hypothesis of Conjecture A.3. The paper's runs on every input and outputs exactly when some answer is non-zero.
Formalization Note is a Mathlib Nat.Partrec.Code applied to the natural-number description of , so decidability means decidability by a partial recursive function.
Preamble
import Mathlib import Definitions.Def_ObfImpossibility_RiceNoSize_ProofObjects
Formal statement
namespace ObfImpossibility.RiceNoSize /-- p. A:42: the promise problem `Π = (Π_Y, Π_N)` of the proof of Theorem A.4 is decidable: some program `T`, run on descriptions `⌜M⌝`, outputs `1` on `Π_Y` and `0` on `Π_N`. -/ theorem Pi_decidable : ∃ T : Nat.Partrec.Code, Decides T PiY PiN := by sorry end ObfImpossibility.RiceNoSize
Source
Barak et al., On the (Im)possibility of Obfuscating Programs, J. ACM 59(2) (2012), author's copy, p. A:42, proof of Theorem A.4 ("We claim that Π is decidable.")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.