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

CREATORAndrej Dudenhefner ORCID:0000-0003-1104-444X
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65962
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602.02091

Browse the full library · About the Tower of Babel