4 ms·
Issue is that a Turing Machine cannot communicate with other Turing Machines in the middle of a computation.
by ProfHewitt 5y ago
Issue is that a Turing Machine cannot communicate with other Turing Machines in the middle of a computation.
- oscardssmith 5y agoThis is just false. A Turing machine can emulate multiple Turing machines that communicate with each other.
- ProfHewitt 5y agoTuring machine can simulate multiple Turing Machines but cannot implement multiple Turing Machines communicating with each other because there is no means to communicate.
- oscardssmith 5y agoBut since Turing machines can emulate multiple Turing machines, any problem that can be completed by multiple machines communicating can be solved by 1 Turing machine. As such, the computational power is exactly the same.
- ProfHewitt 5y agoAs said elsewhere in this posting: Nondeterministic Turing Machine has only bounded nondeterminism. That is, for a given input a Nondeterministic Turing Machine can only explore the number of alternatives bounded by its input. Actors do not have the limitation.
- kaba0 5y agoLet me rephrase: an n-core CPU can be simulated on a Turing machine with eg. time sharing — effectively being able to simulate the Actor model.
- ProfHewitt 5y agoTuring Machine can only do cooperative multiprogramming and cannot do time-interrupted scheduling.
- kaba0 5y agoWell, not time-interrupted but there absolutely is a way to schedule n steps of each core, isn’t there? Similarly to how the universal Turing machine is constructed, or how the nondeterministic TM is made deterministic.
- ProfHewitt 5y agoNondeterministic Turing Machine has only bounded nondeterminism. That is, for a given input a Nondeterministic Turing Machine can only explore the number of alternatives bounded by its input. Actors do not have the limitation.
- kaba0 5y agoSo unbounded nondeterminism is basically hypercomputation? Then I assume one can write a program for the theoretical Actor model that computes a function on every natural number, is that right? Or that it can solve the halting problem for Turing machines, since if it is stronger then it, the halting problem of TMs is no longer true for them (is replaced by their own halting problem).
- ProfHewitt 5y agoAn Actor cannot decide the halting problem for program expressions. See proof in the following: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021
- tsimionescu 5y agoDoes this difference still hold if time were discrete? I may be out of my depth, but it seems intuitive that if time were discrete, you could enumerate all possible interleavings of actors' actions, and reproduce their behaviors in a Turing machine.