Program-Size Complexity Computes the Halting Problem
Login
University Home
→
Library
JavaScript is disabled for your browser. Some features of this site may not work without it.
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
Name:
008HHP.pdf
Size:
408.3Kb
Format:
PDF
Related URL:
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
This item appears in the following Collection(s)
CDMTCS Research Reports (1995+)
[566]
Share
Search ResearchSpace
Search ResearchSpace
This Collection
Browse
All of ResearchSpace
Communities & Collections
By Issue Date
Authors
Titles
Subjects
This Collection
By Issue Date
Authors
Titles
Subjects
Statistics
View Usage Statistics