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