Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

> It's poor because it's undecidable. We would ideally want to work with the real numbers, but no computational model can represent all real numbers (by a trivial cardinality argument).

This is a fallacy. The standard model for Computable Real Analysis, Type Two Effectivity, supports computation over all real numbers. See: https://en.wikipedia.org/wiki/Computable_analysis#Real_numbe...

Essentially, in TTE, a real number is an arbitrary stream of digits that can come from any source. Therefore any real number can be computed on.

Additionally, the ability to decide equality of floating point numbers is an illusion. Rounding errors can make numbers that ought to equal each other not equal each other.



You can compute on any real number you're given, but IIUC that's not what "computability" means. By the cardinality argument above (there are more infinite streams of digits than finite streams of digits, in an important sense) there will exist streams of digits that you cannot produce by any program (regardless of how you encode it).


You can produce an arbitrary infinite stream using a random number generator, for instance.


The probability of generating any given infinite stream is 0, though.


But, assuming you have a true random number generator, so is the probability that a stream you generate is computable.


Yes.


Where is the fallacy? I don't doubt type-2 effectivity is used in the way you mention, but that wasn't what I was talking about. See my other reply.




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

Search: