Remix.run Logo
tshaddox 4 days ago

If a number if computable, it means you can compute it to any given precision using an algorithm which halts.

It doesn't mean that you can compute a complete representation in decimal (or any other positional numeral system) of the number using an algorithm which halts. This is of course impossible with computable numbers like pi or 1/3.

But you can compute the value of pi or 1/3 within error bound n, for any rational number n. Thus we say pi and 1/3 are both computable numbers. This isn't quite the same as saying you can always generate the first n digits of the decimal representation, because as you point out, any decimal digit can be sensitive to arbitrarily small changes in value.

But given these definitions, we can see that adding two computable numbers is indeed computable. In your example, the decimal representation of the output could begin with 0.5 or 0.6, depending on the precision you chose and the values of the two inputs at that chosen precision. Regardless, the output will be within the chosen precision.

Your example also comes close to illustrating that testing the equality of two computable numbers is not computable. There is no finite algorithm which can tell you if any two computable numbers are equal (or tell you which one is larger). Again, you can compute whether they are within any chosen bound of each other, but not whether they are equal.

xscott 4 days ago | parent [-]

I did say we needed to be careful with the definitions. I'm sure you can look at Wikipedia to see that Minsky gave a definition like I used. You're not wrong to use a new definition though.