No Access
TURING MACHINES
This chapter of the survey has not been published elsewhere.
https://doi.org/10.1142/9789812796493_0002Cited by:0 (Source: Crossref)
Abstract:
We review the Turing machine version of a fundamental information-theoretic incompleteness theorem, which asserts that it is difficult to prove that specific strings s have high Turing machine state complexity Htm(s). We also construct a Thing machine “halting probability” Ωtm with the property that the initial segments of its base-two expansion asymptotically have the maximum possible Turing machine complexity Htm.
