Page 1 Next

Displaying 1 – 20 of 64

Showing per page

Call-by-value solvability

Luca Paolini, Simona Ronchi Della Rocca (1999)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Call-by-value Solvability

Luca Paolini, Simona Ronchi Della Rocca (2010)

RAIRO - Theoretical Informatics and Applications

The notion of solvability in the call-by-value λ-calculus is defined and completely characterized, both from an operational and a logical point of view. The operational characterization is given through a reduction machine, performing the classical β-reduction, according to an innermost strategy. In fact, it turns out that the call-by-value reduction rule is too weak for capturing the solvability property of terms. The logical characterization is given through an intersection type assignment system,...

Craig's interpolation theorem, in computation theory

Daniele Mundici (1981)

Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni

Si espongono alcuni risultati, provati dall’Autore negli articoli citati nella bibliografia, a proposito della complessità del teorema d’interpolazione di Craig: con ciò si intende la relazione tra la lunghezza (cioè il numero di simboli) della formula χ e la lunghezza di φ e ψ , ove φ ψ è un’implicazione valida, e χ è un interpolante, come esibito dal teorema di interpolazione stesso. Si intende altresì sottolineare la rilevanza dello studio della complessità dell’interpolazione per far luce su alcuni...

Gödel et la thèse de Turing

Pierre Cassou-Noguès (2008)

Revue d'histoire des mathématiques

Cet article porte sur la discussion par Gödel de la thèse de Turing. Pour l’essentiel, nous présentons des notes inédites conservées dans les Archives Gödel, qui apportent des éléments nouveaux sur la relation ambiguë de Gödel à Turing. La première section examine la position qu’avait Gödel avant 1937 sur la possibilité d’une définition de la calculabilité. La deuxième concerne directement l’interprétation par Gödel de la thèse de Turing. Dans plusieurs passages, antérieurs à 1937, Gödel qualifie...

Currently displaying 1 – 20 of 64

Page 1 Next