Hacker News Reader

Comment by yequalsx | Hacker News Reader

I haven't read the entire article you linked to. Can you elaborate on something?

Godel's Incompleteness Theorem (in essence) said that the first order Peano axioms for the integers was not strong enough to prove all statement in the second order Peano axioms. My understanding is that mathematicians wanted a computable system that would be strong enough to prove all true statements encompassed by the second order system.

Godel showed this can't be done. No computable system can be strong enough to prove all true statements in the second order system. Given that humans can prove statements that are true in a system that can't be reducible to a computable set of axioms how can computer intelligence ever equal human intelligence? Human intelligence must be fundamentally not a computable system. What's wrong with this reasoning?

View on HN

Could you elaborate on "... given that humans can prove statements that are true in a system that can't be reducible to a computable set of axioms ..."? Perhaps with an example?

From Wikipedia:

The true but unprovable statement referred to by the theorem is often referred to as “the Gödel sentence” for the theory. It is not unique; there are infinitely many statements in the language of the theory that share the property of being true but unprovable.

How does that prove in any way that the human mind can find all true statements in Mathematics and thus go beyond the limits of computability? Do you have any proof of this? Also, do you have any proof that the human mind is in fact consistent (meaning it can't possibly reach A and ~A at the same time)?

I'm not claiming that humans can discover all true statements in mathematics. I'm saying the Incompleteness Theorem demonstrates that such a task is not computable and in the proof of the theorem a statement that can't be proven in a computable system is proved. So....can a computer ever reach the same level of reasoning? I'm skeptical.

Solving a particular instance of a noncomputable problem is not the same than solving the problem itself. Eg, the busy beaver problem is noncomputable, but it's trivial to make a machine output solutions for simple cases in the same way that it's trivial for a human to do so. In fact, you cannot prove that what we are doing is essentially programming ourselves to solve ad-hoc cases of the general problem, which is computable, as opposed to somehow having in our heads a general way of solving the problem, which we know it's not computable.

Basically, what you need to prove to show that humans are intrinsically more powerful than machines is that we have the ability to generally solve noncomputable problems in a general way, ie, that we are hypercomputers.

Don't the existence of thing like the Gödel sentence show that there are things that are true but which humans can't prove, contradicting the claim that this is an important distinction between humans and computers?

I'll try to give an overview of what's going on. In the late 1800s Peano came up with his set of axioms for the integers. This set is second order which means it isn't computable. Hilbert and others wanted a computable set of axioms so that one could, in theory, remove humans from the discovery of mathematical truth.

So the first order axioms were invented. Godel showed that the first order axioms are not strong enough to prove all true statements about the integers. There are infinitely distinct models of the first order integers. There is only one model of the second order integers.

In the proof of the Incompleteness Theorem Godel proves a statement about an integer which is not provable in the first order system.

Humans can work in the second order system but not computers. So, from my perspective there is something different about human thought patterns. I'm not an expert and would like to know what is wrong with my reasoning.

Ok, I'll confess that I'm not sure what you're talking about when you mention second order systems. However, Godel's incompleteness theorems (plural) were a lot more general than you're suggesting.

First Theorem: "Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory."

Second Theorem: "For any formal effectively generated theory T including basic arithmetical truths and also certain truths about formal provability, T includes a statement of its own consistency if and only if T is inconsistent."

It wasn't that Godel proved that Peano arithmetic was incomplete that shocked mathematicians, it was that he showed that _no formal system_ could ever be complete as long as remained consistent.

Of course maybe this second order system isn't consistent, in which case there's no problem. After all, I'm fairly convinced that human reason isn't always perfectly consistent, so it makes sense that we can avoid Godel's theorems. Of course, I see no reason we couldn't make a slightly inconsistent computer either.

Definitely his Incompleteness Theorem (I there are two of them and also a Completeness Theorem) was more general than what I mentioned but the shock was its application to arithmetic. The second order axioms are not recursively enumerable (think computable). It was the goal of Hilbert to find a computable system capable of proving (in theory) all true statements. There is no such computable system.

One can find complete axiomatic systems of the integers. It's quite easy. Just take all true statements as the axiom system. The problem is that there is no computable method for determining in such a system whether or not a given statement is an axiom.

Again, we humans can work in the second order axiom system but computers can't. So it appears there's a difference between human intelligence and computer intelligence.

I still don't understand what you mean by the "second order axiom system" that is somehow the domain only of humans...

Reply on news.ycombinator.com