“Because all computable functions are continuous”—how does this make any sense? Why can’t I just pick a value x=1 and if it’s left limit and right limit are p, set the function to p+1 at x=1.
Because equality of (computable) real numbers is uncomputable. So is calculating the limit of an infinite sequence of them.
In more detail: a computable real number must be represented by a Turing machine (or your favorite Turing-equivalent model) that generates some representation of it as a possibly infinite string. Equality of the infinite output of two Turing machines is uncomputable.
In fact, picking a representation for “computable” real numbers, and implementing basic arithmetic on them is non-trivial. The usual decimal or binary strings of digits won’t work.
Hmm, I’m still not following. Limits are uncomputable in general, but I just need one computational function where I know the limits at one point and then I can set it to p+1 instead. Why wouldn’t this function still be computable? Maybe “computable function” is being defined differently than I would expect.
To compute that function for an unknown argument x, you would have to determine whether x is equal to 1. But if real numbers are encoded as infinite strings, there is no way to tell whether x=1 in finite time. If x happens to be 1, then however long an initial segment of that representation you examined, you could never be sure that x was not very slightly different from 1. In the usual decimal representation, if you see 1.00000.… if the number is greater than 1 you will eventually know that, but if the zeroes go on forever, you can never know that. Similarly if you see 0.99999.....
I’m not sure how relevant this is to the original context, see other replies to Adele Lopez’s ancestor comment.
Okay, so there is an additional assumption that these strings are all encoded as infinite sequences. Instead, they could be encoded with a system that starts by listing the number of digits or −1 if the sequence if infinite, then provide those digits. That’s a pretty key property to not mention (then again, I can’t criticise too much as I was too lazy to read the PDF). Thanks for the explanation!
“Because all computable functions are continuous”—how does this make any sense? Why can’t I just pick a value x=1 and if it’s left limit and right limit are p, set the function to p+1 at x=1.
Because equality of (computable) real numbers is uncomputable. So is calculating the limit of an infinite sequence of them.
In more detail: a computable real number must be represented by a Turing machine (or your favorite Turing-equivalent model) that generates some representation of it as a possibly infinite string. Equality of the infinite output of two Turing machines is uncomputable.
In fact, picking a representation for “computable” real numbers, and implementing basic arithmetic on them is non-trivial. The usual decimal or binary strings of digits won’t work.
Hmm, I’m still not following. Limits are uncomputable in general, but I just need one computational function where I know the limits at one point and then I can set it to p+1 instead. Why wouldn’t this function still be computable? Maybe “computable function” is being defined differently than I would expect.
To compute that function for an unknown argument x, you would have to determine whether x is equal to 1. But if real numbers are encoded as infinite strings, there is no way to tell whether x=1 in finite time. If x happens to be 1, then however long an initial segment of that representation you examined, you could never be sure that x was not very slightly different from 1. In the usual decimal representation, if you see 1.00000.… if the number is greater than 1 you will eventually know that, but if the zeroes go on forever, you can never know that. Similarly if you see 0.99999.....
I’m not sure how relevant this is to the original context, see other replies to Adele Lopez’s ancestor comment.
Okay, so there is an additional assumption that these strings are all encoded as infinite sequences. Instead, they could be encoded with a system that starts by listing the number of digits or −1 if the sequence if infinite, then provide those digits. That’s a pretty key property to not mention (then again, I can’t criticise too much as I was too lazy to read the PDF). Thanks for the explanation!