# Is there any proof that a network made of Turing machines can't solve the halting problem? [closed]

My question points to the fact that Turing machines are isolated by definition. But what if they can send and receive information from/to other Turing machines? What if they can be "interrupted" at any time by communication with other Turing machines?

I think this problem is different, and perhaps gives different answer to the halting problem. But I don't know.

Is there any work on this? Has this equivalence been proven?

If someone found a single example where a non-computable algorithm (with a single universal Turing machine) becomes computable with a network, could it mean that perhaps a Turing network may solve the halting problem?

• If the communication channels of the network are error-free, then your question is not very interesting. This is because you could have just one computer simulating multiple threads or machines, and not "communicating" with itself very often. However, if the communication channel can be faulty sometimes, then it is possible to prove that certain computations are impossible to perform, even if all the computers in the network are able to solve the Halting Problem because of some magical powers. The first such result was the famous FLP result in distributed computing. Dec 6, 2011 at 16:00
• That said, your question is not research-level, hence off topic for this site, so I am voting to close it. Dec 6, 2011 at 16:01
• @AaronSterling: But you are implicitly assuming that the network is finite. There are graph problems that can be solved with a constant-time distributed algorithm. Many of these problems and algorithms have a perfectly reasonable generalisation to infinitely large (but locally finite) graphs. Hence we can say that a network of Turing machines can solve certain infinitely large problem instances in finite time, while a single Turing machine cannot even read the infinitely large input in finite time. Dec 6, 2011 at 16:30