3 ms·
That book doesn't touch any nondeterministic behavior at all. So, the nondeterministic extension of the Church-Turing Thesis is absolutely irrelevant here. You
by dandanua 6y ago
That book doesn't touch any nondeterministic behavior at all. So, the nondeterministic extension of the Church-Turing Thesis is absolutely irrelevant here. Your other cited "developments" seem senseful only in your personal universe.
- arethuza 6y agoYeah - its a long time since I studied this kind of stuff but I'm pretty sure the Church–Turing thesis doesn't say anything about non-determinism or not - being more relevant to complexity than computability?
- dandanua 6y agoThe original thesis concerns only computable functions, which are deterministic by definition. It doesn't even consider their complexity. There are extended variations of the thesis, though. The complexity variation means that any computable function in one model of computation can have only a polynomial slowdown factor in comparison with another model of computation. It's believed to be false since the raise of quantum computations.
- ProfHewitt 6y agoNondeterministic Turing Machines were introduced very early and became the basis for the Church/Turing Thesis. An important complexity result is that in important applications, a digital implementation can be hundreds of times faster that a parallel lambda expression. Consequently, the lambda calculus cannot be a practical foundation for computing. See the following for more information: "An Actor Application Can Be Hundreds of Times Faster Than a Parallel Lambda Expression" https://professorhewitt.blogspot.com/2021/03/an-actor-application-can-be-hundreds-of.html https://professorhewitt.blogspot.com/2021/03/an-actor-applic...
- ProfHewitt 6y agoThe Church/Turing Thesis is that all computation can be performed by a nondeterministic Turing Machine. The Thesis is false because there are digital computations that cannot be performed by a nondeterministic Turing Machine. See the following article on how to formalize all of digital computation: "Physical Indeterminacy in Digital Computation" https://papers.ssrn.com/abstract=3459566 https://papers.ssrn.com/abstract=3459566
- deleted 6y ago[deleted]
- ProfHewitt 6y agoNondeterministic Turing Machines are the standard for the Church/Turing Thesis. Do you have anything substantive to contribute to the discussion?