Hacker News new | past | comments | ask | show | jobs | submit login

> in applied maths ... all functions are continuous

I guess that's related to the fact that all computable functions from real numbers to real numbers are continuous. It seems reasonable that the laws of physics should be computable to a large extent otherwise we'd have been able to build a hypercomputer by now.




A step function is not computable?


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/


If I gave you 0.0000000... as input, you would have to scan forever to find out whether I put in a nonzero digit. Scanning to a partial depth would not result in partial accuracy, because the step function is discontinuous.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: