5 ms·
There are very simple digital computations that cannot be performed by a Nondeterministic Turing Machine. See the following for an example: https://papers.ss
by ProfHewitt 5y ago
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 https://papers.ssrn.com/abstract=3603021
- tsimionescu 5y agoThat 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.
- ProfHewitt 5y agoDo you have any reasoning to back up your belief?
- tsimionescu 5y agoAs 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.
- ProfHewitt 5y agoScientific 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 https://papers.ssrn.com/abstract=3603021
- jjgreen 5y agoThat's 7 times you've linked to that paper in this discussion, going for some kind of record?
- ProfHewitt 5y agoHave you read the article? Can you suggest any improvements?
- kaba0 5y agoWith 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.
- ProfHewitt 5y agoIssue 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 ago