Program-Size Complexity Computes the Halting Problem

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

Files in this item

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
Find Full text

This item appears in the following Collection(s)

Share

Search ResearchSpace


Browse

Statistics