Undecidable Tiling Problems in the Hyperbolic Plane.
Undecidable varieties with solvable word problems. II.
Undecidable varieties with solvable word problems. III (a semigroup variety).
Une généralisation de la notion d'ensemble immune
Une généralisation des ensembles énumérés
Unification for nilpotent groups of class 2.
Uniform reducibility of representability problems for algebraic structures.
Universal Isols.
Wadge degrees of -languages of deterministic Turing machines
We describe Wadge degrees of -languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is where is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
Wadge Degrees of ω-Languages of Deterministic Turing Machines
We describe Wadge degrees of ω-languages recognizable by deterministic Turing machines. In particular, it is shown that the ordinal corresponding to these degrees is ξω where ξ = ω1CK is the first non-recursive ordinal known as the Church–Kleene ordinal. This answers a question raised in [2].
Weakly maximal decidable structures
We prove that there exists a structure M whose monadic second order theory is decidable, and such that the first-order theory of every expansion of M by a constant is undecidable.
What Is A Mathematical Theory?
What machines can and cannot do.
In this paper, the questions of what machines cannot do and what they can do will be treated by examining the ideas and results of eminent mathematicians. Regarding the question of what machines cannot do, we will rely on the results obtained by the mathematicians Alan Turing and Kurt G¨odel. Turing machines, their purpose of defining an exact definition of computation and the relevance of Church-Turing thesis in the theory of computability will be treated in detail. The undecidability of the “Entscheidungsproblem”...
Zu den primitiv-rekursiven Funktionen über einem Bereich endlicher Mengen.
Zur Beweistheorie der Kripke-Platek-Mengenlehre über den natürlichen Zahlen.
Zur konstruktiven Differenzierbarkeit von monotonen berechenbaren Funktionen.
Zur Theorie der spektralen Darstellung von Prädikaten durch Ausdrücke der Prädikatenlogik 1. Stufe.
-tautologies, uniform and non-uniform upper bounds in computation theory
Una -tautologia è una tautologia del tipo avente un solo interpolante di Craig , a meno di equivalenza logica. Utilizzando misure di complessità relative al problema di trovare tale , mostriamo come si possano ottenere limiti non uniformi di complessità mediante limiti uniformi, e viceversa.
-principal numberings.
-cofinalities of