8 ms·

Turing Machine can only do cooperative multiprogramming and cannot do time-interrupted scheduling.

kaba0 5y ago
Well, 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 ago
  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 ago
    So 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 ago
      An 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 ago
    Does 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.
    - ProfHewitt 5y ago
      Bounded nondeterminism means that there is a bound determined by initial input for the number of possibilities that a system can explore given that it must always come back with an answer. A Nondeterministic Turing Machine has the property of bounded nondeterminism because it starts in a global state and from each state there are finitely many possible successor states. Because the machine must always produce an answer, each path must be finite and consequently the total number of states that can be explored is finite. In the development of a theory of concurrent computation, Dijkstra remained committed to a global state model of computation. This commitment gave rise to the “unbounded nondeterminism” controversy. Digital systems can be physically indeterminate by making use of arbiters in order to resolve reception order in communication between systems. Because of physical indeterminacy, a digital system can have the property of unbounded nondeterminism in that no bound exists when it is started on the number of possibilities that an always-responding digital system can explore. Consequently, there are digital computations that cannot be performed by a nondeterministic Turing Machine. Being restricted to bounded nondeterminism is one the reasons that the lambda calculus and Turing Machines models are inadequate for digital computation.
deleted 5y ago
[deleted]

Well, 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 ago
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 ago
  So 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 ago
    An 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 ago
  Does 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.
  - ProfHewitt 5y ago
    Bounded nondeterminism means that there is a bound determined by initial input for the number of possibilities that a system can explore given that it must always come back with an answer. A Nondeterministic Turing Machine has the property of bounded nondeterminism because it starts in a global state and from each state there are finitely many possible successor states. Because the machine must always produce an answer, each path must be finite and consequently the total number of states that can be explored is finite. In the development of a theory of concurrent computation, Dijkstra remained committed to a global state model of computation. This commitment gave rise to the “unbounded nondeterminism” controversy. Digital systems can be physically indeterminate by making use of arbiters in order to resolve reception order in communication between systems. Because of physical indeterminacy, a digital system can have the property of unbounded nondeterminism in that no bound exists when it is started on the number of possibilities that an always-responding digital system can explore. Consequently, there are digital computations that cannot be performed by a nondeterministic Turing Machine. Being restricted to bounded nondeterminism is one the reasons that the lambda calculus and Turing Machines models are inadequate for digital computation.

deleted 5y ago

[deleted]