7 ms·
This seems like really exotic stuff. It's one of those talks that seems to talk about things I know but then immediately jumps to theories and definitions I ha
by joe_the_user 8y ago
This seems like really exotic stuff.
It's one of those talks that seems to talk about things I know but then immediately jumps to theories and definitions I have never heard of. "Sequential algorithms were axiomatized in 2000" - This "axiomization" was apparently performed by the author of the talk, my Googling says. All links about things talked in this talk just seem to lead to other texts and such by this author. Might not be a good sign but maybe it's just a very hard to grasp realm.
Anyway, broadly, the Church-Turing thesis is not a theorem and cannot be proven true or false (so said my professors and Wikidepia). 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 (there is a theorem that Turing machines, partial recursive functions and the lambda calculus are equivalent - and then there's the jump to "these are really general and I think that about covers it" but still, not a theorem, not provable).
My hunch is the author is mixing in "higher-order" logic "version of Church-Turing" into their argument. Which is basically "cheating", switching to an effectively different question without making things clear. However, I simply don't know. This is basically opaque to my mere MA-level maths.
- joe_the_user 8y agoOK, 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).
- 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)
- rocqua 8y ago> 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.
- yters 8y agoAny PTM can be simulated by a DTM.
- OscarCunningham 8y agoMore powerful in what sense? The computable functions are the same for either type of machine.
- tom_mellior 8y ago> the Church-Turing thesis is not a theorem and cannot be proven true or false This is not quite correct: It cannot be proven true. But it could be proven false with a counterexample. The speaker would simply have to point to a concrete algorithm that can be performed by a person with pencil and paper but not by a Turing machine (or vice versa). I haven't had the time to watch the video, but from the comments here it appears that the speaker did not provide such an example.
- lmm 8y ago> The speaker would simply have to point to a concrete algorithm that can be performed by a person with pencil and paper but not by a Turing machine (or vice versa). Humans do all sorts of things that Turing machines don't (e.g. a Turing machine can't hold a pencil), so the question there is what constitutes an "algorithm" which comes right back to the definition of computation. Even an example that was obviously "computation" in the intuitive sense wouldn't make the Church-Turing definition "false", it would just mean that it defines something different from what we thought it defines.
- dooglius 8y agoIf theoretical physics can find a complete model of all particles and spacetime, and we can show that a Turing Machine can emulate it, then that would suffice.
- tom_mellior 8y agoIf you can write down the Turing machine for anything, then a person with pencil and paper can simulate its execution. That direction doesn't appear to be the way to go. Despite the generality of what I wrote above, the only feasible counterexample would be one that people can do on paper but a Turing machine somehow can't.
- dooglius 8y ago>If you can write down the Turing machine for anything, then a person with pencil and paper can simulate its execution What you're describing is the reverse direction, simulating a TM with pencil and paper, and this is doable so long as you are allowed two stacks of paper to work with, and an unlimited supply of pencil/paper. The question of simulating TMs in the real world really doesn't have anything to do with the Church-Turing thesis, though. >Despite the generality of what I wrote above, the only feasible counterexample would be one that people can do on paper but a Turing machine somehow can't. If some dimensionless measurable physical constant were a non-computable number, then the Church-Turing thesis would be false. In fact, if we think that certain quantities are in some sense random or arbitrary, rather than something that could be written as an equation, we should expect the Church-Turing thesis to be false with probability 1.