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.

Read the Lean proof on GitHub

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.