5 ms·

The first part of the first paragraph is wrong: > Nearly a century ago, Alonzo Church invented the simple, elegant, and yet elusive lambda calculus. Along with

The first part of the first paragraph is wrong: > Nearly a century ago, Alonzo Church invented the simple, elegant, and yet elusive lambda calculus. Along with Alan Turing, he then proved the Church-Turing thesis: that anything computable with a Turing machine can also be computed in the lambda calculus. The Church-Turing thesis is not something one can prove. It's more like an intuition and/or definition we have. It states that anything that is computable can be computed with a Turing machine. See [1]. "Anything computable with a Turing machine can also be computed in the lambda calculus" this is true but it not the Church-Turing thesis and its called a Turing-equivalence. This was also not proved by Church, but by Turing in an appendix to his paper [2]. About a computation model being Turing-equivalent: the fact that most reasonable computation models we came up with were proven to be Turing-equivalent is one of the reasons we believe in the Church-Turing thesis. [1] https://plato.stanford.edu/entries/church-turing/ https://plato.stanford.edu/entries/church-turing/ [2] https://link.springer.com/article/10.1007/s10506-017-9200-2 https://link.springer.com/article/10.1007/s10506-017-9200-2

naniwaduni 6y ago
Another statement of the Church-Turing thesis is to say that the the functions computable by a Turing machine (or lambda-computable, or general recursive) makes a good proxy for the intuitive concept of computability. From this perspective, "thesis" is a misnomer: it just happens to be a useful definition for "computability". That's not to say that there aren't edge cases where intuitive "computability" and Turing computability disagree; for most people, any number of oracle machine constructions will fall under the former but not the latter. We've just chosen to define the term in a way that's "easy" to define somewhat rigorously and has useful properties. It's kind of just like if we were to call the usual definition of the reals "Cauchy's thesis" or somesuch.
- 30f0fn 6y ago
  The Church-Turing proposition carries an implicit challenge: find an algorithm to evaluate a function which is not Turing computable. Because it can be challenged in this way, it’s not just a definition (mere stipulation how to use the word “computable”).
  - Konohamaru 6y ago
    Back in 200 B.C. we had something called the "Euclid-Archimedes Thesis" (okay it wasn't literally called this) which stated that every measurable curve was either a line or a circle. The idea that there was a way to measure the length of any irregular curve was simply impossible. And this thesis went unchallenged for an amazing 1,800 years until the 17th century when several mathematicians constructed measures for various irregular curves. Be very skeptical about "theses" that are handwavy about a frontier subject (pure, abstract geometry was just as much of a frontier subject as abstract machines) suspiciously lacking any proof.
  - naniwaduni 6y ago
    It's pretty easy to come up with "algorithms" in the intuitive sense that are not Turing computable; just violate any of the finiteness constraints. The fact that you might object to considering such procedures algorithms rests on the fact that the "thesis" is providing a definition.
    - simcop2387 6y ago
      Turing machines and being turing computable doesn't require any finite constraints. Both infinite time and infinite storage space are expected for a universal turing machine. We obviously have never built one.
      - supercasio 6y ago
        There are many finite constraints. First, there is no infinite time [1]. The most famous uncomputable problem is the halting problem (given an algorithm A and an input x, can we compute it? that is, will A stop on x?). Although we have an infinite tape, since the time of a computation is finite, the space it uses is also. Second, we describe a Turing machine using finite sets. [1] Actually, as described by Turing, a Turing machine neves stops, but this is only because he is interested in computing real numbers (for example pi). But even using an original Turing machine, we do not "compute" pi. We only "compute" pi with some precision.

naniwaduni 6y ago

Another statement of the Church-Turing thesis is to say that the the functions computable by a Turing machine (or lambda-computable, or general recursive) makes a good proxy for the intuitive concept of computability. From this perspective, "thesis" is a misnomer: it just happens to be a useful definition for "computability". That's not to say that there aren't edge cases where intuitive "computability" and Turing computability disagree; for most people, any number of oracle machine constructions will fall under the former but not the latter. We've just chosen to define the term in a way that's "easy" to define somewhat rigorously and has useful properties. It's kind of just like if we were to call the usual definition of the reals "Cauchy's thesis" or somesuch.

30f0fn 6y ago
The Church-Turing proposition carries an implicit challenge: find an algorithm to evaluate a function which is not Turing computable. Because it can be challenged in this way, it’s not just a definition (mere stipulation how to use the word “computable”).
- Konohamaru 6y ago
  Back in 200 B.C. we had something called the "Euclid-Archimedes Thesis" (okay it wasn't literally called this) which stated that every measurable curve was either a line or a circle. The idea that there was a way to measure the length of any irregular curve was simply impossible. And this thesis went unchallenged for an amazing 1,800 years until the 17th century when several mathematicians constructed measures for various irregular curves. Be very skeptical about "theses" that are handwavy about a frontier subject (pure, abstract geometry was just as much of a frontier subject as abstract machines) suspiciously lacking any proof.
- naniwaduni 6y ago
  It's pretty easy to come up with "algorithms" in the intuitive sense that are not Turing computable; just violate any of the finiteness constraints. The fact that you might object to considering such procedures algorithms rests on the fact that the "thesis" is providing a definition.
  - simcop2387 6y ago
    Turing machines and being turing computable doesn't require any finite constraints. Both infinite time and infinite storage space are expected for a universal turing machine. We obviously have never built one.
    - supercasio 6y ago
      There are many finite constraints. First, there is no infinite time [1]. The most famous uncomputable problem is the halting problem (given an algorithm A and an input x, can we compute it? that is, will A stop on x?). Although we have an infinite tape, since the time of a computation is finite, the space it uses is also. Second, we describe a Turing machine using finite sets. [1] Actually, as described by Turing, a Turing machine neves stops, but this is only because he is interested in computing real numbers (for example pi). But even using an original Turing machine, we do not "compute" pi. We only "compute" pi with some precision.