RAIRO - Theoretical Informatics and Applications

Table of Contents - January 2003 - Volume 37, Issue 01  

Research Article

Wadge Degrees of ω-Languages of Deterministic Turing Machines

Selivanov, Victor

Universität Siegen, Theoretische Informatik, Fachbereich 6, Germany; vseliv@informatik.uni-siegen.de.

Novosibirsk State Pedagogical University Chair of Informatics and Discrete Mathematics, Russia; vseliv@nspu.ru .

Abstract

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

(Received July 2002)

(Accepted April 2003)

(Online publication November 15 2003)

Key Words:

  • Hierarchy;
  • Wadge degree;
  • ω-language;
  • ordinal;
  • Turing machine;
  • set-theoretic operation.

Mathematics Subject Classification:

  • 03D55;
  • 04A15;
  • 68Q05