Fractions continues limitées et théorie des langages
Function operators spanning the arithmetical and the polynomial hierarchy
A modified version of the classical µ-operator as well as the first value operator and the operator of inverting unary functions, applied in combination with the composition of functions and starting from the primitive recursive functions, generate all arithmetically representable functions. Moreover, the nesting levels of these operators are closely related to the stratification of the arithmetical hierarchy. The same is shown for some further function operators known from computability and complexity theory....
Functions provably total in
Functions provably total in
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...
Goldbach conjecture.
Good choice sets
Goodstein's function.
Groups of automatic automorphisms of some automatic structures.
Halteprobleme von Fang-Systemen (Tag Systems).
Hierarchien primitiv-rekursiver Funktionen im Transfiniten.
Hierarchies and reducibilities on regular languages related to modulo counting
We discuss some known and introduce some new hierarchies and reducibilities on regular languages, with the emphasis on the quantifier-alternation and difference hierarchies of the quasi-aperiodic languages. The non-collapse of these hierarchies and decidability of some levels are established. Complete sets in the levels of the hierarchies under the polylogtime and some quantifier-free reducibilities are found. Some facts about the corresponding degree structures are established. As an application,...
Hierarchies and reducibilities on regular languages related to modulo counting
We discuss some known and introduce some new hierarchies and reducibilities on regular languages, with the emphasis on the quantifier-alternation and difference hierarchies of the quasi-aperiodic languages. The non-collapse of these hierarchies and decidability of some levels are established. Complete sets in the levels of the hierarchies under the polylogtime and some quantifier-free reducibilities are found. Some facts about the corresponding degree structures are established. As an application, we...
Hierarchies of function classes defined by the first-value operator
The first-value operator assigns to any sequence of partial functions of the same type a new such function. Its domain is the union of the domains of the sequence functions, and its value at any point is just the value of the first function in the sequence which is defined at that point. In this paper, the first-value operator is applied to establish hierarchies of classes of functions under various settings. For effective sequences of computable discrete functions, we obtain a hierarchy connected...
Hierarchies of function classes defined by the first-value operator
The first-value operator assigns to any sequence of partial functions of the same type a new such function. Its domain is the union of the domains of the sequence functions, and its value at any point is just the value of the first function in the sequence which is defined at that point. In this paper, the first-value operator is applied to establish hierarchies of classes of functions under various settings. For effective sequences of computable discrete functions, we obtain a hierarchy connected...
Hierarchies of number - theoretic functions I, II: a correction.
Hierarchies of number-theoretic functions. I.
Hierarchies of number-theoretic functions. II.
Highly Undecidable Problems For Infinite Computations
We show that many classical decision problems about 1-counter ω-languages, context free ω-languages, or infinitary rational relations, are Π½ -complete, hence located at the second level of the analytical hierarchy, and “highly undecidable”. In particular, the universality problem, the inclusion problem, the equivalence problem, the determinizability problem, the complementability problem, and the unambiguity problem are all Π½ -complete for context-free ω-languages or for infinitary rational...
Horn clause programs and recursive functions defined by systems of equations