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.
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.
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.
- You can't output a voltage of sqrt(2) because you output a finite amount of electrons in each timeframe, so your resolution is limited.
- We don't know if you can output a signal of length of sqrt(2) because we aren't sure yet whether time is infinitely divisible [1]
- You might be able to position gears or other physical objects with infinite precision, but reading the value with a higher precision than one plank length seems impossible [2]
Computers can also work symbolically rather than based on some direct binary representation. I think equality and especially comparison become more difficult to determine, but it remains possible.
Here is a fully expanded representation: 1.
Of course my choice of base is a bit exotic, but the point is that no matter what, we're working on symbols. We're just used to seeing some as more direct analogues of numbers than others.
For a proof, consider the fact that every representable number, by definition (I know I haven't given a formal definition), is represented by some finite string. But the number of finite strings is countable. So it must be a measure zero subset of [0, 1], so a random sample is representable with probability zero.
How long is that piece of string?
a) Here, have a look at it. It's exactly that long.
b) 4.51 inches
both answers are correct. "a" is correct by definition. "b" may be totally correct if we add a precision to the answer, like +- 0.01 or whatever we find true.
With how much precision can you measure it?
With how much precision can you describe it?
The answers are pretty similar for humans or turing machines IMO.
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 [2] https://arxiv.org/abs/math/0411418 [3] https://news.ycombinator.com/item?id=14080024 [4] https://ptolemy.berkeley.edu/~eal/pnerd/blog/are-real-number... [5] https://www.sciencedirect.com/science/article/pii/S030439750...
Ruler and compass are made of atoms though. Or, if not atoms, planck units or something.
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.
Same goes for printing 0 to an infinite number of decimal places.
I suspect that the proof is that geometry is uncomputable.
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.
In practice, anything you do with a ruler and compass has an equivalent representation in polynomials that is exactly computable.
¹ http://mathworld.wolfram.com/ConstructibleNumber.html ² http://mathworld.wolfram.com/AlgebraicNumber.html ³ http://mathworld.wolfram.com/ComputableNumber.html ⁴ http://mathworld.wolfram.com/MeasureZero.html
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.
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.
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.
newtype Real = Supremum {
isGreaterThan :: Rational -> Bool
}
sqrt2 :: Real
sqrt2 = Supremum (\r -> r * r < 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)
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_a...