Hacker News Reader

Comment by joe_the_user | Hacker News Reader

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_a...

View on HN

The 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.

By 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).

Not 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.

A 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

Sure, 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.

I'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?

An 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.

Under that definition, can Turing machines produce output at all? It seems that the Church-Turing thesis is about representations and not outputs.

The original formulation of the machine just operates on a tape, the closest thing to an output it has is moving the tape into a particular state (such as writing down the digits of the calculated function on successive cells of the tape). But there's no "output" function to spit out a number. You can just tack that onto the specification if you want, but it doesn't change the power of the device really.

I'm specifically asking about joe_the_user's definition of output as being a physical object rather than a number.

Or put differently:

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.

How long is that piece of string?

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.

The point is that we can represent sqrt(2) symbolically (as I just did there) but it cannot be represented as a binary (or decimal) expansion.

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.

But this merely a product of the choice of representation.

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.

What's a direct binary representation? If that means having each digit explicitly written out, no model of computation could possibly do that in finite time. If it means having the ability to output arbitrary bits in finite time, Turing machines can do that.

It's probably easier to give an example of a number that I can't represent symbolically. However, I can't give you a specific example, since if I uniquely define a number then that definition is itself a symbolic representation of that number. But here is an example: a uniformly random real number on [0, 1]. Or, computationally speaking, uniformly sample an infinite number of Bernoulli random variables, and write down the binary representation. Of course, this process takes infinite time, which suggests that they are not representable.

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.

I think even the ability of a (even non-digital) computer to output the square root of two isn't easily asserted. Quantum theory doesn't play nice with infinite precision.

- 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]

1: https://en.wikipedia.org/wiki/Chronon

2: https://en.wikipedia.org/wiki/Planck_length

Doesn't computable numbers, from the reference Wikipedia article, only state they can be computed to a given nth digit? Thus, in the OP's example, the rule-and-compass construction is exact whereas the Turing machine could only approximate the number (unless given infinite time, which I assume is out).

We need a digital representation of real numbers. One possible choice is: a real number r is represented as the source code of a function which takes a natural number n to the nth digit of r. This seems no more like “cheating” (and to me, it is less like cheating) than to represent a real number r by a line segment of length r.

Both representations have the feature that it's impossible to check whether two real numbers are equal.

Actually with the physical objects you could use one to occlude the other and test for light passage

Not with infinite precision.

Importantly, this is actually true of the real numbers.

I don't think I believe in "actual" real numbers.

That can't represent most real numbers, although I don't know that we have actually established that physical lengths can.

The catch is that you can't actually measure the rule-and-compass construction with infinite precision. You can perform more operations on the construction and then measure later to verify that it produced the correct result, but so can a turing machine acting on a mere "representation" of the number.

I don't think that's technically correct; I think it would be more correct to say that, for a given natural-number N precision, a Turing machine can calculate sqrt(2) to N precision, and there is no upper bound on N after which a Turing machine can't do it anymore. That's not the same as computing "the exact square root of 2" (only Chuck Norris can do that, of course).

The square root of two cannot be represented exactly in a finite decimal representation, but there are other ways to represent it exactly in finite space. We both know precisely which number we're talking about, despite using computers to represent it.

But "exactly representing it" just cashes out as "being able to answer questions to arbitrary precision about its value", and yep, TMs can do that do that, in finite space.

Ah, 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 [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...

Are 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.

"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.

The 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.

I’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.

Which 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.

Actually, a TM tape is unbounded, not infinite. Not the same thing.

Better to say a Turing machine has unbounded tape. ‘Infinite’ can lead to slippery equivocations.

Think 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.

That seems to be the same thing as representing sqrt(2) as sqrt(2).

Yes, exactly my point.

Yes, 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.

In 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.

For 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/AlgebraicNumber.html ³ http://mathworld.wolfram.com/ComputableNumber.html ⁴ http://mathworld.wolfram.com/MeasureZero.html

Not 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.

The 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.

Square 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.

perhaps for clarity write that as

    newtype Real = Supremum {
       isGreaterThan :: Rational -> Bool
    }

    sqrt2 :: Real
    sqrt2 = Supremum (\r -> r * r < 2)

√2 is a bad example for this purpose; there are only countably many algebraic numbers.

My 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)

Reply on news.ycombinator.com