EuDML | Browse

Items

All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 4 Next

Displaying 61 – 80 of 110

The unique existential quantifier.

H.B. Enderton (1970)

Archiv für mathematische Logik und Grundlagenforschung

Turning Borel sets into clopen sets effectively

Vassilios Gregoriades (2012)

Fundamenta Mathematicae

We present the effective version of the theorem about turning Borel sets in Polish spaces into clopen sets while preserving the Borel structure of the underlying space. We show that under some conditions the emerging parameters can be chosen in a hyperarithmetical way and using this we obtain some uniformity results.

Über die mit Stackautomaten berechenbaren Funktionen.

Horst Müller (1970)

Archiv für mathematische Logik und Grundlagenforschung

Über Hilbert's reale und ideale Elemente.

Horst Luckhardt (1975)

Archiv für mathematische Logik und Grundlagenforschung

Undecidability of topological and arithmetical properties of infinitary rational relations

Olivier Finkel (2003)

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

We prove that for every countable ordinal $α$ one cannot decide whether a given infinitary rational relation is in the Borel class $Σ_{α}^{0}$ (respectively $Π_{α}^{0}$ ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a $Σ_{1}^{1}$ -complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide whether...

Undecidability of Topological and Arithmetical Properties of Infinitary Rational Relations

Olivier Finkel (2010)

RAIRO - Theoretical Informatics and Applications

We prove that for every countable ordinal α one cannot decide whether a given infinitary rational relation is in the Borel class $Σ_{α}^{0}$ (respectively $Π_{α}^{0}$ ). Furthermore one cannot decide whether a given infinitary rational relation is a Borel set or a $Σ_{1}^{1}$ -complete set. We prove some recursive analogues to these properties. In particular one cannot decide whether an infinitary rational relation is an arithmetical set. We then deduce from the proof of these results some other ones, like: one cannot decide...

Undecidability vs transfinite induction for the consistency of hyperarithmetical sets.

S. Caporaso, G. Pani (1982)

Archiv für mathematische Logik und Grundlagenforschung

Wadge degrees of $ω$ -languages of deterministic Turing machines

Victor Selivanov (2003)

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

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 $ξ = ω_{1}^{CK}$ 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

Victor Selivanov (2010)

RAIRO - Theoretical Informatics and Applications

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