11 ms·

Three criticisms of Penrose's argument: 1. I don't think human reasoning is consistent in the technical sense, which makes the incompleteness theorem inapplica

Three criticisms of Penrose's argument: 1. I don't think human reasoning is consistent in the technical sense, which makes the incompleteness theorem inapplicable regardless of what you think about us and Turing machines. 2. The human brain is full of causal cycles at all scales. Even if you think human reasoning is axiomatisable, it's not at all obvious to me that the set of axioms would be finite or even computable. Again this rules out any application of Gödel's theorem. 3. Penrose's argument revolves around the fact that the sentence encoding "true but not provable" in Gödel's argument is actually provably true in the outer logical system being used to prove Gödel's theorem, just not the inner logical system being studied. But as all logicians know, truth is a slippery concept and is itself internally indefinable (Tarski's theorem), so there's no guarantee that this notion of "truth" used in the outer system is the same as the "real" truth predicate of the inner system (at best it's something like an arbitrary choice, dependent on your encoding). Penrose is referring to "truth" at multiple logical levels and conflating them. In other words: you can't selectively chose to apply Gödel's theorem to the situation but not any of the other results of mathematical logic.

Borealid 2y ago
> it's not at all obvious to me that the set of axioms would be finite or even computable The reasoning is representable with and by a finite number of elementary physical particles and so must itself be finite. Because it is finite it is computable. Said another way, you would need an infinitely large brain (or an infinitely deep one) to create infinite reasoning.
- bubblyworld 2y ago
  I think that doesn't work, because we don't know how to represent and predict the state of a cloud of elementary particles to that level of detail. You could argue that the mathematics proves that this is possible in principle, but I counter that you have no idea whether the theory extrapolates to such situations in real life because it is way out of humanity's compute budget to test. Like the rest of physics, I expect new regimes would come with new phenomena that we don't understand.
- eru 2y ago
  > Because it is finite it is computable. Busy Beaver numbers are finite, but not computable.
  - rstuart4133 2y ago
    The Busy Bever numbers may be finite, but the machine (specifically its tape) that produces them is not. If the Busy Bever is running on a Turing machine with a finite tape length the number becomes computable. Turning it around, the answer to "can a machine of infinite size do things a finite computer can't" is "yes". That answer ends up being the reason many things aren't computable, including the halting problem. The halting problem is a trick in disguise. The trick is: no one said the program you are checking halts had to have finite code, or finite storage. Once you see the trick the halting problem looses a lot of its mystique.
    - bubblyworld 2y ago
      I'm not sure what you mean here - the Turing machine that represents a particular BB number halts by definition, which means that it can only visit a finite segment of the tape. Nevertheless BB numbers are incomputable in general. On your second point - allowing infinitely many steps of computation lets you solve the halting problem for regular Turing machines, but you still get an infinitary version of the halting problem that's incomputable (same proof more or less). So I don't think that's really the issue at stake.
      - rstuart4133 2y ago
        The difficulty of the problem is not determined by the answer. The Busy Bever's case the answer could be the number or the number of states in its code. Yes, they are both finite, but that doesn't matter. The difficulty of a problem (which is the time required to find it) is determined by how many possibilities you have to explore. Since Busy Bever is defined in terms of the number of 1's on a tape when it halts, a "possibility" is how many arrangements of 1's a Turing tape can support. As a Turing tape is infinitely long, the answer is it supports an infinite number of arrangements of 1's. This all follows from the definition of "not computable". We say a problem isn't computable if we can't find the the answer with a finite sized program, using finite space. It's not an unreasonable definition. How else could you define it? That definition does leave out the number of steps needed to find the solution. The OP's assertion above is that if the both the program and the space is finite, then the number of steps must also be finite or it must loop forever. I'll leave looking up why as a exercise for the reader. (The proof is pretty simple. It's only a few lines long.) That means in a finite system there is no "halting problem" because looping is easy enough to detect when it happens, and you will either eventually see the program loop or halt because there are no other possible outcomes. "Non-computable" therefore means "oops we hit an infinity". Twisting that around, if we decide something isn't computable an infinity must have snuck into the problem somehow. All the proofs you see demonstrating something is non-computable on a Turing machine happen because the infinite thing sneaking in is it's tape. Restrict the Turing tape to being finite, and every problem that can be solved on it is computable. If you want to see how this works in a practical sense, consider BusyBever(6). It's possible we will never solve it because to solve it you need to solve the Collatz Conjecture. The conjecture is simple: if you repeatedly replace a positive integer x by x/2 if x is even or 3x+1 if x is odd, you’ll always eventually reach x=1. It's easy to disprove: all you have to do is find a counter example. None has been found of course, but that doesn't mean much because there are infinite numbers to check and infinite means non-computable. But what if we remove the infinity? Lets just insist x < N, where N is an integer. Then the Collatz Conjecture becomes solvable, and if BusyBever(6) doesn't contain another such puzzle it becomes solvable too.
- foobarian 2y ago
  > The reasoning is representable with and by a finite number of elementary physical particles Do we even know this much?
  - traverseda 2y ago
    I'm sorry you had to find out this way but no, souls aren't real.
    - mrybczyn 2y ago
      Show me the experimental results...
      - Xunjin 2y ago
        Well, I could argue the contrary, show that souls are real with experimental results! Your argument, might not be your intention, infer that just because you can't prove X thus Y exist.
        costigan 2y ago
        The commenter's point was to disagree with the previous comment that "souls aren't real". Lack of evidence either way means we don't know. Occam's razor, while a good heuristic, is a heuristic, not a theorem.
      - sorokod 2y ago
        That result is stashed in a small china teapot that is orbiting the sun.
      - GoblinSlayer 2y ago
        Even according to platonism souls are forms and forms are described by science. The only difference is that forms are substance and can exist detached from matter, but this doesn't affect computability. Moreover, mathematics is epitome of eidos.
evrydayhustling 2y ago
Your (3) is beautifully said... and to prove the point, we are perfectly able to make computational systems that can manipulate symbols in the same way that Gödel did to verify the incompleteness theorem. Humans and computers are both able to do work within either logical system, and incapable of doing work that crosses between them. Everything that makes "truth" slippery makes "intelligence" and "consciousness" even more slippery and subjective. This is why AGI has such negative impact on AI discourse -- the cause only advances when we focus on improving at measurable tasks.
- bubblyworld 2y ago
  Indeed, proof-checking tools like Lean can reason about their own logical systems and prove their own incompleteness, but I doubt Penrose would conclude that they are not formal systems as a result. I like to think people can still make progress on questions of intelligence and consciousness though. Michael Levin's work comes to mind, for instance. Science is just at very early stages of understanding =)
ccppurcell 2y ago
Just a word on 2, I think that the axioms have to be finite right? (Given that they exist at all) Nothing in the physical universe can require an infinite description.
- bubblyworld 2y ago
  Well, technically for Gödel's theorem to apply to a formal system it has to satisfy a few properties. One of those is that it has a computable list of axioms. Infinite sets can be computable too - the only requirement is that determining whether an axiom is contained in the set can be performed by an algorithm. For instance the set of even numbers is infinite but computable, just check whether the number is divisible by 2. The algorithm itself is finite, even if the set it determines is not.
abathologist 2y ago
Perhaps I misunderstand, but your criticism seems to me rather to agree with Penrose's argument. Points (1) and (2) argue that human reasoning is not computational, in the sense relevant for Gödel's theorems. That is exactly Penrose's point (and was Gödel's point too). He's arguing that we are not going to get a fundamentally super-computational system thru a stack of computations, no matter how big your stack gets. You seem to be confirming this. I don't understand how you mean (3) to apply as a criticism at all. He is not making a claim about truth at some level, he's just reminding us what computation is and what its limits are. afaiu, there are two ways to counter Penrose's claim: a. Prove that consciousness is actually just computational. b. Prove that merely stacking computations can somehow produce a super-computational system.
- bubblyworld 2y ago
  I understood that part of Penrose's argument to run as follows (which I got from his book the emperor's new mind, I admit I actually skimmed the interview). 1. Assume for contradiction that human reasoning is formally describable, as an algorithm or as a logical structure. 2. As a result, the incompleteness theorem produces a sentence that is true in that formal system but which human reasoning cannot detect (by virtue of being described by this formal system). 3. But the proof of the incompleteness theorem shows that this sentence is true, and it was produced by a human, a contradiction. I don't necessarily disagree with the conclusion (I'm kinda agnostic at this point), I just think that this particular argument doesn't hold water.
  - moi2388 2y ago
    Point 3 doesn’t make sense to me. Just because Godels incompleteness theorem exists, does not mean you cannot prove this theorem itself. It has in fact already been proven in theorem provers, so this completely undermines Penrose’s point
  - soulofmischief 2y ago
    Yeah if anything in this universe is undecidable, it's gotta be the conscious thought and behavior of a sufficiently complex brain. Even if a full system analysis reveals patterns that can be used for short-term predictions, you're still only looking at inputs and outputs, and run into the system identification problem. Two brains could produce the same measurable output while still experiencing wildly different internal phenomenon and qualia. For example, how would I know that my blue is your blue, even if we both answer blue and our visual cortex exhibits similar firing patterns?
pfdietz 2y ago
> 1. I don't think human reasoning is consistent in the technical sense, which makes the incompleteness theorem inapplicable regardless of what you think about us and Turing machines. Human reasoning is certainly limited. I mean, imagine the kinds of formulas one would get applying GT to the brain. They would be so enormous they'd be entirely impenetrable to human reasoning. We couldn't even read them in a single lifetime. As for proving GT itself, this proof has been formalized. There's no reason a computer couldn't prove GT by itself.
GoblinSlayer 2y ago
The incompleteness theorem is plausibly applicable to human reasoning. How do you prove "this sentence is false"?
- bubblyworld 2y ago
  That's not quite the incompleteness theorem, which is about sentences that are unprovable but nevertheless have a truth value. I think the liar's paradox is of a different kind. It's a sentence that looks well-formed but arguably has no truth value. If you were to formalise human reasoning as a logical system, such sentences would not be definable in it. Either way, for Penrose's argument to work you actually need the proof of Gödel's theorem to hold, not just the result.

Borealid 2y ago

> it's not at all obvious to me that the set of axioms would be finite or even computable The reasoning is representable with and by a finite number of elementary physical particles and so must itself be finite. Because it is finite it is computable. Said another way, you would need an infinitely large brain (or an infinitely deep one) to create infinite reasoning.

bubblyworld 2y ago
I think that doesn't work, because we don't know how to represent and predict the state of a cloud of elementary particles to that level of detail. You could argue that the mathematics proves that this is possible in principle, but I counter that you have no idea whether the theory extrapolates to such situations in real life because it is way out of humanity's compute budget to test. Like the rest of physics, I expect new regimes would come with new phenomena that we don't understand.
eru 2y ago
> Because it is finite it is computable. Busy Beaver numbers are finite, but not computable.
- rstuart4133 2y ago
  The Busy Bever numbers may be finite, but the machine (specifically its tape) that produces them is not. If the Busy Bever is running on a Turing machine with a finite tape length the number becomes computable. Turning it around, the answer to "can a machine of infinite size do things a finite computer can't" is "yes". That answer ends up being the reason many things aren't computable, including the halting problem. The halting problem is a trick in disguise. The trick is: no one said the program you are checking halts had to have finite code, or finite storage. Once you see the trick the halting problem looses a lot of its mystique.
  - bubblyworld 2y ago
    I'm not sure what you mean here - the Turing machine that represents a particular BB number halts by definition, which means that it can only visit a finite segment of the tape. Nevertheless BB numbers are incomputable in general. On your second point - allowing infinitely many steps of computation lets you solve the halting problem for regular Turing machines, but you still get an infinitary version of the halting problem that's incomputable (same proof more or less). So I don't think that's really the issue at stake.
    - rstuart4133 2y ago
      The difficulty of the problem is not determined by the answer. The Busy Bever's case the answer could be the number or the number of states in its code. Yes, they are both finite, but that doesn't matter. The difficulty of a problem (which is the time required to find it) is determined by how many possibilities you have to explore. Since Busy Bever is defined in terms of the number of 1's on a tape when it halts, a "possibility" is how many arrangements of 1's a Turing tape can support. As a Turing tape is infinitely long, the answer is it supports an infinite number of arrangements of 1's. This all follows from the definition of "not computable". We say a problem isn't computable if we can't find the the answer with a finite sized program, using finite space. It's not an unreasonable definition. How else could you define it? That definition does leave out the number of steps needed to find the solution. The OP's assertion above is that if the both the program and the space is finite, then the number of steps must also be finite or it must loop forever. I'll leave looking up why as a exercise for the reader. (The proof is pretty simple. It's only a few lines long.) That means in a finite system there is no "halting problem" because looping is easy enough to detect when it happens, and you will either eventually see the program loop or halt because there are no other possible outcomes. "Non-computable" therefore means "oops we hit an infinity". Twisting that around, if we decide something isn't computable an infinity must have snuck into the problem somehow. All the proofs you see demonstrating something is non-computable on a Turing machine happen because the infinite thing sneaking in is it's tape. Restrict the Turing tape to being finite, and every problem that can be solved on it is computable. If you want to see how this works in a practical sense, consider BusyBever(6). It's possible we will never solve it because to solve it you need to solve the Collatz Conjecture. The conjecture is simple: if you repeatedly replace a positive integer x by x/2 if x is even or 3x+1 if x is odd, you’ll always eventually reach x=1. It's easy to disprove: all you have to do is find a counter example. None has been found of course, but that doesn't mean much because there are infinite numbers to check and infinite means non-computable. But what if we remove the infinity? Lets just insist x < N, where N is an integer. Then the Collatz Conjecture becomes solvable, and if BusyBever(6) doesn't contain another such puzzle it becomes solvable too.
foobarian 2y ago
> The reasoning is representable with and by a finite number of elementary physical particles Do we even know this much?
- traverseda 2y ago
  I'm sorry you had to find out this way but no, souls aren't real.
  - mrybczyn 2y ago
    Show me the experimental results...
    - Xunjin 2y ago
      Well, I could argue the contrary, show that souls are real with experimental results! Your argument, might not be your intention, infer that just because you can't prove X thus Y exist.
      - costigan 2y ago
        The commenter's point was to disagree with the previous comment that "souls aren't real". Lack of evidence either way means we don't know. Occam's razor, while a good heuristic, is a heuristic, not a theorem.
    - sorokod 2y ago
      That result is stashed in a small china teapot that is orbiting the sun.
    - GoblinSlayer 2y ago
      Even according to platonism souls are forms and forms are described by science. The only difference is that forms are substance and can exist detached from matter, but this doesn't affect computability. Moreover, mathematics is epitome of eidos.

evrydayhustling 2y ago

Your (3) is beautifully said... and to prove the point, we are perfectly able to make computational systems that can manipulate symbols in the same way that Gödel did to verify the incompleteness theorem. Humans and computers are both able to do work within either logical system, and incapable of doing work that crosses between them. Everything that makes "truth" slippery makes "intelligence" and "consciousness" even more slippery and subjective. This is why AGI has such negative impact on AI discourse -- the cause only advances when we focus on improving at measurable tasks.

bubblyworld 2y ago
Indeed, proof-checking tools like Lean can reason about their own logical systems and prove their own incompleteness, but I doubt Penrose would conclude that they are not formal systems as a result. I like to think people can still make progress on questions of intelligence and consciousness though. Michael Levin's work comes to mind, for instance. Science is just at very early stages of understanding =)

ccppurcell 2y ago

Just a word on 2, I think that the axioms have to be finite right? (Given that they exist at all) Nothing in the physical universe can require an infinite description.

bubblyworld 2y ago
Well, technically for Gödel's theorem to apply to a formal system it has to satisfy a few properties. One of those is that it has a computable list of axioms. Infinite sets can be computable too - the only requirement is that determining whether an axiom is contained in the set can be performed by an algorithm. For instance the set of even numbers is infinite but computable, just check whether the number is divisible by 2. The algorithm itself is finite, even if the set it determines is not.

abathologist 2y ago

Perhaps I misunderstand, but your criticism seems to me rather to agree with Penrose's argument. Points (1) and (2) argue that human reasoning is not computational, in the sense relevant for Gödel's theorems. That is exactly Penrose's point (and was Gödel's point too). He's arguing that we are not going to get a fundamentally super-computational system thru a stack of computations, no matter how big your stack gets. You seem to be confirming this. I don't understand how you mean (3) to apply as a criticism at all. He is not making a claim about truth at some level, he's just reminding us what computation is and what its limits are. afaiu, there are two ways to counter Penrose's claim: a. Prove that consciousness is actually just computational. b. Prove that merely stacking computations can somehow produce a super-computational system.

bubblyworld 2y ago
I understood that part of Penrose's argument to run as follows (which I got from his book the emperor's new mind, I admit I actually skimmed the interview). 1. Assume for contradiction that human reasoning is formally describable, as an algorithm or as a logical structure. 2. As a result, the incompleteness theorem produces a sentence that is true in that formal system but which human reasoning cannot detect (by virtue of being described by this formal system). 3. But the proof of the incompleteness theorem shows that this sentence is true, and it was produced by a human, a contradiction. I don't necessarily disagree with the conclusion (I'm kinda agnostic at this point), I just think that this particular argument doesn't hold water.
- moi2388 2y ago
  Point 3 doesn’t make sense to me. Just because Godels incompleteness theorem exists, does not mean you cannot prove this theorem itself. It has in fact already been proven in theorem provers, so this completely undermines Penrose’s point
- soulofmischief 2y ago
  Yeah if anything in this universe is undecidable, it's gotta be the conscious thought and behavior of a sufficiently complex brain. Even if a full system analysis reveals patterns that can be used for short-term predictions, you're still only looking at inputs and outputs, and run into the system identification problem. Two brains could produce the same measurable output while still experiencing wildly different internal phenomenon and qualia. For example, how would I know that my blue is your blue, even if we both answer blue and our visual cortex exhibits similar firing patterns?

pfdietz 2y ago

> 1. I don't think human reasoning is consistent in the technical sense, which makes the incompleteness theorem inapplicable regardless of what you think about us and Turing machines. Human reasoning is certainly limited. I mean, imagine the kinds of formulas one would get applying GT to the brain. They would be so enormous they'd be entirely impenetrable to human reasoning. We couldn't even read them in a single lifetime. As for proving GT itself, this proof has been formalized. There's no reason a computer couldn't prove GT by itself.

GoblinSlayer 2y ago

The incompleteness theorem is plausibly applicable to human reasoning. How do you prove "this sentence is false"?

bubblyworld 2y ago
That's not quite the incompleteness theorem, which is about sentences that are unprovable but nevertheless have a truth value. I think the liar's paradox is of a different kind. It's a sentence that looks well-formed but arguably has no truth value. If you were to formalise human reasoning as a logical system, such sentences would not be definable in it. Either way, for Penrose's argument to work you actually need the proof of Gödel's theorem to hold, not just the result.