Some corrolaries.¥There is no general algorithm which, given two programs that output infinite decimals as streams, computes the infinite decimal representing their sum.
Let A and B be two computer programs.
Let x start with "0." followed by 0's until program A halts, at which point the digits change to 1's.
Let y start with "0." followed by 9's until program B halts, at which point the digits change to 8's.
If A halts and B does not halt, then x+y > 1, and the ones place of x+y must be 1. If B halts and A does not halt, then x+y < 1, and the ones place of x+y must be 0. Thus there is no way to calculate the ones place of x+y.
Note that it's possible to get around this problem by using more than 10 digits. For example, infinite decimals built using the digits -9 through 9, like I talked about in >>9462
, don't have this problem.¥There is no general algorithm which converts an object of our real number type to a stream of digits giving an infinite decimal representation of the number.
I mentioned I didn't know a proof of this; now we have one. We can easily convert a stream of digits into a stream of nested rational intervals. For example, 3.14... becomes [3,4], [3.1,3.2], [3.14,3.15], ... . If we could convert back into an infinite decimal stream, then we could take the two infinite decimal streams from the previous proof, convert them into nested interval streams, add them, then convert to the desired inifinite decimal stream.
Note that there would be no problem converting to infinite decimal form if we allow the digits -9 through 9. Also, there's no problem with doing what's done now in Post too long. Click here to view the full text.