5 ms·

The Church-Turing proposition carries an implicit challenge: find an algorithm to evaluate a function which is not Turing computable. Because it can be challen

by 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.
    - dfischer 6y ago
      In a way, anything discrete is a logical assertion that exists purely in imagination. Base reality is continuous in every way. It’s imaginary human reality to separate things apart from the whole. Physics and philosophy have struggled with this over atom vs non atom view of “base reality” - interesting to see how it shows itself in many different ways. Anything quantized runs into issues with consistency, as the quantity only works in an imaginary model. No model is sufficient as it has a fixed size of requirements to be a model.
      - drdeca 6y ago
        I think the jury is still out on whether space is quantized. Maybe wave function values can’t be quantized, but that’s not “in every way”. And I’m pretty sure the different eigenstates for spin operator in a given direction are distinct and not a continuum?
        amw-zero 6y ago
        The unfortunate truth is that once you pick apart the definitions of deep things like logic and math, you see that we don’t even all agree on them. We like to think that because we can describe something with math it’s inherently true, but the answer is pretty much always up for debate. We found flaws in basic set theory and had to move to the updated Zermelo-Frankel set theory because of it. People try and create new foundations of math all the time for varying reasons. Anyway, I see so many people speak with such conviction about truth and objectivity, that it’s refreshing to see someone show humility about what we actually know about our universe. Lots is still up for debate, is the sad truth.
        drdeca 6y ago
        (I’ve also been wondering for a few years whether it is possible to make a version of quantum mechanics which works with the wavefunctions taking on values from a (very large) finite field instead of the complex numbers. My impression so far is “probably not” because you need exponentials, and the multiplication group of a finite field doesn’t have a nontrivial group homomorphism to/from the additive group. Also, for the simple way of defining differentiation for functions over finite fields, has 0 as the only eigenvalue of differentiation, and I’m thinking that the other definition I made up for it also does. I think I saw some definition of differentiation for finite fields which maybe does have a non-zero eigenvalue, Yeah found it, https://arxiv.org/abs/1501.07502 https://arxiv.org/abs/1501.07502 but, this doesn’t have the “derivative” of a constant be 0, so I’m not sure that it would be suitable either. So, my guess is that probably one can’t make quantum mechanics work with wave functions that have their values all from a finite field. Still going to keep looking a bit more though. )
- supercasio 6y ago
  > The fact that you might object to considering such procedures algorithms rests on the fact that the "thesis" is providing a definition. Unfortunately, many people don't seem to understand this. An interesting paper related to this issue is The Myth of Hypercomputation [1] Basically it is easy compute something that is uncomputable by using uncomputable inputs. [1] https://link.springer.com/chapter/10.1007/978-3-662-05642-4_8 https://link.springer.com/chapter/10.1007/978-3-662-05642-4_...
  - eindiran 6y ago
    Thank you for the pointer to this. Searching for the paper led me to a few things. If anyone would like to read the paper mentioned in OP's post, you can find it here: https://www.researchgate.net/publication/243784599_The_Myth_of_Hypercomputation https://www.researchgate.net/publication/243784599_The_Myth_... This is a response to "The Myth of Hypercomputation" (entitled "The Myth of 'The Myth of Hypercomputation'"): http://kryten.mm.rpi.edu/PRES/TURKUHYPER/NSG_SB_MoMoH_presentation_v3.pdf http://kryten.mm.rpi.edu/PRES/TURKUHYPER/NSG_SB_MoMoH_presen... This is an interesting blog post that explains a bit about both positions, without addressing the rebuttal to Davis' paper: https://paulcockshott.wordpress.com/2018/02/13/no-mysteries-davis-and-the-myth-of-hypercomputation/ https://paulcockshott.wordpress.com/2018/02/13/no-mysteries-...

by 30f0fn 6y ago

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.
  - dfischer 6y ago
    In a way, anything discrete is a logical assertion that exists purely in imagination. Base reality is continuous in every way. It’s imaginary human reality to separate things apart from the whole. Physics and philosophy have struggled with this over atom vs non atom view of “base reality” - interesting to see how it shows itself in many different ways. Anything quantized runs into issues with consistency, as the quantity only works in an imaginary model. No model is sufficient as it has a fixed size of requirements to be a model.
    - drdeca 6y ago
      I think the jury is still out on whether space is quantized. Maybe wave function values can’t be quantized, but that’s not “in every way”. And I’m pretty sure the different eigenstates for spin operator in a given direction are distinct and not a continuum?
      - amw-zero 6y ago
        The unfortunate truth is that once you pick apart the definitions of deep things like logic and math, you see that we don’t even all agree on them. We like to think that because we can describe something with math it’s inherently true, but the answer is pretty much always up for debate. We found flaws in basic set theory and had to move to the updated Zermelo-Frankel set theory because of it. People try and create new foundations of math all the time for varying reasons. Anyway, I see so many people speak with such conviction about truth and objectivity, that it’s refreshing to see someone show humility about what we actually know about our universe. Lots is still up for debate, is the sad truth.
      - drdeca 6y ago
        (I’ve also been wondering for a few years whether it is possible to make a version of quantum mechanics which works with the wavefunctions taking on values from a (very large) finite field instead of the complex numbers. My impression so far is “probably not” because you need exponentials, and the multiplication group of a finite field doesn’t have a nontrivial group homomorphism to/from the additive group. Also, for the simple way of defining differentiation for functions over finite fields, has 0 as the only eigenvalue of differentiation, and I’m thinking that the other definition I made up for it also does. I think I saw some definition of differentiation for finite fields which maybe does have a non-zero eigenvalue, Yeah found it, https://arxiv.org/abs/1501.07502 https://arxiv.org/abs/1501.07502 but, this doesn’t have the “derivative” of a constant be 0, so I’m not sure that it would be suitable either. So, my guess is that probably one can’t make quantum mechanics work with wave functions that have their values all from a finite field. Still going to keep looking a bit more though. )
supercasio 6y ago
> The fact that you might object to considering such procedures algorithms rests on the fact that the "thesis" is providing a definition. Unfortunately, many people don't seem to understand this. An interesting paper related to this issue is The Myth of Hypercomputation [1] Basically it is easy compute something that is uncomputable by using uncomputable inputs. [1] https://link.springer.com/chapter/10.1007/978-3-662-05642-4_8 https://link.springer.com/chapter/10.1007/978-3-662-05642-4_...
- eindiran 6y ago
  Thank you for the pointer to this. Searching for the paper led me to a few things. If anyone would like to read the paper mentioned in OP's post, you can find it here: https://www.researchgate.net/publication/243784599_The_Myth_of_Hypercomputation https://www.researchgate.net/publication/243784599_The_Myth_... This is a response to "The Myth of Hypercomputation" (entitled "The Myth of 'The Myth of Hypercomputation'"): http://kryten.mm.rpi.edu/PRES/TURKUHYPER/NSG_SB_MoMoH_presentation_v3.pdf http://kryten.mm.rpi.edu/PRES/TURKUHYPER/NSG_SB_MoMoH_presen... This is an interesting blog post that explains a bit about both positions, without addressing the rebuttal to Davis' paper: https://paulcockshott.wordpress.com/2018/02/13/no-mysteries-davis-and-the-myth-of-hypercomputation/ https://paulcockshott.wordpress.com/2018/02/13/no-mysteries-...