Chaitin Ω Numbers and Strong Reducibilities
Дата
Авторы
Calude,Cristian S.
Nies,André
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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