Proof of `Post's correspondence 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 matching with value invention; hardness from the library's computation-history reduction of the halting problem to Post's correspondence problem, the halting problem being RE-hard by this submission's statement.