Program-Size Complexity Computes the Halting Problem
Reference
CDMTCS Research Reports CDMTCS-008 (1995)
Degree Grantor
Abstract
Can the halting problem be solved if one could compute program-size complexity? The answer is yes and here are two different proofs.
Description
DOI
Related Link
Keywords
ANZSRC 2020 Field of Research Codes
Collections
Permanent Link
Rights
The author(s)