Hacker News Reader

Comment by curtisf | Hacker News Reader

Without more setup, you haven't described a problem that would normally be classifiable as computable or non-computable.

A real number, in general, requires an infinite number of bits to describe, so it cannot be used as the input to an algorithm in standard models of computation such as Turing machines.

However, the version where the numbers have finite representations (such as floating point, fixed point, or rational numbers) are trivially computable.

There are results for particular finite representations of certain kinds of real numbers, such as https://en.m.wikipedia.org/wiki/Richardson%27s_theorem which applies to the equality of expressions involving arithmetic, exponentiation, and trigonometry, but I don't think this is clearly a geometric problem since the space of such mathematical expressions doesn't really have any obvious geometry

View on HN

> A real number, in general, requires an infinite number of bits to describe

Which is why any charitable, non-sarcastic reading of my comment would take it to be referring to a subset of reals which are compatible with TMs and which make the claim true, instead of pointing out every possible way to misinterpret my comment deliberately. Be better.

You could have said it's a function CR x CR -> 2 to refer to the Computable Reals. Instead you explicitly made it about the reals R, making it hard to be charitable.

All the ways of encoding Reals that you mention in your comment are limited to Rationals. It seems like you just didn't know that one can encode Reals too, which puffoflogic assumed readers to know.

Yes, they could have made their comment more accessible and mentioned the encoding (but I think then the problem may have sounded less "natural", since you'd have Turing machines mentioned). But you also could have noticed you're building a strawman argument, and instead just asked how does one encode Reals. Heuristics: if other person's argument sounds too absurd, there's a chance you're misunderstanding something.

If you claim a construction is obvious and dispells confusion, that construction should not have any readings that are obviously wrong.

Sure, charitable readings of informed readers will find it obvious. But less informed readers, or skeptical readers, will see the wrong interpretation. For a skeptical reader to then think "since they state its obvious, perhaps they refer to the general uncomputability of the reals", is not surprising.

Regarding the actual construction, once its well formulated, it becomes a lot less 'natural'. Since the definition is already taking about computable (or representable) reals, it is much less surprising that the result is a non-computable function. The beauty of the example is that the definition of the function never refers to any ideas from computational theory. Hence the article serves as a counter example to the theory "You never get uncomputable functions in fields outside of computational theory".

Reply on news.ycombinator.com