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?


closed as off-topic by András Salamon, Jeffε, Yoshio Okamoto, Artem Kaznatcheev Apr 12 '14 at 3:15

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – András Salamon, Jeffε, Yoshio Okamoto, Artem Kaznatcheev
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    $\begingroup$ 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. $\endgroup$ – Aaron Sterling Dec 6 '11 at 16:00
  • 6
    $\begingroup$ That said, your question is not research-level, hence off topic for this site, so I am voting to close it. $\endgroup$ – Aaron Sterling Dec 6 '11 at 16:01
  • 4
    $\begingroup$ @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. $\endgroup$ – Jukka Suomela Dec 6 '11 at 16:30
  • 2
    $\begingroup$ @JukkaSuomela: Your expertise has motivated me to ask a question about this. Thank you. $\endgroup$ – Aaron Sterling Dec 6 '11 at 16:44
  • 4
    $\begingroup$ @SureshVenkat: As I understand this question, it is: Do we gain greater-than-halting computational power if two TM's are networked together such that one can communicate with the other in a random or asynchronous fashion? If that is indeed the question, then yes, I am still voting to close it. $\endgroup$ – Aaron Sterling Dec 7 '11 at 12:16

A single Turing machine can simulate a network of Turing machines and all communication between them (if you prefer to think about real computers, you could simulate/virtualize several computers on one computer).

So whatever a network of TMs can compute, a single TM can compute, too.


Not the answer you're looking for? Browse other questions tagged or ask your own question.