7 ms·
OK, yeah, reading more[1] so I think the author is indeed considering things like computation on real numbers where, for example, the value of square root of tw
by joe_the_user 8y ago
OK, yeah, reading more[1] so I think the author is indeed considering things like computation on real numbers where, for example, the value of square root of two can only be approximated by a Turing machine but where ruler-and-compass construction hypothetically can construct this exactly.
So if you toss out the idea of computation involving digital computers, you can exhibit something not (exactly) Turing computable. If you have a chaotically behaving dynamic system and call it a computer, then you have something where computation becomes something in the eye of the beholder.
I'm not sure what questions this answers but there you are.
[1] https://www.researchgate.net/publication/221512843_What_Is_an_Algorithm https://www.researchgate.net/publication/221512843_What_Is_a...
- perl4ever 8y ago"the value of square root of two can only be approximated by a Turing machine but where ruler-and-compass construction hypothetically can construct this exactly." Ruler and compass are made of atoms though. Or, if not atoms, planck units or something.
- lisper 8y agoThe square root of 2 can also be computed exactly by a Turing machine. The result is exactly √2. What, that's cheating you say? You wanted an exact decimal expansion? Well, you're right, a Turing machine can't produce that. But neither can a ruler and compass.
- jfoutz 8y agoI’m pretty sure a Turing machine has infinite tape. So maybe it can represent that. But you’re going to have to wait a moment for it to print.
- MaxBarraclough 8y agoWhich leads us to a rather trivial conclusion: How many operations will it take to print the infinitely-many digits of the number? Infinity, of course. Same goes for printing 0 to an infinite number of decimal places.
- lisper 8y agoActually, a TM tape is unbounded, not infinite. Not the same thing.
- kps 8y agoBetter to say a Turing machine has unbounded tape. ‘Infinite’ can lead to slippery equivocations.
- mcguire 8y agoThink back to your geometry class. Mathematical geometry works with infinitely small points and has infinite precision. I suspect that the proof is that geometry is uncomputable.
- kaibee 8y agoThat seems to be the same thing as representing sqrt(2) as sqrt(2).
- lisper 8y agoYes, exactly my point.
- mcguire 8y agoYes, sort of. You can "compute" sqrt(2) by the geometric construction of a unit square and "drawing" the diagonal. You cannot do it physically, because marks on paper are not geometric primitives: points are not 0-dimensional; when drawn with a pencil, they have a physical size. A line on paper is not 1-dimensional, etc. But on the other hand, all physical computers are actually equivalent to finite state machines: they don't have infinite (or, unbounded) storage. I'm halfway through the video, and they are discussing this: the fundamental limit of Turing machines, etc., is that they cannot do an infinite (or unbounded) amount of work in a finite number of steps. As a result, geometric constructions a la Euclid are not computable.
- daveFNbuck 8y agoA Turing machine can compute the square root of two exactly. It can't represent it exactly as a fixed point number, but that's not the only way to compute something. There's a pretty standard definition of computable numbers [1] and it includes the square root of two. [1] https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number
- joe_the_user 8y agoSure, note I'm not trying to say the position being argued is right, I am simply trying to describe it as well as I can understand it. One might say that a "classical analogue" computer that "outputs" line segments could output the square root of two but an digital computer could merely "represent" it. That could be pure sophistry, especially since such classical analogue never have real infinite precision. But it seems like that's the sort of thing being claimed here.
- daveFNbuck 8y agoI'm having a hard time understanding the difference between outputting something and representing it. Can you explain the difference, or is that just your best understanding of the argument here?
- joe_the_user 8y agoAn output would be a physical extent in space (a line of some length, the turning of a dial, etc), a representation would be an description.
- daveFNbuck 8y agoUnder that definition, can Turing machines produce output at all? It seems that the Church-Turing thesis is about representations and not outputs.
- roywiggins 8y ago
- fnrslvr 8y agoThe burden is on the specifier of the compass and straight-edge algorithm to explain a reasonable mechanism for carrying out the steps exactly, to infinite precision. Without this, the procedure can only be expected to give a reliable approximation of sqrt(2) to some finite precision, which a Turing machine can match. A similar observation applies to chaotic systems. In general, a chaotic system can only be said to "solve" a problem if it can be configured to reliably arrive at (an encoding of) the solution for a given instance, despite any chaotic behaviour exhibited by the system. It wouldn't be reasonable to, for example, claim that a Turing machine cannot solve the problem of predicting the behaviour of a chaotic system with some particular initial conditions, if you couldn't reasonably conifgure the chaotic system itself to do that either.
- CJefferson 8y agoBy the same argument, doesnt that mean there can be no reliable Turing machine either, as quantum effects and random perturbations means that eventually your machine will calculate some logical expression wrong (and that's before we talk about running out of tape).
- AstralStorm 8y agoNot really, the machine can be built to exclude all sorts of probabilistic results to any given redundancy level. Probabilistic algorithms still work on Turing machines. What a standard Turing machine cannot do is entangle and superpose states. (It can only simulate it at high and variable cost.) Remember that a Turing machine is an abstract thing. Building an ideal one is not possible. You can try though.
- remcob 8y agoIn some sense the ruler-and-compass constructions are even more computable than the natural numbers: Any (first-order) statement in Euclidean geometry is either true or false and there is an algorithm (on a Turing machine) that can compute it. Natural numbers don't have this property due to Gödel incompleteness. In practice, anything you do with a ruler and compass has an equivalent representation in polynomials that is exactly computable.
- kps 8y agoFor the non-math readers, ruler-and-compass constructions are constructible numbers¹, which are a subset of algebraic numbers², which are a subset of computable numbers³, which are a tiny⁴ subset of complex numbers. ¹ http://mathworld.wolfram.com/ConstructibleNumber.html http://mathworld.wolfram.com/ConstructibleNumber.html ² http://mathworld.wolfram.com/AlgebraicNumber.html http://mathworld.wolfram.com/AlgebraicNumber.html ³ http://mathworld.wolfram.com/ComputableNumber.html http://mathworld.wolfram.com/ComputableNumber.html ⁴ http://mathworld.wolfram.com/MeasureZero.html http://mathworld.wolfram.com/MeasureZero.html
- Al-Khwarizmi 8y agoNot an expert on the Church-Turing thesis, but I suppose to find a counterexample, one has to be rigorous in defining the problem. And defining the problem includes defining the output. If the problem is "compute and output the decimal representation of the square root of two", then neither the human nor the Turing machine can do it in finite time, because that decimal representation is infinite. In fact, as far as I know this falls out of the scope of the Church-Turing thesis because most definitions of algorithms include that they must run in a finite number of steps, so there is no algorithm to do that. If the problem is "compute and output a symbolic representation of the square root of two" (in some symbol system where it is finite), then the human and the machine can both do it. If the problem is "compute and output a segment whose length is sqrt(2) times the length of this segment"... I don't think that's what computation is about. You might as well claim the Church-Turing thesis is false because a Turing machine cannot wave its hand.
- andrewla 8y agoThe problem is that the Church-Turing thesis is not rigorously defined, and it was in the attempt to rigorously define the parameters that the research in the video was done. I think that qualitatively we can agree that the ruler-and-compass construction of the square root of two is an algorithm. It's a repeatable procedure that can be described in a finite set of steps, and will always yield a provably correct answer. Whereas "waving a hand" is not an algorithm, but the same qualitative definition. The speaker wrote a paper that proved the Church-Turing thesis for sequential algorithms, primarily by defining in strict terms what a sequential algorithm is. Ruler-and-compass constructions are not sequential algorithms by this definition, and the difficulty in specifying the parameters for a generalized "algorithm" is apparently what leads him to the conclusion that the Church-Turing thesis cannot be true in general.
- jonathanstrange 8y agoAh, okay, so it boils down to the question whether real numbers are physically realizable. There is a debate about that in the philosophy of physics and mathematics. AFAIK, according to the current state of physics real numbers cannot be realized within a finite amount of space, at least Gisin [1] recently argued that way and I've seen other arguments for this view before [2,3,4,5:167-170]. I also remember some argument based on thermodynamics but cannot find the reference. [1] https://arxiv.org/pdf/1803.06824.pdf https://arxiv.org/pdf/1803.06824.pdf [2] https://arxiv.org/abs/math/0411418 https://arxiv.org/abs/math/0411418 [3] https://news.ycombinator.com/item?id=14080024 https://news.ycombinator.com/item?id=14080024 [4] https://ptolemy.berkeley.edu/~eal/pnerd/blog/are-real-numbers-real.html https://ptolemy.berkeley.edu/~eal/pnerd/blog/are-real-number... [5] https://www.sciencedirect.com/science/article/pii/S0304397507008778 https://www.sciencedirect.com/science/article/pii/S030439750...
- gowld 8y agoAre there any arguments in favor of "a noncountable subset of real numbers are physically realizable" ? That seems obviously false to me. The "debate" is one-sided; anyone who considers the problem comes to the same conclusion.
- tathougies 8y agoSquare root of two represented exactly in Haskell (turing equivalent): newtype Real = Real { isGreaterThan :: Rational -> Bool } sqrt2 :: Real sqrt2 = Real (\r -> r * r < 2) Doing arithmetic on these numbers is a more complicated matter. But this representation is exact.
- gowld 8y agoperhaps for clarity write that as newtype Real = Supremum { isGreaterThan :: Rational -> Bool } sqrt2 :: Real sqrt2 = Supremum (\r -> r * r < 2)
- kps 8y ago√2 is a bad example for this purpose; there are only countably many algebraic numbers.
- tathougies 8y agoMy representation is countable, but not because of the fact it uses the algebraic term 'r * r' in its definition of sqrt(2). My representation is based on dedekind cuts, implemented in Haskell, which is based on the lambda calculus. There are countably many lamdda terms. Thus, I can only represent countably many real numbers. My representation can store all the computable numbers, but there are computable numbers that are not algebraic. For example, e is not algebraic, but it is computable. Here is a representation of e factorials :: Rational factorials = 1:zipWith (*) [1..] factorials eApproxes :: [Rational] eApproxes = scanl (+) 0 (map recip factorials) e :: Rational e = Rational (\r -> any (r <) eApproxes)