3 ms·

Can neural networks solve the halting problem?

• dagav 8y ago
  No. Neural networks are still computed on Turing machines, which are mathematically proven to not be able to solve the halting problem.
  • segfaultbuserr 8y ago
    It doesn't matter if neural networks are computed on Turing machines or not. The term "compute" or "computation" is commonly defined by a Turing machine, as all other models have been shown to have equivalent power, and so far there is no indication that the Church-Turing thesis is false. So if one says a model can perform arbitrary computation, it cannot be stronger than a Turing machine, unless one is talking about hypercomputation, which is still largely a conjuncture. Just my two cents, correct me if I'm wrong.
    • contravariant 8y ago
      Well, you're not exactly wrong but what you're saying is a bit weird. Technically something capable of arbitrary computation in the Turing machine sense can be stronger than a Turing machine (the obvious example being a Turing machine with access to a halting oracle). Also if you want to show something is limited by the capabilities of a Turing machine it's way easier to point out it's being run on a Turing machine, as opposed to showing it's capable of arbitrary computation (which might not even be sufficient, as I explained above). As it stands it's not entirely obvious that a neural network with access to arbitrary precision arithmetic might not be more powerful than a Turing machine, but since we couldn't possibly construct a neural network precise enough that's a bit of a moot point.
  • AnaniasAnanas 8y ago
    If you are referring to our modern computers then they are actually computed on finite state machines - just with a lot of states. After all a Turing machine requires unbounded memory.
  • yters 8y ago
    So I guess neural networks can only compute a very small portion of all possible functions.
• deleted 8y ago
  [deleted]