Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What exactly does it mean to say that a real number $x$ is computable? I can think of two reasonable definitions but I am not sure whether or not they are equivalent:

1) There is an algorithm which given $n$ outputs the $n^{\text{th}}$ bit of the binary representation of $x$.

2) There is an algorithm which given $n$ outputs a rational number $q$ with $\vert{q-x}\vert \le \frac{1}{n}$.

The troublesome case is the following: Let $z$ be the reciprocal of the length of the shortest proof of falsehood in ZFC if ZFC is inconsistent, else $0$ if ZFC is consistent, and let $x = 1 - z$. So either $x=1$ or $x = 0.1111...0...$. Seemingly the latter definition is satisfied but not the former. In the latter case, the program can spend some time hunting for a contradiction in ZFC and then output a sufficiently precise approximation whether or not a contradiction is found. In the former case, we cannot even determine the first bit, unless ZFC is actually inconsistent. Is this reasoning that the definitions are not equivalent correct? If so, what definition (perhaps neither) is standard, and how can the argument be stated more clearly? If the definitions are in fact equivalent, why?

share|improve this question
add comment

3 Answers 3

up vote 6 down vote accepted

The number you describe is a rational. Thus it is certainly computable, by either of your definitions. The fact that we don't know which computation outputs approximations to $x$ is not relevant.

share|improve this answer
    
Ah, that makes sense, so my example is invalid. I expect I will be able to figure out what is wrong with my argument on that basis. Are the definitions equivalent then? –  Dan Brumleve Jan 7 '13 at 7:27
    
I think so, for essentially the same reason. I haven't fully checked the details. –  Chris Eagle Jan 7 '13 at 7:29
1  
The definitions are actually equivalent, because either a number has a terminating binary expansion (in which case the algorithm consists of a finite number of "$1$" cases and "$0$ otherwise") or not (in which case we can try better and better rational approximations until we get one that decides the $n$'th bit). The reason that (1) is preferred is that it allows effective algorithms for functions. –  Robert Israel Jan 7 '13 at 7:42
    
Thanks @Robert, I think I get it now -- when $x$ is rational, it is computable, and when $x$ is not rational, it has a non-terminating binary expansion, so in that case algorithm (1) can be implemented by making calls to algorithm (2). –  Dan Brumleve Jan 7 '13 at 7:57
add comment

The reasoning is not correct. If ZFC is consistent, there is an algorithm that outputs $x$, namely "output $1$". It's just that we don't happen to know that this algorithm is correct.

share|improve this answer
add comment

The other answers address your particular example, but not the equivalence of the two representations.

The base-2 representation of real numbers and the Cauchy representation (your second representation) do indeed define the same set of computable numbers.

However, the functions computable on these representations differ (multiplication by 3 is not computable in the base-2 representation -- Turing originally noted this for base-10).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.