<p>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). </p>

<p>So whatever a network of TMs can compute, a single TM can compute, too.</p>

CC BY-SA 3.0
2012-05-06T21:34:16.510Z
This is nearly what I want to ask about http://cs.stackexchange.com/questions/438/is-interaction-more-powerful-than-algorithms
Hernán Eche
CC BY-SA 3.0
2011-12-06T16:13:24.043Z
2011-12-08T20:31:05.183Z
2011-12-08T20:31:05.183Z
Prateek
<p>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?</p>

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

<p>Is there any work on this? Has this equivalence been proven?</p>

<p>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 <em>perhaps</em> a Turing network may solve the halting problem?</p>

CC BY-SA 3.0
2011-12-06T16:00:29.933Z
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.
Aaron Sterling
CC BY-SA 3.0
2011-12-06T16:01:03.410Z
That said, your question is not research-level, hence off topic for this site, so I am voting to close it.
Aaron Sterling
CC BY-SA 3.0
2011-12-06T16:30:27.333Z
@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.
Jukka Suomela
CC BY-SA 3.0
2011-12-06T16:33:03.363Z
@AaronSterling Hello, I've asked because (even for error-free communication) I see a difference, I wrote in the question, it's about synchronization, If machines interrupt them desynchronized, I think, that can't be simulated within a single machine.
Hernán Eche
CC BY-SA 3.0
2011-12-06T16:44:09.130Z
@JukkaSuomela: Your expertise has motivated me to [ask a question](http://cstheory.stackexchange.com/q/9313/30) about this.  Thank you.
Aaron Sterling
CC BY-SA 3.0
2011-12-07T05:49:52.313Z
Not sure what to make of this @AaronSterling - do you still recommend closing even though there's enough in it for a related question ?
Suresh Venkat
CC BY-SA 3.0
2011-12-07T10:57:24.940Z
@HernánEche : Interruptions can easily be simulated: You can simply use an extra tape to record interruption information. Similar problems arise in an isolated machine (TM or processor) , for example maintaining data consistency and monitoring concurrency in databases and job scheduling in processors.
chazisop
CC BY-SA 3.0
2011-12-07T12:16:24.370Z
@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.
Aaron Sterling
<computability><turing-machines><dc.distributed-comp><halting-problem>
Is there any proof that a network made of Turing machines can't solve the halting problem?
Hernán Eche
# Is there any proof that a network made of Turing machines can't solve the halting problem?

(Asked by: username_0 on 2011-12-06)

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?

**Tags:** computability, turing-machines, dc.distributed-comp, halting-problem

> **Comments:**
> **username_1**: 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.  
> **username_1**: That said, your question is not research-level, hence off topic for this site, so I am voting to close it.  
> **username_2**: @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.  
> **username_0**: @AaronSterling Hello, I've asked because (even for error-free communication) I see a difference, I wrote in the question, it's about synchronization, If machines interrupt them desynchronized, I think, that can't be simulated within a single machine.  
> **username_1**: @JukkaSuomela: Your expertise has motivated me to [ask a question](http://cstheory.stackexchange.com/q/9313/30) about this.  Thank you.  
> **username_3**: Not sure what to make of this @AaronSterling - do you still recommend closing even though there's enough in it for a related question ?  
> **username_4**: @HernánEche : Interruptions can easily be simulated: You can simply use an extra tape to record interruption information. Similar problems arise in an isolated machine (TM or processor) , for example maintaining data consistency and monitoring concurrency in databases and job scheduling in processors.  
> **username_1**: @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.  

---

## 1 answers

### Answer by username_5 on 2011-12-06. Score: 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.

> **Comments:**
> **username_0**: This is nearly what I want to ask about http://cs.stackexchange.com/questions/438/is-interaction-more-powerful-than-algorithms  

---

