5 ms·

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

> 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 ago
If 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 ago
  If 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.
    - ikeboy 8y ago
      Only if it's measurable to infinite precision, and doesn't break down at e.g. Planck levels
      - dooglius 8y ago
        Right, I don't think physics is advanced enough yet to say whether anything can be measured with infinite precision. In the case of distance, our current understanding of quantum physics says this can't be done (or rather, the notion of distance is not meaningful beyond a certain precision), but I don't think there is any known limitation on generating quantum states of the form a|0>+b|1> where a and b are non-computable, in which case measuring these states over time could give a (probabilistically) infinite measurement.
        ikeboy 8y ago
        But can you make infinitely many states with same exact non computable numbers? Also once we're talking real world, entropy is finite and there's only so many computations you can do before you run out
    - tom_mellior 8y ago
- deleted 8y ago
  [deleted]
otabdeveloper1 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). No, this is a circular definition. We define an "algorithm" as something that can be performed by a Turing machine. So the Church-Turing thesis is a trivial tautology. (Though of course a useless one.)
- thfuran 8y ago
  That's a peculiar definition of algorithm.
- roywiggins 8y ago
  Not quite: https://en.wikipedia.org/wiki/Effective_method https://en.wikipedia.org/wiki/Effective_method "- It consists of a finite number of exact, finite instructions. - When it is applied to a problem from its class: - It always finishes (terminates) after a finite number of steps. - It always produces a correct answer. - In principle, it can be done by a human without any aids except writing materials. - Its instructions need only to be followed rigorously to succeed. In other words, it requires no ingenuity to succeed." "Several independent efforts to give a formal characterization of effective calculability led to a variety of proposed definitions (general recursion, Turing machines, λ-calculus) that later were shown to be equivalent."
- justinpombrio 8y ago
  > No, this is a circular definition. We define an "algorithm" as something that can be performed by a Turing machine. So the Church-Turing thesis is a trivial tautology. (Though of course a useless one.) No, that's a terrible definition, and it isn't what computer scientists typically use, though it might be what one says if they're not careful. If someone says that "algorithm" means "what a Turing machine can compute", it's because they believe the Church-Turing thesis, which says that they're the same. If they're the same, then you can talk about them interchangeably, and "Turing machine computations" have a cleaner definition than "pen and paper algorithms", so it's convenient to talk about "Turing machine computations" as if that's the ground truth. But if the Church-Turing thesis is false, then they're not the same, and you should be very careful not to mix them up. And we need a word for "the sorts of things you can compute by hand by a set of well-defined steps", and that's what "algorithm" has always meant. EDIT: Note that I'm making a prediction. If a person told you that "algorithm" means "what a Turing machine can compute", ask them what "algorithm" means if the Church-Turing thesis is false. My prediction is that they'll use a different defintion, based on what you can effectively compute by hand, like the "Effective Method" wikipedia article that my sibling posted.
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 ago
  Yeah, 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 ago
  Sure- 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 ago
  I 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.
joe_the_user 8y ago
This is not quite correct: No, my original statement is absolutely correct. Church-Turing is an approach, a labeling, a thesis, not a theorem. Not being a theorem, it is not subject to proof. One could exhibit a plausible argument that Church-Turing is wrong but that argument would not be a proof. It would not involve a sequence of mathematical argumentation that is standard for those artifacts which we call proofs. Just no. Pointing to a concrete algorithm would not be a "proof". Maybe it would be very persuasive and the world would be persuaded to abandon Church-Turing. Still it would not be a proof. Edit: I will admit my claim here involves a "mathematicians' thesis" that proofs are mathematical objects rather than just extra-strong arguments. So be it. I believe the whole reason Church-Turing is labeled a "thesis" rather than a theorem was because it's framers were using this distinction. And the distinction appears in the foundation of mathematics. Philosophers still argue for and against the continuum hypothesis even it's well not to be provable or disprovable - the argument is whether assuming it's true or falsehood produces good or bad mathematics. etc.

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 ago

If 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 ago
If 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.
  - ikeboy 8y ago
    Only if it's measurable to infinite precision, and doesn't break down at e.g. Planck levels
    - dooglius 8y ago
      Right, I don't think physics is advanced enough yet to say whether anything can be measured with infinite precision. In the case of distance, our current understanding of quantum physics says this can't be done (or rather, the notion of distance is not meaningful beyond a certain precision), but I don't think there is any known limitation on generating quantum states of the form a|0>+b|1> where a and b are non-computable, in which case measuring these states over time could give a (probabilistically) infinite measurement.
      - ikeboy 8y ago
        But can you make infinitely many states with same exact non computable numbers? Also once we're talking real world, entropy is finite and there's only so many computations you can do before you run out
  - tom_mellior 8y ago
deleted 8y ago
[deleted]

otabdeveloper1 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). No, this is a circular definition. We define an "algorithm" as something that can be performed by a Turing machine. So the Church-Turing thesis is a trivial tautology. (Though of course a useless one.)

thfuran 8y ago
That's a peculiar definition of algorithm.
roywiggins 8y ago
Not quite: https://en.wikipedia.org/wiki/Effective_method https://en.wikipedia.org/wiki/Effective_method "- It consists of a finite number of exact, finite instructions. - When it is applied to a problem from its class: - It always finishes (terminates) after a finite number of steps. - It always produces a correct answer. - In principle, it can be done by a human without any aids except writing materials. - Its instructions need only to be followed rigorously to succeed. In other words, it requires no ingenuity to succeed." "Several independent efforts to give a formal characterization of effective calculability led to a variety of proposed definitions (general recursion, Turing machines, λ-calculus) that later were shown to be equivalent."
justinpombrio 8y ago
> No, this is a circular definition. We define an "algorithm" as something that can be performed by a Turing machine. So the Church-Turing thesis is a trivial tautology. (Though of course a useless one.) No, that's a terrible definition, and it isn't what computer scientists typically use, though it might be what one says if they're not careful. If someone says that "algorithm" means "what a Turing machine can compute", it's because they believe the Church-Turing thesis, which says that they're the same. If they're the same, then you can talk about them interchangeably, and "Turing machine computations" have a cleaner definition than "pen and paper algorithms", so it's convenient to talk about "Turing machine computations" as if that's the ground truth. But if the Church-Turing thesis is false, then they're not the same, and you should be very careful not to mix them up. And we need a word for "the sorts of things you can compute by hand by a set of well-defined steps", and that's what "algorithm" has always meant. EDIT: Note that I'm making a prediction. If a person told you that "algorithm" means "what a Turing machine can compute", ask them what "algorithm" means if the Church-Turing thesis is false. My prediction is that they'll use a different defintion, based on what you can effectively compute by hand, like the "Effective Method" wikipedia article that my sibling posted.

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 ago
Yeah, 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 ago
Sure- 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 ago
I 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.

joe_the_user 8y ago

This is not quite correct: No, my original statement is absolutely correct. Church-Turing is an approach, a labeling, a thesis, not a theorem. Not being a theorem, it is not subject to proof. One could exhibit a plausible argument that Church-Turing is wrong but that argument would not be a proof. It would not involve a sequence of mathematical argumentation that is standard for those artifacts which we call proofs. Just no. Pointing to a concrete algorithm would not be a "proof". Maybe it would be very persuasive and the world would be persuaded to abandon Church-Turing. Still it would not be a proof. Edit: I will admit my claim here involves a "mathematicians' thesis" that proofs are mathematical objects rather than just extra-strong arguments. So be it. I believe the whole reason Church-Turing is labeled a "thesis" rather than a theorem was because it's framers were using this distinction. And the distinction appears in the foundation of mathematics. Philosophers still argue for and against the continuum hypothesis even it's well not to be provable or disprovable - the argument is whether assuming it's true or falsehood produces good or bad mathematics. etc.