Program-Size Complexity Computes the Halting Problem

ResearchSpace/Manakin Repository

Program-Size Complexity Computes the Halting Problem

Chaitin, G.J ; Arslanov, A ; Calude, C
Identifier: http://hdl.handle.net/2292/3517
Issue Date: 1995-09
Reference: CDMTCS Research Reports CDMTCS-008 (1995)
Rights: The author(s)
Rights (URI): https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm

Abstract:

Can the halting problem be solved if one could compute program-size complexity? The answer is yes and here are two different proofs.

Show full item record

Full text options

Icon
Name: 008HHP.pdf
Size: 408.3Kb
Format: PDF
Icon
Related URL: http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial

This item appears in the following Collection(s)

Statistics

Country Code Views
New Zealand 1259
United States 361
China 64
Germany 46
United Kingdom 20

Share

Search ResearchSpace


Advanced Search

Browse