Proof of Thm A.4, p. A:42 — is closed under
ProvedObfImpossibility.RiceNoSize.Pi_closedcomputabilityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1promise-problemsrice-theorem
Let be the promise problem of the proof of Theorem A.4: consists of the machines that always halt and output on some input , and of the machines that always halt and output on every input. Then is closed under : for all machines ,
This is the first of the two properties that make an instance of the hypothesis of Conjecture A.3.
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 closed under `[·]`. -/ theorem Pi_closed : ClosedUnderFn 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 ("It is obvious that Π is closed under [·].")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.