HackerTrans
TopNewTrendsCommentsPastAskShowJobs

hermod

no profile record

comments

hermod
·il y a 6 ans·discuss
This was downvoted, but I think it's an interesting argument, in this context and in general.

Should we be rooting for things that make supply of labor in our field more plentiful? Wouldn't it be in our self-interest to prevent as many people as possible from learning math and computer science? One could argue it wouldn't be in the interest of humans as a species, but I'm skeptical that the marginal loss to each of us is greater than the gain.
hermod
·il y a 6 ans·discuss
In fact, yes! This is counterintuitive if you think of the floats as a model for the reals, but in fact the floats give the wrong intuition, being (a finite subset of) rationals. [1] details this and refers to two related articles (particularly [2], which I find a lighter read). This fact is also remarked on in [3] (by example of the signum function being uncomputable).

For the particular example of a step function, consider the function f which is 1 on the positive reals (>=0) and 0 otherwise. What representation of the real numbers would you choose for the computation of f(0) to terminate in a finite amount of time? It cannot be the binary representation, as those are infinite. Your algorithm, terminating in a finite amount of time, will have checked only a finite number N of binary digits of the argument, and so I can choose x = 0.0{..N..}01 and obtain f(0) = f(x) by this algorithm, which is incorrect. You can choose the Cauchy sequence representation, or the Dedekind cut one, but this problem will persist (and [1] proves this in general).

You can "cheat" by saying that the leading two bits will store the sign of the number: 00 for 0, 01 for positive numbers and 10 for negative ones. But then suddenly arithmetic operations are not computable (see comments on [2])!

[1] https://lukepalmer.wordpress.com/2008/08/11/all-functions-ar...

[2] http://math.andrej.com/2006/03/27/sometimes-all-functions-ar...

[3] Vereshchagin, N., Shen, A. Computable Functions. https://bookstore.ams.org/stml-19/