News for hackers. Stuff that matters.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by rocqua on Friday October 19, 2018 @03:38AM (#18254823)
> Effectively, it is a definition of computation that has so far been accepted because nothing fundamentally different and more powerful than a Turing machine has been exhibited.

Note that there is a commonly accepted extension that is more powerful than a Turing machine: Probabilistic Turing machines. I'm guessing the proof of equivalence generalizes to partial recursive functions and the lambda calculus if you add a 'random oracle'.

An interesting counter-argument is that real random oracles don't exist, and that in reality, we can simulate probabilistic computation using Pseudo Random Number Generators. So:

* True probabilistic computation isn't possible * And anyway, deterministic computation gets close enough to probabilistic computation through PRNGs

Alternatively, one might argue one could build a 'real' random oracle by reading from a 'true' random source. E.g. Cosmic microwave background, atmospheric noise, quantum fluctuations or a video of lava lamps. There is a difference between a random source and a random oracle, but with sufficient storage, that can be patched.

Re:Church-Turing Thesis Cannot Possibly Be True [video] by OscarCunningham on Friday October 19, 2018 @05:47AM (#18255448)
More powerful in what sense? The computable functions are the same for either type of machine.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by yters on Friday October 19, 2018 @03:49AM (#18254873)
Any PTM can be simulated by a DTM.