Chaitin Ω Numbers and Strong Reducibilities
| dc.creator | Calude,Cristian S. | |
| dc.creator | Nies,André | |
| dc.date | 1997 | |
| dc.date.accessioned | 2024-02-06T12:49:07Z | |
| dc.date.available | 2024-02-06T12:49:07Z | |
| dc.description | 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. | |
| dc.format | text/html | |
| dc.identifier | https://doi.org/10.3217/jucs-003-11-1162 | |
| dc.identifier | https://lib.jucs.org/article/27425/ | |
| dc.identifier.uri | https://openrepository.mephi.ru/handle/123456789/7249 | |
| dc.language | en | |
| dc.publisher | Journal of Universal Computer Science | |
| dc.relation | info:eu-repo/semantics/altIdentifier/eissn/0948-6968 | |
| dc.relation | info:eu-repo/semantics/altIdentifier/pissn/0948-695X | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | J.UCS License | |
| dc.source | JUCS - Journal of Universal Computer Science 3(11): 1162-1166 | |
| dc.subject | Chaitin Ω | |
| dc.subject | number | |
| dc.subject | wtt-complete r.e. set | |
| dc.subject | tt-complete r.e. set | |
| dc.title | Chaitin Ω Numbers and Strong Reducibilities | |
| dc.type | Research Article |