The Continuum Hypothesis [0] (which the authors are saying the learning problem is isomorphic [1] to) is not provable from the axioms of set theory. You can add "The Continuum Hypothesis is true" OR "The Continuum Hypothesis is false" to the axioms, and still have consistent mathematics.
[0] Continuum hypothesis is that the set of Integers (0, -1, 1, -2, 2, ...) is infinite but smaller than the set of Reals (Integers + Rationals + Irrationals), and there are no infinite sets with size smaller than the Reals, but larger than the Integers.
[1] not sure of correct term here - the point is that they have shown the problems are the same.
Actually, some undecidable problems are NP hard, like the halting problem. That is, a halting oracle gives a polynomial time algorithm for any NP problem.
I'm not sure what you mean with "can be solved", but I would spell it out a bit different:
There are NP-hard problems that are undecidable, that means, there is no algorithm that can decide the question for every input. However, in some instances we are able to solve these problems (even quite easy). For example we know that an algorithm like "while TRUE DO (nothing) END" will never terminate, even though the halting problem is undecidable.
However, if a NP-hard problem is also in NP, than it can be solvend. But it will take exponential time in the worst case. That, too, does not mean that in some instance we are able to solve them in reasonable time.
This is wrong. NP-hard problems can be solved, they just appear to hard to solve efficiently. NP-hard problems are always decidable, like everything in polynomial hierarchy (P, NP, co-NP, and higher classes that have oracle access to lower classes).
Undecidable problems e.g. the Halting problem cannot generally be solved using an algorithm (so it has to be solved on a case-by-case basis and requires "creativity").
Sorry, but you are flat out wrong. For example, the halting problem is NP-hard and undecidable [1]
I think you might confuse NP-hard with NP-complete. There are problems that are NP-hard, not in NP and unsolvable. If a problem is NP-hard _and_ in NP, then they can always be solved.
There are an infinite number of complexity classes that are (probably) harder than NP. Popular ones include PSPACE and EXPTIME. You might want to google for "polynomial hierachy".
There's got to be more to it than that. The halting problem itself isn't some on-off switch, it can be studied and broken down into different problem classes, some of which are indeed decidable.
It's just impossible to write a general-purpose algorithm to solve it in all cases.
“It's just impossible to write a general-purpose algorithm to solve it in all cases.” That is the definition of an undecidable problem. Independence, as in Euclid’s fifth postulate, is not what we typically think of as undecidability, though can be referred to as such.
That is incorrect. The halting problem can be answered -- every Turing Machine either halts or does not halt on a given input. Undecidable only means that we cannot have a single algorithm that outputs the correct answer in every case.
This is the first paragraph from the Wikipedia article on undecidable problems: “In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: there is no algorithm that correctly determines whether arbitrary programs eventually halt when run.” https://en.m.wikipedia.org/wiki/Undecidable_problem
Disclaimer: I'm really noob, not asking it sarcastically.