The undecidability of pattern matching in calculi where primitive recursive functions are representable

DOI10.1016/0304-3975(93)90175-SzbMath0773.03011OpenAlexW2072809974MaRDI QIDQ1208421

Gilles Dowek

Publication date: 16 May 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(93)90175-s

zbMATH Keywords

pattern matchingprimitive recursive functionsHilbert's tenth problemGirard's system \(F\)Gödel's system \(T\)calculi supporting inductive typespolymorphic \(\lambda\)-calculi

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25) Recursive functions and relations, subrecursive hierarchies (03D20) Combinatory logic and lambda calculus (03B40)

Related Items (1)

Third-order matching in the polymorphic lambda calculus

Cites Work

• ÜBER EINE BISHER NOCH NICHT BENÜTZTE ERWEITERUNG DES FINITEN STANDPUNKTES
• Hilbert's Tenth Problem is Unsolvable
• Introduction to generalized type systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The undecidability of pattern matching in calculi where primitive recursive functions are representable