Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 3 / Issue 11

available in:   PDF (186 kB) PS (61 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-003-11-1162


Chaitin Ω Numbers and Strong Reducibilities

Cristian S. Calude (Department of Computer Science, University of Auckland, New Zealand)

André Nies (Department of Mathematics, University of Chicago, USA)

Abstract: We prove that any Chaitin Ω number (i.e., the halting probability of a universal self-delimiting Turing machine) is wtt-complete, but not tt-complete. In this way we obtain a whole class of natural examples of wtt-complete but not tt-complete r.e. sets. The proof is direct and elementary.

1.) Proceedings of the First Japan-New Zealand Workshop on Logic in Computer Science, special issue editors D.S. Bridges, C.S. Calude, M.J. Dinneen and B. Khoussainov.
2.) Partially supported by AURC A18/XXXXX/62090/F3414056, 1997.
3.) Partially supported by NSF Grant DMS-9500983.

Keywords: Chaitin Ω number, tt-complete r.e. set, wtt-complete r.e. set

Categories: F.1