0

Suppose I start with the set of computable real numbers between 0 and 1. Now these are countable.

So I follow Cantor's diagonalization argument to construct a real number B between 0 and 1 outside this set.

I enumerate the countable real numbers S1, S2,S3... and I construct B to have it's nth digit after the decimal place be one plus the nth digit of SN if it's 0-8, and 0 if it's 9.

So following this process have I constructed a non-computable real number? Because it feels like what I did above was a computation (I followed an algorithmic process)... How can I compute a non-computable real number? Was the above not a computation... ie couldn't a computer follow this process to create a number outside the countable real numbers... ie: compute the first digit of the first countable number... add 1 to it to calculate the first digit of B... then go on to the second digit of the second countable number etc.

Where is my error? Thanks.

Ameet Sharma
  • 2,957
  • 4
    The problem is that it is impossible to find an enumeration S1, S2, S3,... which is computable. If you try to do that, then you will quickly find out that you have to essentially exclude algorithms which don't terminate (because those don't define a computable number) and you have no way to do that. – Wojowu May 04 '19 at 11:35
  • 2
    In fact, if there had been a way to enumerate all computable numbers, you would have been able to compute an uncomputable number. – Wuestenfux May 04 '19 at 13:37

0 Answers0