World Scientific
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at customercare@wspc.com for any enquiries.
No Access

BLANK-ENDMARKER PROGRAMS

    This chapter of the survey has not been published elsewhere.

    https://doi.org/10.1142/9789812796493_0003Cited by:0 (Source: Crossref)
    Previous
    Next
    Abstract:

    We review four different versions of the information-theoretic incompleteness theorem asserting that it is difficult to prove that specific strings s have high blank-endmarker complexity Hb(s). We also construct a blank-endmarker “halting probability” Ωb with the property that the initial segments of its base-two expansion asymptotically have the maximum possible blank-endmarker complexity Hb.