Among the unsolvable terms of the lambda calculus, the mute ones are those having the highest degree of undefinedness. In this paper, we define for each natural number n, an infinite and recursive set Mn of mute terms, and show that it is graph-easy: for any closed term t of the lambda calculus there exists a graph model equating all the terms of Mn to t. Alongside, we provide a brief survey of the notion of undefinedness in the lambda calculus.

Graph easy sets of mute lambda terms

FAVRO, GIORDANO;SALIBRA, Antonino
2016-01-01

Abstract

Among the unsolvable terms of the lambda calculus, the mute ones are those having the highest degree of undefinedness. In this paper, we define for each natural number n, an infinite and recursive set Mn of mute terms, and show that it is graph-easy: for any closed term t of the lambda calculus there exists a graph model equating all the terms of Mn to t. Alongside, we provide a brief survey of the notion of undefinedness in the lambda calculus.
File in questo prodotto:
File Dimensione Formato  
tcs-muti-revisione-23-novembre-ore19.pdf

accesso aperto

Tipologia: Documento in Pre-print
Licenza: Accesso chiuso-personale
Dimensione 339.95 kB
Formato Adobe PDF
339.95 kB Adobe PDF Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/3664684
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact