EuDML | Browse

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,...

Combinatorial systems defined over one- and two-letter alphabets.

Ch.E. Hughes, W.E. Singletary (1975)

Archiv für mathematische Logik und Grundlagenforschung

Consistency proof without transfinite induction for a formal system for turing machines.

Salvatore Caporaso (1978)

Archiv für mathematische Logik und Grundlagenforschung

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 $\chi$ e la lunghezza di $\varphi$ e $\psi$ , ove $\varphi\to\psi$ è un’implicazione valida, e $\chi$ è 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...

Crossing-bounded computations and their relation to the LBA-problem

Michal P. Chytil (1976)

Kybernetika

E. T. a infinitární Churchova teze

Robert M. Baer (1996)

Pokroky matematiky, fyziky a astronomie

Finite alogorithmic procedures and inductive definability.

J. Moldestad, V. Stoltenberg-Hansen (1980)

Mathematica Scandinavica

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

Displaying 1 – 20 of 64

A deterministic subclass of context-free languages

A note on comparison of Turing machines with computers

A Turing machine oracle hierarchy. I.

A Turing machine oracle hierarchy. II.

A Turing machine space hierarchy

Alan Mathison Turing – život a dílo

Algebraic caractérisations of NTIME $(F)$ and NTIME $(F, A)$

Bemerkung zu Gurevich's Arbeit über das Entscheidungsproblem für Standardklassen.

Call-by-value solvability

Call-by-value Solvability