5 ms·
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
by andrewla 8y ago
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.
- cultus 8y agoYeah, 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 https://en.wikipedia.org/wiki/Hypercomputation
- deleted 8y ago[deleted]
- roywiggins 8y agoSure- 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.
- blablabla123 8y agoI 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.
- palunon 8y ago> 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
- SilasX 8y agoYeah, 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.