8 ms·

I suspect that Godels incompleteness theorems may imply that no single algorithm can solve all proofs. This is actually the basis for Penrose's argument that th

by duaneb 14y ago

I suspect that Godels incompleteness theorems may imply that no single algorithm can solve all proofs. This is actually the basis for Penrose's argument that the mind is non-deterministic, though his argument is deeply flawed.

leephillips 14y ago
Penrose's argument, if I remember correctly, is not that the mind is necessarily non-deterministic, but that it is not equivalent to an algorithm - that you can never program a computer to create a mind. It might also be non-deterministic, but that is not exactly the same thing. His evidence for this is indeed that we can "know" the truth of theorems whose proof can not be reduced to an algorithm.
- duaneb 14y ago
  Wouldn't finite, deterministic systems necessarily be able to be modeled by an algorithm? Either the human mind is infinite in some way, non-deterministic, or it must be able to be modeled by an algorithm. NB I am a programmer and very weak in theory.
  - leephillips 14y ago
    There is no algorithm that can determine the truth of any proposition in arithmetic (for example). It is impossible, in principle, to construct such an algorithm. But given any proposition in arithmetic, the mind can decide its truth value. It is in this sense that Penrose claims the mind can not be modeled by a computer program. It may seem odd now, but at the time there was still a school of artificial intelligence that assumed that a big computer running a really sophisticated program could be equivalent to a human mind. Penrose was trying to show that this idea is a non-starter.
    - hackinthebochs 14y ago
      >There is no algorithm that can determine the truth of any proposition in arithmetic (for example). Currently, yes. But I don't see that this is necessarily true. Why do you think it is?
      - krichman 14y ago
        Simply because there are some propositions that are unprovable in a consistent system with finite axioms. Having an algorithm that solves any proposition would be equivalent to having an algorithm that solves the halting problem.
        hackinthebochs 14y ago
        >There is no algorithm that can determine the truth of any proposition in arithmetic (for example). It is impossible, in principle, to construct such an algorithm. But given any proposition in arithmetic, the mind can decide its truth value. These two statements seem to contradict, unless you grant that the mind either fudges the proof or constructs new axioms such that the proof can be valid. Why do you assume a program can never do this?
        leephillips 14y ago
        Because the program that does it would itself be an algorithm with its own finite set of axioms. There would be undecidable propositions unreachable by the program.
        DanWaterworth 14y ago
        Solving the halting problem wouldn't be sufficient to tell you whether a proposition was true, but it could tell you whether a proposition is independent and if it wasn't whether it was true or false.
    - wbl 14y ago
      Okay, so is the twin prime constant transcendental?
      - mjcohenw 14y ago
        Yes.
    - voyou 14y ago
      "Given any proposition in arithmetic, the mind can decide its truth value." Really? I don't see what reason we have to believe that this is true.
      - leephillips 14y ago
        I guess I didn't really mean that. What I should have said was that in any system of axioms (or within any algorithmic structure) there will exist undecidable propositions (unreachable by the algorithm). The mind can determine the truth value of some of these, so the mind can not be encompassed or modeled by an algorithm.
        duaneb 14y ago
        > The mind can determine the truth value of some of these, so the mind can not be encompassed or modeled by an algorithm. Do you have an example of this? I have an extremely difficult time comprehending it. Also, I was under the impression that there weren't necessarily propositions that are not algorithmically possible to reach, but rather, there are always propositions a given algorithm cannot solve.
        leephillips 14y ago
        > not algorithmically possible to reach I just meant undecidable propositions. > Do you have an example Maybe check out the conclusion on p.76 of this book[1] by Penrose (and the argument supporting it that begins on p.72.): "Human mathematicians are not using a knowably sound algorithm in order to ascertain mathematical truth". His example is our knowledge that a certain computation will not halt, and the impossibility of constructing an algorithm that can prove that fact. More flippantly, you know that you can examine the soundness of your own reasoning, but no algorithm can reach conclusions about its own correctness. [1]http://www.amazon.com/dp/0198539789 http://www.amazon.com/dp/0198539789
    - cbr 14y ago
      at the time there was still a school of artificial intelligence that assumed that a big computer running a really sophisticated program could be equivalent to a human mind We're talking theory, so imagine we have extremely powerful hardware, gobs of memory, understand the brain really well, and have some sort of extremely high-resolution scanning device. We could build an "emulator" that would simulate the brain's "hardware" and then load a scan of someone's brain onto it as "software". The system as a whole is just a big computer running a sophisticated program but it's equivalent to a human mind. This mind running on a computer would have the same strengths and weaknesses as the mind had when running on a biological brain when it comes to determining the truth values of propositions in arithmetic (and everywhere else).
      - leephillips 14y ago
        To say that a computer program can not, in principle, do what the mind does is not to say that the mind can not exist on a substrate other than the familiar biological one. In your thought experiment the "software" would not be a computer program as we understand it; it would not be a set of algorithms. Also, it is problematic to separate "hardware" and "software", and to define what a "scan" of the brain might be.
Evbn 14y ago
Gödel's theorems are about uncountable infinities of statements, and statements whose meaning proof is outside the bounds of a theory. Nothing contradicts the possibility of an algorithm as good as as any human doing formal math.

by duaneb 14y ago

leephillips 14y ago

Penrose's argument, if I remember correctly, is not that the mind is necessarily non-deterministic, but that it is not equivalent to an algorithm - that you can never program a computer to create a mind. It might also be non-deterministic, but that is not exactly the same thing. His evidence for this is indeed that we can "know" the truth of theorems whose proof can not be reduced to an algorithm.

duaneb 14y ago
Wouldn't finite, deterministic systems necessarily be able to be modeled by an algorithm? Either the human mind is infinite in some way, non-deterministic, or it must be able to be modeled by an algorithm. NB I am a programmer and very weak in theory.
- leephillips 14y ago
  There is no algorithm that can determine the truth of any proposition in arithmetic (for example). It is impossible, in principle, to construct such an algorithm. But given any proposition in arithmetic, the mind can decide its truth value. It is in this sense that Penrose claims the mind can not be modeled by a computer program. It may seem odd now, but at the time there was still a school of artificial intelligence that assumed that a big computer running a really sophisticated program could be equivalent to a human mind. Penrose was trying to show that this idea is a non-starter.
  - hackinthebochs 14y ago
    >There is no algorithm that can determine the truth of any proposition in arithmetic (for example). Currently, yes. But I don't see that this is necessarily true. Why do you think it is?
    - krichman 14y ago
      Simply because there are some propositions that are unprovable in a consistent system with finite axioms. Having an algorithm that solves any proposition would be equivalent to having an algorithm that solves the halting problem.
      - hackinthebochs 14y ago
        >There is no algorithm that can determine the truth of any proposition in arithmetic (for example). It is impossible, in principle, to construct such an algorithm. But given any proposition in arithmetic, the mind can decide its truth value. These two statements seem to contradict, unless you grant that the mind either fudges the proof or constructs new axioms such that the proof can be valid. Why do you assume a program can never do this?
        leephillips 14y ago
        Because the program that does it would itself be an algorithm with its own finite set of axioms. There would be undecidable propositions unreachable by the program.
      - DanWaterworth 14y ago
        Solving the halting problem wouldn't be sufficient to tell you whether a proposition was true, but it could tell you whether a proposition is independent and if it wasn't whether it was true or false.
  - wbl 14y ago
    Okay, so is the twin prime constant transcendental?
    - mjcohenw 14y ago
      Yes.
  - voyou 14y ago
    "Given any proposition in arithmetic, the mind can decide its truth value." Really? I don't see what reason we have to believe that this is true.
    - leephillips 14y ago
      I guess I didn't really mean that. What I should have said was that in any system of axioms (or within any algorithmic structure) there will exist undecidable propositions (unreachable by the algorithm). The mind can determine the truth value of some of these, so the mind can not be encompassed or modeled by an algorithm.
      - duaneb 14y ago
        > The mind can determine the truth value of some of these, so the mind can not be encompassed or modeled by an algorithm. Do you have an example of this? I have an extremely difficult time comprehending it. Also, I was under the impression that there weren't necessarily propositions that are not algorithmically possible to reach, but rather, there are always propositions a given algorithm cannot solve.
        leephillips 14y ago
        > not algorithmically possible to reach I just meant undecidable propositions. > Do you have an example Maybe check out the conclusion on p.76 of this book[1] by Penrose (and the argument supporting it that begins on p.72.): "Human mathematicians are not using a knowably sound algorithm in order to ascertain mathematical truth". His example is our knowledge that a certain computation will not halt, and the impossibility of constructing an algorithm that can prove that fact. More flippantly, you know that you can examine the soundness of your own reasoning, but no algorithm can reach conclusions about its own correctness. [1]http://www.amazon.com/dp/0198539789 http://www.amazon.com/dp/0198539789
  - cbr 14y ago
    at the time there was still a school of artificial intelligence that assumed that a big computer running a really sophisticated program could be equivalent to a human mind We're talking theory, so imagine we have extremely powerful hardware, gobs of memory, understand the brain really well, and have some sort of extremely high-resolution scanning device. We could build an "emulator" that would simulate the brain's "hardware" and then load a scan of someone's brain onto it as "software". The system as a whole is just a big computer running a sophisticated program but it's equivalent to a human mind. This mind running on a computer would have the same strengths and weaknesses as the mind had when running on a biological brain when it comes to determining the truth values of propositions in arithmetic (and everywhere else).
    - leephillips 14y ago
      To say that a computer program can not, in principle, do what the mind does is not to say that the mind can not exist on a substrate other than the familiar biological one. In your thought experiment the "software" would not be a computer program as we understand it; it would not be a set of algorithms. Also, it is problematic to separate "hardware" and "software", and to define what a "scan" of the brain might be.

Evbn 14y ago

Gödel's theorems are about uncountable infinities of statements, and statements whose meaning proof is outside the bounds of a theory. Nothing contradicts the possibility of an algorithm as good as as any human doing formal math.