3 ms·
So unbounded nondeterminism is basically hypercomputation? Then I assume one can write a program for the theoretical Actor model that computes a function on eve
by 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 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