News for hackers. Stuff that matters.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by andrewla on Friday October 19, 2018 @09:28AM (#18256554)
He does in fact provide at least one counterexample (around 18:55 in the video).

One is the real-number GCD algorithm; basically the same as Euclid's standard GCD algorithm, but with real numbers. He seems to be arguing that since Turing machines cannot represent real numbers, they cannot compute this algorithm. On the other hand, it can be easily computed with pen and paper, and he gives an example of a ruler-and-compass algorithm for evaluating it.

To me this seems a little wishy-washy; a Turing machine can approximate the problem to an arbitrary degree of precisions, just as a pen-and-paper approach is only capable to executing to a finite degree of approximation. Still, an "idealized" ruler and compass does provide a framework for describing an algorithm which is not directly Turing computable.

Re:Church-Turing Thesis Cannot Possibly Be True [video] by roywiggins on Friday October 19, 2018 @10:21AM (#18256892)
Sure- if you have access to exact real numbers, you have something more powerful than a Turing machine. But there's no evidence that that's physically possible. The Church-Turing thesis is about actual computation that could happen in the world, not theoretical models, of which there are many that can perform hypercomputation.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by SilasX on Friday October 19, 2018 @01:02PM (#18258126)
Yeah, I agree, but from the opposite side: the human isn't really doing the real-number version either, because you can't represent a full real number. You're just doing an arbitrary approximation of the real number, which -- of course! -- Turing machines can do too.
Re:Church-Turing Thesis Cannot Possibly Be True [video] by blablabla123 on Friday October 19, 2018 @12:48PM (#18257999)
I mean when talking about real numbers this way, we mean numbers that can only we represented as compositions of periodic digits, or worse, transcendental numbers which lack even periodicity. However, unless you do Numerics, you probably choose a different representation, for instance as series. This is precise and there is a choice of Computer Algebra Systems available for that.

In fact Algebra has very deep connections to pen and paper geometry.

Apart from that... Due to the increased use of statistics, the postulates of CS might shift. One example being CAP theorem.

Re:Church-Turing Thesis Cannot Possibly Be True [video] by palunon on Friday October 19, 2018 @03:07PM (#18259134)
> we mean numbers that can only we represented as compositions of periodic digits, or worse, transcendental numbers which lack even periodicity

Every number that has periodicity in its decimals is rational... √2 doesn't have periodic decimals.

Transcendental numbers are non algebraic numbers, ie. they are not the root of any non zero polynomial with rational coefficient. √2 is algebraic

Re:Church-Turing Thesis Cannot Possibly Be True [video] by cultus on Friday October 19, 2018 @09:37AM (#18256595)
Yeah, that's a nonsensical "proof."

> Still, an "idealized" ruler and compass does provide a framework for describing an algorithm which is not directly Turing computable.

You could describe such an algorithm, but you could not do it in this universe. This is called hypercomputation.

"If non-computable inputs are permitted then non computable outputs are attainable"

https://en.wikipedia.org/wiki/Hypercomputation