3 ms·
Can you link to a proof for these "computable numbers" being a countably infinite subset of R? :)
by StandardFuture 12y ago
Can you link to a proof for these "computable numbers" being a countably infinite subset of R? :)
- alexbecker 12y agoNot the comment-er, but here's a rough sketch. Definition: A computable number is a real number x such that there exists a total computable function f:Q->Q for which, given any r>0, f(r) is within r of x. Proof: There are only countably many total computable functions, since each can be described as a finite string of symbols from a finite alphabet. Hence only countably many computable numbers.
- avmich 12y agoCharles Petzold in "Annotated Turing" gives a good explanation of this and related subjects.