6 ms·

How would this affect the practical nature of the problem? Also, why is this novel? All machine learning algorithms can be implemented on a Turing machine, so

by yters 8y ago

How would this affect the practical nature of the problem? Also, why is this novel? All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem.

amelius 8y ago
> All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem. I think the argument should be the other way around.
- deleted 8y ago
  [deleted]
- deleted 8y ago
  [deleted]
fredgrott 8y ago
its the old Godel trick of translating it into a different form..ie what Godel originally did to prove his own theorem was to translate his theorem into symbolics and than negate it,.. In their example they are expressing it in set theory and than operating on it... I probably failed at explaining on a simple level...sorry
- rs86 8y ago
  Theorems are strings of symbols and can thus be encoded as numbers, and statements about numbers become statements about theorems. That's why the theorem applies to systems at least as strong as arithmetics
umanwizard 8y ago
What do you mean by "subject to the halting problem"? There are plenty of Turing machines that can be proven to halt. The halting problem doesn't say "given any Turing machine, no algorithm can determine whether it halts". It says "no algorithm can determine whether any given Turing machine halts".
yes_man 8y ago
> All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem. Assumption that all learning algorithms can be implemented on a Turing machine cannot hold true, since there are mathematical problems that cannot (take for example https://en.m.wikipedia.org/wiki/Hilbert%27s_tenth_problem https://en.m.wikipedia.org/wiki/Hilbert%27s_tenth_problem). Unless you categorise machine learning problems as problems that can be implemented with a Turing machine, making the statement a tautology. Edit: thinking about my comment maybe I am the one being tautologic. If there is a learning algorithm that can solve Hilbert's problem it would transcend mathematics
- umanwizard 8y ago
  "X can be implemented as a Turing machine" means the same thing as "there exists an algorithm to do X". Turing machines are just a formalization of the concept of algorithms/computer programs. So problems that can't be implemented as a Turing machine are not "learning algorithms", or any kind of algorithm.
  - deleted 8y ago
    [deleted]
  - __MatrixMan__ 8y ago
    I think that simplifies things a bit too far. A Turing Machine represents the most complete computational toolkit we happen to know of--not the most complete computational toolkit possible. If we discovered a new computational trick tomorrow--one that a Turing Machine can't perform (the ability to solve the halting problem for Turing Machines, for instance), then we would have discovered another--higher--class of computers, and it would be a reasonable linguistic move to refer to their programs as "algorithms" as well.
    - umanwizard 8y ago
      It is probably not possible to discover a new computational trick, by the Church-Turing thesis. The Church-Turing thesis can't be proven, since it is a statement about what is possible in the physical universe, not a statement about mathematics. But the intuitive arguments in favor of it (i.e., that Turing machines capture exactly what we mean by "computation") are, for me, extremely convincing.
rs86 8y ago
This is about the possibility of proving certain things about the model, not about properties of any implementation. Properties include for example the relation between the amount and quality of data available for training and the accuracy of the model. If a model is proven to learn too slowly it costs more to train it. And some models might never approximate a target function.
bnjmn 8y ago
I suspect the Halting Problem was already an obvious theoretical limitation to machine learning. Just imagine a network trained to classify programs according to whether or not they halt. Then construct a program that runs forever if the network says the program halts, and halts if the network says the program does not halt. No training strategy would ever produce a network that always gives the correct answer in this case. In the Generative Adversarial Network (GAN) framework, this would be the One Weird Trick the generator could pull that would always foil the discriminator. This paper is interesting because it connects learnability to a different kind of undecidability than the Halting Problem: the Continuum Hypothesis. In some ways it's more troubling than the Halting Problem, because at least we can usually figure out whether some actual program halts, using some cleverness, but no one can begin to say whether the Continuum Hypothesis is true or false. The Continuum Hypothesis is more like P!=NP, in that most mathematicians suspect the CH is true (that is, there's no cardinality in between the integers and the reals). That's good news, because it implies the EMX learning model will work: > Their results imply that the finite subsets of the unit interval have monotone-compression schemes, and therefore are learnable in EMX, if and only if the continuum hypothesis is true, which is known to be unprovable. If someone comes along and casts doubt on the Continuum Hypothesis through some mystical but persuasive line of reasoning (news flash: not gonna happen), then there might be some EMX functions that can't be learned, but no one is going to lose sleep over that. There are lots of more immediate reasons why machine learning fails in practice, like not having good training data.
- baddox 8y ago
  I'm confused. I'm pretty sure that the issue isn't "no one can begin to say whether the Continuum Hypothesis is true or false," but rather that we know it to be independent of the widely-used axiomatic set theories (at least ZFC). Since "truth" is defined in terms of the chosen axioms, and we have proven that the axioms of ZFC can neither prove nor disprove the continuum hypothesis, that means that we already know that you could arbitrarily choose to use "ZFC with CH" or "ZFC with !CH" and either will be consistent (or as consistent as plain old ZFC). > The Continuum Hypothesis is more like P!=NP, in that most mathematicians suspect the CH is true (that is, there's no cardinality in between the integers and the reals). I don't think this is correct. It's very well-accepted that CH is independent of ZFC. Now, you might mean that most mathematicians suspect that adding CH to ZFC is more intuitive/natural/useful than adding !CH to ZFC, but that's a quite different statement. I don't know much about this, but it seems plausible that both extensions of ZFC could be useful for different things, in the same way that using the parallel postulate is useful for some things (Euclidean geometry) and using alternative parallel postulates is useful for other things (non-Euclidean geometries). The P=NP problem, AFAIK, isn't yet proven to be independent of ZFC, although I have heard some seemingly educated people suggest their suspicions that it may be. And now you have me wondering if you win the Millennium Prize if you prove that P=NP is independent of ZFC. Surely you would.
gowld 8y ago
It's novel because no one had bothered to prove the result before. It's not an earth-shattering paper, it's a technical curiosity. the OP is a light article about a light paper, to promote a new lightweight journal that launched this week. https://www.nature.com/natmachintell/ https://www.nature.com/natmachintell/
Sniffnoy 8y ago
As other commenters have pointed out, this is backwards. The unsolvability of the halting problem says that there is no one algorithm that can tell you whether an arbitrary Turing machine will halt. But for special types of Turing machines, it is often possible to say whether they will halt. So, if you define a special type of Turing machine, and it turns out that the halting problem is unsolveable even for that restricted type, that is noteworthy.

by yters 8y ago

amelius 8y ago

> All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem. I think the argument should be the other way around.

deleted 8y ago
[deleted]
deleted 8y ago
[deleted]

fredgrott 8y ago

its the old Godel trick of translating it into a different form..ie what Godel originally did to prove his own theorem was to translate his theorem into symbolics and than negate it,.. In their example they are expressing it in set theory and than operating on it... I probably failed at explaining on a simple level...sorry

rs86 8y ago
Theorems are strings of symbols and can thus be encoded as numbers, and statements about numbers become statements about theorems. That's why the theorem applies to systems at least as strong as arithmetics

umanwizard 8y ago

What do you mean by "subject to the halting problem"? There are plenty of Turing machines that can be proven to halt. The halting problem doesn't say "given any Turing machine, no algorithm can determine whether it halts". It says "no algorithm can determine whether any given Turing machine halts".

yes_man 8y ago

> All machine learning algorithms can be implemented on a Turing machine, so they all are subject to the halting problem. Assumption that all learning algorithms can be implemented on a Turing machine cannot hold true, since there are mathematical problems that cannot (take for example https://en.m.wikipedia.org/wiki/Hilbert%27s_tenth_problem https://en.m.wikipedia.org/wiki/Hilbert%27s_tenth_problem). Unless you categorise machine learning problems as problems that can be implemented with a Turing machine, making the statement a tautology. Edit: thinking about my comment maybe I am the one being tautologic. If there is a learning algorithm that can solve Hilbert's problem it would transcend mathematics

umanwizard 8y ago
"X can be implemented as a Turing machine" means the same thing as "there exists an algorithm to do X". Turing machines are just a formalization of the concept of algorithms/computer programs. So problems that can't be implemented as a Turing machine are not "learning algorithms", or any kind of algorithm.
- deleted 8y ago
  [deleted]
- __MatrixMan__ 8y ago
  I think that simplifies things a bit too far. A Turing Machine represents the most complete computational toolkit we happen to know of--not the most complete computational toolkit possible. If we discovered a new computational trick tomorrow--one that a Turing Machine can't perform (the ability to solve the halting problem for Turing Machines, for instance), then we would have discovered another--higher--class of computers, and it would be a reasonable linguistic move to refer to their programs as "algorithms" as well.
  - umanwizard 8y ago
    It is probably not possible to discover a new computational trick, by the Church-Turing thesis. The Church-Turing thesis can't be proven, since it is a statement about what is possible in the physical universe, not a statement about mathematics. But the intuitive arguments in favor of it (i.e., that Turing machines capture exactly what we mean by "computation") are, for me, extremely convincing.

rs86 8y ago

This is about the possibility of proving certain things about the model, not about properties of any implementation. Properties include for example the relation between the amount and quality of data available for training and the accuracy of the model. If a model is proven to learn too slowly it costs more to train it. And some models might never approximate a target function.

bnjmn 8y ago

I suspect the Halting Problem was already an obvious theoretical limitation to machine learning. Just imagine a network trained to classify programs according to whether or not they halt. Then construct a program that runs forever if the network says the program halts, and halts if the network says the program does not halt. No training strategy would ever produce a network that always gives the correct answer in this case. In the Generative Adversarial Network (GAN) framework, this would be the One Weird Trick the generator could pull that would always foil the discriminator. This paper is interesting because it connects learnability to a different kind of undecidability than the Halting Problem: the Continuum Hypothesis. In some ways it's more troubling than the Halting Problem, because at least we can usually figure out whether some actual program halts, using some cleverness, but no one can begin to say whether the Continuum Hypothesis is true or false. The Continuum Hypothesis is more like P!=NP, in that most mathematicians suspect the CH is true (that is, there's no cardinality in between the integers and the reals). That's good news, because it implies the EMX learning model will work: > Their results imply that the finite subsets of the unit interval have monotone-compression schemes, and therefore are learnable in EMX, if and only if the continuum hypothesis is true, which is known to be unprovable. If someone comes along and casts doubt on the Continuum Hypothesis through some mystical but persuasive line of reasoning (news flash: not gonna happen), then there might be some EMX functions that can't be learned, but no one is going to lose sleep over that. There are lots of more immediate reasons why machine learning fails in practice, like not having good training data.

baddox 8y ago
I'm confused. I'm pretty sure that the issue isn't "no one can begin to say whether the Continuum Hypothesis is true or false," but rather that we know it to be independent of the widely-used axiomatic set theories (at least ZFC). Since "truth" is defined in terms of the chosen axioms, and we have proven that the axioms of ZFC can neither prove nor disprove the continuum hypothesis, that means that we already know that you could arbitrarily choose to use "ZFC with CH" or "ZFC with !CH" and either will be consistent (or as consistent as plain old ZFC). > The Continuum Hypothesis is more like P!=NP, in that most mathematicians suspect the CH is true (that is, there's no cardinality in between the integers and the reals). I don't think this is correct. It's very well-accepted that CH is independent of ZFC. Now, you might mean that most mathematicians suspect that adding CH to ZFC is more intuitive/natural/useful than adding !CH to ZFC, but that's a quite different statement. I don't know much about this, but it seems plausible that both extensions of ZFC could be useful for different things, in the same way that using the parallel postulate is useful for some things (Euclidean geometry) and using alternative parallel postulates is useful for other things (non-Euclidean geometries). The P=NP problem, AFAIK, isn't yet proven to be independent of ZFC, although I have heard some seemingly educated people suggest their suspicions that it may be. And now you have me wondering if you win the Millennium Prize if you prove that P=NP is independent of ZFC. Surely you would.

gowld 8y ago

It's novel because no one had bothered to prove the result before. It's not an earth-shattering paper, it's a technical curiosity. the OP is a light article about a light paper, to promote a new lightweight journal that launched this week. https://www.nature.com/natmachintell/ https://www.nature.com/natmachintell/

Sniffnoy 8y ago

As other commenters have pointed out, this is backwards. The unsolvability of the halting problem says that there is no one algorithm that can tell you whether an arbitrary Turing machine will halt. But for special types of Turing machines, it is often possible to say whether they will halt. So, if you define a special type of Turing machine, and it turns out that the halting problem is unsolveable even for that restricted type, that is noteworthy.