-2

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?

ouflak
  • 113
  • 1
  • 1
  • 6
Hernán Eche
  • 141
  • 4
  • 6
    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 Dec 06 '11 at 16:00
  • 6
    That said, your question is not research-level, hence off topic for this site, so I am voting to close it. – Aaron Sterling Dec 06 '11 at 16:01
  • 4
    @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 Dec 06 '11 at 16:30
  • @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 Dec 06 '11 at 16:33
  • 2
    @JukkaSuomela: Your expertise has motivated me to ask a question about this. Thank you. – Aaron Sterling Dec 06 '11 at 16:44
  • 1
    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 Dec 07 '11 at 05:49
  • @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 Dec 07 '11 at 10:57
  • 4
    @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 Dec 07 '11 at 12:16

1 Answers1

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.

Community
  • 1
Prateek
  • 455
  • 2
  • 11
  • This is nearly what I want to ask about http://cs.stackexchange.com/questions/438/is-interaction-more-powerful-than-algorithms – Hernán Eche May 06 '12 at 21:34