Proof of `The halting problem is RE-complete`
groundedproofs/Lax624099Proofs/Bridge.lean · lax-624099
What this proof establishes
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Membership from the library's definition of unbounded acceptance with value invention; hardness because finite satisfiability, recursively enumerable on concrete instances, reduces to the halting problem by the library's ordered reduction, the machine bridge, and is RE-hard by this submission's statement.