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 and NTIME
Bemerkung zu Gurevich's Arbeit über das Entscheidungsproblem für Standardklassen.
Call-by-value solvability
Call-by-value Solvability
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.
Consistency proof without transfinite induction for a formal system for turing machines.
Craig's interpolation theorem, in computation theory
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...
Crossing-bounded computations and their relation to the LBA-problem
E. T. a infinitární Churchova teze
Finite alogorithmic procedures and inductive definability.
Gödel et la thèse de Turing
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...
Halteprobleme von Fang-Systemen (Tag Systems).
Horn clause programs and recursive functions defined by systems of equations
Může stroj myslet? (Hypotetická debata L. Wittgensteina, A. Turinga a A. Churche)