-2
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 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, 2011 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, 2011 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, 2011 at 16:30
  • 2
    $\begingroup$ @JukkaSuomela: Your expertise has motivated me to ask a question about this. Thank you. $\endgroup$
    – Aaron Sterling
    Dec 6, 2011 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, 2011 at 12:16

1 Answer 1

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
1

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