JUCS - Journal of Universal Computer Science 3(11): 1162-1166, doi: 10.3217/jucs-003-11-1162
Chaitin Ω Numbers and Strong Reducibilities
expand article infoCristian S. S. Calude, André Nies§
‡ University of Auckland, Auckland, New Zealand§ Department of Mathematics, University of Chicago, Chicago, IL, United States of America
Open Access
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.
Chaitin Ω number, wtt-complete r.e. set, tt-complete r.e. set