News for hackers. Stuff that matters.
Re:Unprovability comes to machine learning by mike00632 on Tuesday January 08, 2019 @09:41PM (#18861838)
>we often make calculations with a finite, countable subset of real numbers.

We also often make calculations with finite subsets of rational numbers. We don't work with all of the rational numbers.

> We can only approximate the real numbers with finite precision.

The same can be said for rational numbers. It really matters that we can be arbitrarily precise when we talk about .333333... (one third), 1.41421... (square root of 2) or 3.14159... (pi) because we can be as exact as our calculations demand.

Re:Unprovability comes to machine learning by throwawaymath on Tuesday January 08, 2019 @11:31PM (#18862281)
Two points:

First, yes the rationals are already countable. But the reals are uncountable. You cannot write a function to generate all real numbers - not even if you allowed the function to run for an infinite amount of time.

Second, most of the reals are individually uncomputable, which literally means no, we cannot calculate them to arbitrary precision (or any exact precision).

Likewise we cannot just redefine the set of real numbers to be restricted to the set of computable reals. Analysis rapidly breaks down when you do so and it follows that the real field is no longer closed (by definition, and therefore no longer subject to the field axioms).

Re:Unprovability comes to machine learning by mike00632 on Wednesday January 09, 2019 @03:45PM (#18868670)
>Likewise we cannot just redefine the set of real numbers to be restricted to the set of computable reals. Analysis rapidly breaks down when you do so and it follows that the real field is no longer closed (by definition, and therefore no longer subject to the field axioms).

I was with you until you wrote that Analysis would break down. We can easily do analysis with dense subsets of the reals and also extensions of the reals, like in Non-Standard Analysis.

Re:Unprovability comes to machine learning by pure-awesome on Wednesday January 09, 2019 @03:13AM (#18863157)
> Likewise we cannot just redefine the set of real numbers to be restricted to the set of computable reals. Analysis rapidly breaks down when you do so and it follows that the real field is no longer closed (by definition, and therefore no longer subject to the field axioms).

Whilst this is true, I feel it should be noted that there exist constructive and computable versions of analysis which exist to work under under assumptions like "all the reals are computable".

Of course, the big difference is that we've mostly agreed on a single canonical version of the classical reals and of classical analysis, whilst there are numerous versions of different constructive analyses depending on what exactly you mean by "constructive".

Additionally many theorems of classical analysis "split up" into multiple independent versions which would be equivalent classically, but only some of which are true constructively.

Worse than that, often there is not a single definition of the "reals" any more. For example, two definitions of the reals (Dedekind Cuts and Cauchy Sequences) may result in entirely different objects constructively speaking. And, in fact, it may be that neither one is actually a good way of capturing the concept of a "real" "number" in that particular universe, so you need yet another definition.

As terrible as this might make it sound, it is worth the effort, in my opinion. In trying model the real world, classical mathematics throws away just a little bit too much information, in my opinion. This messiness is not just the result of wanting to work under some weird axioms, but an actual statement about the messiness of reality. Trying to sweep these issues under the rug is not a sustainable strategy if you eventually want to solve real-world problems.

Using classical mathematics is fine as a first-pass. It's a good way of investigating the problem under some simplifying assumptions and getting some good and useful results. But after that is done, it's not always enough to just declare the problem "solved" (or "unsolvable"). You need to consider what the practical version of the results will be, especially if you want to write a program to use them.

I am glad that the world is moving towards more computable and constructive versions of mathematics. It is still early days, and there are still way too many different takes on trying to solve the same mathematical issues, but soon enough we'll converge on a select few "generally acceptable" versions of constructive mathematics (in particular, something based on some form of constructive Type Theory) and we'll be able to reform our mathematical and scientific knowledge on a more stable base.

Re:Unprovability comes to machine learning by throwawaymath on Wednesday January 09, 2019 @07:48AM (#18864299)
Dedekind cuts and Cauchy sequences don't result in different reals. They're different methods of proof, but the resulting sets are isomorphic to one another, so they're structurally the same even if a real from one looks a bit different from a real in the other.

All the Dedekind cuts and Cauchy sequences do is tell us, in essence: "yes, the axiomatized reals you're using are correct and fine because there are constructive proofs of their existence." Moreover, the point of those proofs (and analysis more generally) is to demonstrate mathematical continuity and uncountability. No matter how you slice this problem, if you construct analysis you will lose computability along the way.

Re:Unprovability comes to machine learning by pure-awesome on Wednesday January 09, 2019 @09:06AM (#18864736)
I think there's perhaps a misunderstanding.

You are correct that under classical assumptions of logic ("normal" mathematics), the Dedekind Cuts and Cauchy Sequences indeed result in the construction of isomorphic objects.

However, under constructive assumptions of the logical axioms of mathematics, such as intuitionism (not accepting the law of excluded middle, i.e., assuming that the statement "P and NOT P" is not necessarily true for all P), the construction of the Dedekind Cuts and the Cauchy Sequences may result in different objects, i.e., it may no longer provable that they are equivalent.

Re:Unprovability comes to machine learning by roywiggins on Tuesday January 08, 2019 @10:26PM (#18862018)
We can effectively calculate all of the rationals to arbitrary precision, but we can't do that with all of the reals. Most of the reals have no effective procedure to calculate their decimal expansion.
Re:Unprovability comes to machine learning by mike00632 on Wednesday January 09, 2019 @03:53PM (#18868774)
Right, but we're getting away from illustrating the point of the paper, which isn't about number computability (interestingly) but about cardinality of sets. The intractability of this machine learning problem could have more to do with an absence of a successor function in the Real numbers than about the cardinality of uncomputable numbers. Or it could be a consequence of properties of differing infinite sets in general, like the difference between the Reals and the power set of the Reals. What I'm trying to get at is that we're not just talking about infinite decimal expansions.