Hacker News Reader

Hacker News

Comment by ProfHewitt | Hacker News Reader

Parent Full thread

ProfHewitt

There are very simple digital computations that cannot be

performed by a Nondeterministic Turing Machine.

See the following for an example:

https://papers.ssrn.com/abstract=3603021

View on HN

That would be a major revolution to the foundations of computer science if it were true, disproving the Church-Turing thesis. It seems unlikely that such a fundamental, world-shattering result would be so obscure, so I am much more likely to believe it is false.

Do you have any reasoning to back up your belief?

As I said, if someone had convincingly proved this, it would shake the field to its core. Since that didn't happen, they can't have convincingly proven this.

Scientific progress does occur!

Recent advances are compatible with a long tradition with

contributions by Euclid, Dedekind, Frege, Russell, Church, Turing, von Neumann, etc.

The following article is in furtherance of the long tradition:

https://papers.ssrn.com/abstract=3603021

That's 7 times you've linked to that paper in this discussion, going for some kind of record?

Have you read the article?

Can you suggest any improvements?

With all due respect, it would be very hard for me to believe so. For the simplest case, one can trivially create a Turing machine that simulates a CPU, so I’m not sure the digital computation holds any water.

Issue is that a Turing Machine cannot communicate with other Turing Machines in the middle of a computation.

This is just false. A Turing machine can emulate multiple Turing machines that communicate with each other.

Turing machine can simulate multiple Turing Machines but cannot implement multiple Turing Machines communicating with each other because there is no means to communicate.

But 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.

As 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.

Let 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.

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

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.

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.

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

An Actor cannot decide the halting problem for program

expressions. See proof in the following:

https://papers.ssrn.com/abstract=3603021

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.

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.

Reply on news.ycombinator.com