Neural networks are Turing machines. You can make them perform any computation by carefully setting up their weights. It would be nice to have compilers for them that were not based on approximation, though.
Could you elaborate?
TFA is a beautiful step in that direction. What I want is an automated way to do this, without having to hire vgel every time.
As an example, algebraic type systems are often TC simply because general recursion is allowed.
Feed forward networks are effectively DAGs and while you may be able to express any algorithms using them they are also pairwise linear in respect to inputs.
Statistical learning is powerful in finding and matching patterns, but graph rewriting, which is what your doing with initial random weights and training is not trivial.
More importantly it doesn't make issues like the halting problem decidable.
I don't see why the same limits in graph rewriting languages which were explored in the 90s won't hit using feed forward networks as computation systems outside of the application of nation-state scale computing power.
But I am open to understanding where I am wrong.
I review a few papers on the topic here: https://blog.wtf.sg/posts/2023-02-03-the-new-xor-problem/
It's not that we don't know how to set the weights - neural networks are only designed with weights because it makes them easy to optimize.
There is no reason to use them if you plan to write your own code for them. You won't be able to do anything that you couldn't do in a normal programming language, because what makes NNs special is the training process.
The generality of the approach [NNs] implies that they are effectively a union of all programs that may be represented, and as such there needs to be the capacity for that, this capacity is in size, which makes them wasteful for exact solutions.
it is fairly trivial to create FFNNs that behave as decision trees using just relus if you can encode your problem as a continuous problem with a finite set of inputs. Then you can very well say that this decision tree is, well, a program, and there you have it.
The actual problem is the encoding, which is why NNs are so powerful, that is, they learn the encodings themselves through grad descent and variants.
Its like going from computing PI as a constant to computing it as a giantic float.
You lose info
RASP https://arxiv.org/abs/2106.06981
python implementation: https://srush.github.io/raspy/
And even if we could try to solve this problem, there is no known way of verifying the solution would be correct in general.
My point was that Transformers and neural networks as they are now are not Turing machines if you don't allow for the model to grow with the input size. That said, it has to grow in "depth" not just parameters. The fact that people think fixed depth computation can universally compute everything is a worrying trend.