3 ms·
Turing completeness can't be improved on. Are we sure of that though? I thought it was the case that the Church-Turing Thesis[1] was "widely considered to be t
by mindcrime 4y ago
Turing completeness can't be improved on.
Are we sure of that though? I thought it was the case that the Church-Turing Thesis[1] was "widely considered to be true" but had not been, in the strict sense, proven. If so, doesn't that leave open the at least the possibility of Hypercomputation[2] as a real thing?
[1]: https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
[2]: https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation
- cvccvroomvroom 4y agoWhat does a "hyperprogram" look like? What "problem" does a "hypercomputer" solve? If you can find a real P solution to Travel Salesman without redefining big O complexity or inventing magical computing, I'll give you a billion dollars.
- anyfoo 4y agoMeh, I obviously can't say anything definitively without hard proofs, but to me it feels similar to how P != NP is assumed to be true. As in, one can dream, but don't get your hopes up that we will even ever find out if the boring answer turns out to be true. From a distance, this type of "biological" computing just looks "very massively parallel" to me.
- cvccvroomvroom 4y agoAnd as in the Iota language, you only need the X combinator to do everything. (Sorry YC.)