3 ms·

could ML language models be turing complete if they are able to solve functions given parameters in English? e.g. “x is a variable. y is equal to two plus x. i

could ML language models be turing complete if they are able to solve functions given parameters in English? e.g. “x is a variable. y is equal to two plus x. if x is two, what is y?” and when run, it outputs four. what would be the implications of this?

frabert 6y ago
Maybe a lame answer, but it is my understanding that current ML models are based around neural networks, and NN can easily encode NAND gates which are universal, so they are already Turing-complete.
- bhntr3 6y ago
  Here's an interesting paper on the topic. It seems that only some NN architectures are turing complete: https://arxiv.org/pdf/1901.03429.pdf https://arxiv.org/pdf/1901.03429.pdf To the essence of what I think the original question is asking: It seems possible (due to the turing completeness of some NN architectures) that a language model could learn a sub-network that was a turing complete computational framework + problem solver and then use that to solve problems in natural language. But it also seems highly unlikely that it would actually play out that way. The linked paper has a nice summary of attempts to build neural nets that learn algorithms. It seems this more direct approach would be likely to yield a result faster than waiting for such a capability to emerge in GPT-12 or something. Of course most ML models execute from within a turing complete programming language/execution environment anyway. If we want to solve math problems, it might be easier to train a model to translate natural language into a more formal definition (afaik this is still very hard) and then hand off the formal definition of the problem to an automated theorem prover. After all, being turing complete doesn't make all problems solvable or tractable from a run time / memory perspective and that's probably the bigger bottleneck when it comes to solving hard math problems.
jobigoud 6y ago
> x is a variable. y is equal to two plus x. if x is two, what is y? Alternative answer: "y is a variable".

frabert 6y ago

Maybe a lame answer, but it is my understanding that current ML models are based around neural networks, and NN can easily encode NAND gates which are universal, so they are already Turing-complete.

bhntr3 6y ago
Here's an interesting paper on the topic. It seems that only some NN architectures are turing complete: https://arxiv.org/pdf/1901.03429.pdf https://arxiv.org/pdf/1901.03429.pdf To the essence of what I think the original question is asking: It seems possible (due to the turing completeness of some NN architectures) that a language model could learn a sub-network that was a turing complete computational framework + problem solver and then use that to solve problems in natural language. But it also seems highly unlikely that it would actually play out that way. The linked paper has a nice summary of attempts to build neural nets that learn algorithms. It seems this more direct approach would be likely to yield a result faster than waiting for such a capability to emerge in GPT-12 or something. Of course most ML models execute from within a turing complete programming language/execution environment anyway. If we want to solve math problems, it might be easier to train a model to translate natural language into a more formal definition (afaik this is still very hard) and then hand off the formal definition of the problem to an automated theorem prover. After all, being turing complete doesn't make all problems solvable or tractable from a run time / memory perspective and that's probably the bigger bottleneck when it comes to solving hard math problems.

jobigoud 6y ago

> x is a variable. y is equal to two plus x. if x is two, what is y? Alternative answer: "y is a variable".