JUCS - Journal of Universal Computer Science 3(11): 1162-1166, doi: 10.3217/jucs-003-11-1162
Chaitin Ω Numbers and Strong Reducibilities
Cristian S. S. Calude‡, André Nies§‡ University of Auckland, Auckland, New Zealand§ Department of Mathematics, University of Chicago, Chicago, IL, United States of America
Corresponding author: Cristian S. Calude ( cristian@cs.auckland.ac.nz ) © Cristian S. Calude, André Nies. This article is freely available under the J.UCS Open Content License. Citation:
Calude CSS, Nies A (1997) Chaitin Ω Numbers and Strong Reducibilities. JUCS - Journal of Universal Computer Science 3(11): 1162-1166. https://doi.org/10.3217/jucs-003-11-1162 |  |
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, wtt-complete r.e. set, tt-complete r.e. set