dc.contributor.author |
Chaitin, G.J |
en |
dc.date.accessioned |
2009-04-16T23:16:07Z |
en |
dc.date.available |
2009-04-16T23:16:07Z |
en |
dc.date.issued |
2007-04 |
en |
dc.identifier.citation |
CDMTCS Research Reports CDMTCS-305 (2007) |
en |
dc.identifier.issn |
1178-3540 |
en |
dc.identifier.uri |
http://hdl.handle.net/2292/3812 |
en |
dc.description.abstract |
Using 1947 work of Post showing that the word problem for semigroups
is unsolvable, we explicitly exhibit an algebraic characterization
of the bits of the halting probability
Ω. Our proof closely follows
a 1978 formulation of Post’s work by M. Davis. The proof is selfcontained
and not very complicated. |
en |
dc.publisher |
Department of Computer Science, The University of Auckland, New Zealand |
en |
dc.relation.ispartofseries |
CDMTCS Research Report Series |
en |
dc.rights.uri |
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm |
en |
dc.source.uri |
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial |
en |
dc.title |
An Algebraic Characterization of the Halting Probability |
en |
dc.type |
Technical Report |
en |
dc.subject.marsden |
Fields of Research::280000 Information, Computing and Communication Sciences |
en |
dc.rights.holder |
The author(s) |
en |
dc.rights.accessrights |
http://purl.org/eprint/accessRights/OpenAccess |
en |