HackerPapers

arXiv:1003.0480cs.CC

A definable number which cannot be approximated algorithmically

Nicolas Brener

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

The Turing machine (TM) and the Church thesis have formalized the concept of computable number, this allowed to display non-computable numbers. This paper defines the concept of number "approachable" by a TM and shows that some (if not all) known non-computable numbers are approachable by TMs. Then an example of a number not approachable by a TM is given.

arXiv comments
Journal reference
DOI
Subjects
cs.CCComputational Complexity cs.LOLogic in Computer Science

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Apr 2017 to Apr 2017.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. How real are real numbers? (2004) 1 comment

    • I don't think that argument works. How do you guarantee that you can compute the n-th decimal of the n-th number in the list? In fact, from what I understand, this paper[1] shows how to specify exactly a number can't be computed like that. [1] https://arxiv.org/pdf/1003.0480.pdf

      moefhView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.