I'm more troubled by the fact that almost all real numbers are uncomputable (same goes for complex numbers, of course). It's very straightforward to see that this is the case, but the mathematics involved to even begin to ponder questions like "under which operations is the set of computable reals not closed" seem to be far over my head.

▲ xscott 5 days ago | parent [-]

Are there any operations you can even perform on the computables in the general case? Take addition, it seems simple until you try to add two computable numbers:

      0.59999999999999999999999...
    + 0.00000000000000000000000...
    ------------------------------
      0.?

Until you see a non-nine in that first number, or a non-zero in the second, you can't even emit the first digit of the output. From outside the black box, you don't know if the nines and zeros will stop or continue forever.

I think you can make pathological cases for every arithmetic operation, so maybe (I'm not sure) none of the operations are computable. (Need to be careful with the definitions though, and I'm being pretty sloppy)

▲

tshaddox 4 days ago | parent | next [-]

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.

▲

BobbyTables2 3 days ago | parent | prev [-]

That’s just 0.6 and 0.0 written cleverly.

If the 9’s repeat forever then there is no possible number between that and 0.6, so it must be the same…

Put another way, any single digit “n” repeating is just n/9.

Your problem is equivalent to (4/9 + 5/9 - 0.4) + 0/9

(Equivalent to 0.6)

	▲	xscott 3 days ago \| parent [-]
		You don't know if those 9s repeat forever in this problem. It's output from a program, and the program could switch to 3s in 1000 more digits. The "adding" program is reading text digits from two other programs and can't see how they work. It can't assume a bunch of 9s mean there will be more 9s.