On Decidable and Undecidable Extensions of Simply Typed Lambda Calculus
summary
Gives simple proofs that the reachability problem becomes undecidable for four undecidable extensions of finitary PCF and then isolates a decidable fragment with ownership types for call-by-value PCF with references: a linear/ownership type system plus a local store-passing translation removes references and yields a well-typed pure PCF term, preserving reachability. Claims this is the first nontrivial decidable fragment supporting higher-order recursive functions with reference cells, and shows manual translations fed to Mochi distinguish subtle examples (translation works).
AI-written summary · about