Mechanized Undecidability of Higher-order beta-Matching (Extended Version)
Andrej Dudenhefner ORCID:0000-0003-1104-444X · 2026
Read Mechanized Undecidability of Higher-order beta-Matching (Extended Version) by Andrej Dudenhefner ORCID:0000-0003-1104-444X (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-02091.txt.
Description
Andrej Dudenhefner provides a novel proof for higher-order beta-matching undecidability, whether a first lambda-term can be beta-equivalent to a second term, shown undecidable by Loader. The proof encodes string rewriting as beta-matching. The approach has advantages: the proof is simpler to verify; string rewriting undecidability is already certified, yielding a certified Halting Problem reduction. The approach also identifies a uniform construction for beta-matching and lambda-definability. The proof is mechanized in the Rocq Prover.
Catalog record
| CREATOR | Andrej Dudenhefner ORCID:0000-0003-1104-444X |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65962 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602.02091