I considered placing this in General Questions, as it would seem to be a question of fact, but since it often comes up in philosophical discussions I decided Great Debates would suffice.
Godel’s Incompleteness Theorem does not imply that humans will always be smarter than computers.
It does mean that no finite system can ever derive all truths. No computer can be made that cannot be crashed. Mathematics is necessarily incomplete: there will always be “true” statements that cannot be proven within a given system.
Maybe this is because I agree with you, but I don’t really see a debate here. What you’ve said is all exactly in line with what Göedel’s incompleteness theorem implies.
IIRC Godel’s theorem essentially states laymanly that any decent formal system (system of writing down things that may be true or false, complicated enough to handle natural numbers) has all statements expressable false, or some true statements unprovable. Anyone want to elaborate?
Yeah, the incompleteness thm should apply to computers and brains alike. Does it matter if our brains are analogue? I don’t think so.
No computer cannot be crashed? I don’t remember that bit… could you explain?
While I agree with most of your post, I do have a bit of a quibble (on preview, the same as Shade’s):
Heh? How does this follow from Godel’s theorem?
Godel’s theorem is a statement about formal systems of mathematics. A computer (or to be specific a Turing machine) is not a formal system of mathematics.
A Turing machine is a discrete system of information which evolves over time in a deterministic fashion. A formal system does not evolve over time in any meaningful sense . The closest it comes is when a mathematician or automatic theorem proving system generates new proofs in the language of the formal system (which I must stress is not a case of the formal system evolving, it’s a case of an outside agent’s knowledge of the system evolving). But even that isn’t necessarily deterministic, at least in the case of a human mathematician.
What’s more, Godel’s proof is an explicit construction. Given a formal system, Godel’s proof constructs a specific undecidable statement. I am aware of no explicit construction which, given a specific Turing machine, returns a program which “crashes” that Turing machine. I will happily be educated with a cite on this issue if you can provide one.
Finally, your statement is false on its surface. The following Turing machine will never “crash” no matter the input: the Turing machine with a single state, the “stop” state.
I wholeheartedly agree with you that Godel’s theorem gets used well outside its domain. However, it seems to me that applying it to computers is also a case of this.
I had previously started a thread about how the classical concept of a soul is fundamentally self-contradictory, and the Theorem was brought up. Several people claimed that G’sIT didn’t imply these things.
So what does the Incompleteness Theorem imply about AI? I’m sure there’s someone out there willing to create a debate on the subject.
Shade: More accurately, any computer can be given a problem such that it will either fail or crash. No computer can handle everything.
I don’t know enough about mathematics to explain it, but IIRC it is related to the “stopping” problem of idealized Turing machines and the concept of computability. See The Emperor’s New Mind by Roger Penrose if you have a copy.
I also have a question: I’ve heard it claimed that one consequence of the Incompletness Theorem is that no system of laws, rules or regulations can be 100% comprehensive, because you could always postulate a situation that the rules couldn’t cover. Is this correct?
It can evaluate mathematical claims, and the functions of all computers are fundamentally mathematical. Anything that can be accurately described by a formal mathematical system is subject to the Incompleteness Theorem.
Hmmm… I don’t know of any general methods for generating “exceptional” programs that specific Turing machines can’t run.
[blink][blink] Does that even count as a Turing machine? Since I know there are proofs that demonstrate that all Turing machines can solve certain problems, and that specific device can never solve anything, I suspect it can’t be… but perhaps I’m mistaken.
I’m not at all certain that it’s the case. But what is what we’re here to debate, after all!
The Theorem applies to any system sufficiently powerful to describe arithmetic. I don’t think any arbitrary set of rules is sufficiently powerful.
Although, if the rules are meant to describe specific events and the proper responses to them, it may well be that no such system can be made perfectly.
I do know that there are proofs that specific types of rule systems are inherently incomplete. Voting is one.
You’re referring to the “Halting problem” which states that there is no way to write a computer program which can be used to determine automatically whether or not other computer programs will halt in finite time or not. However the proof of this fact, to the best of my knowledge, does not use Godel’s theorem.
**
No.
Well, if the system of laws happened to include the axioms of number theory then Godel’s result implies that there are statements which are meaningful in the system of laws which are either true and unprovable or false and provable. However, those statements would be about number theory exclusively. Godel’s theorem says nothing about, for example, civics.
No, anything that can be accurately described by a formal mathematical system which includes the axioms of number theory is subject to the Incompleteness theorem.
And by “formal mathematical system”, Godel’s theorem means something very specific. A formal mathematical system in this context means a collection of symbols (the “alphabet”), a rule for determining whether strings of symbols from the alphabet are well-formed, a set of axioms which are well-formed strings, and a set of rules which show that certain well-formed strings are “implied” by others.
A Turing machine, by contrast, is a collection of states together with a rule which, given a current state and an particular input, uniquely determine the next state of the machine. Note that there’s no notion of “well-formed” states or input. Also, while there is an initial state which is roughly analogous to an axiom, and while the rule to determine succeeding states is roughly analagous to an “implication”, the states are just elements of a finite set and not strings in any alphabet.
Without one I’m afraid your connection between Godel’s theorem and Turing machines is only speculative. Godel’s theorem is constructive; if the result you claim did follow from Godel’s theorem then it should be possible to construct exceptional programs too.
It’s a Turing machine alright, the trivial one. Perhaps you mean “Turing-complete” computers, which are a subset of Turing machines. That is certainly a more interesting question. I can’t immediately dismiss the claim that any Turing-complete computer can be crashed, but I also don’t see how that claim follows from Godel’s theorem, given my points at the beginning of this post.
Anyway, I gotta go, so don’t expect more replies from me until tomorrow. I’m sure ultrafilter, DrMatrix, Chronos, Achenar, and half a dozen others will take up the slack; nothing like a good juicy mathematical GD to draw them out of the woodwork
** You’re quite correct; I meant to include that, but forgot.
I don’t see the difference. The interactions of the internal states with each other, the source of input, and the output medium, are all defined by mathematics. Computation and mathematics are brought together by physics: any computation must be performed in a medium, and the behavior of that medium can represented with mathematical statements. Any computer can be reduced to mathematics.
Not at all. The Theorem says that any formal system capable of representing arithmetic will have statements it can’t evaluate, but it doesn’t give a general method for finding such statements for specific systems. I’m sure that there are methods for finding a system’s weak points, but I don’t think I need to show that there’s a general method for doing so.
You’re almost certainly right. (Is there any reason at all anyone would consider the trivial case of the Turing machine?)
Well, there’s quite a bit to say here, isn’t there? Godel’s theorem is probably the single most abused statement I’ve ever seen. Let’s get started.
I’ll write TM to mean Turing machine, and GIT to mean Godel’s incompleteness theorem.
GIT implies some things, but it’s got nothing to do with AI, or informal systems. It only applies to systems that can describe our notion of the natural numbers along with addition and multiplication. Toss in the axiom that 0 = 1, and it no longer applies.
I gave a rather complete description of the exact statement of a modern version of the theorem in a thread from July 02 started by erislover in this forum. The title involved the words “incomplete” and “inconsistent”.
Computers can be made that theoretically will never crash (e.g., Orbifold’s all-accepting TM), but if physically realized, they may crash due to a hardware fault. GIT says nothing about computers crashing.
A minor nitpick: TMs do not evolve over time. They are unchanging, just like any mathematical object. For a precise definition, I refer the reader to Sipser’s excellent introduction.
GIT says nothing specifically about AI. It only deals with formal models of arithmetic. To see how specific that is, realize that it does not apply to Euclidean geometry (I think). It most definitely does not apply to informal systems.
The proof that the halting problem is undecidable does not rely on GIT. However, it turns out that it not possible in general to prove that program P halts/does not halt on input Q.
While GIT does not apply to TMs, it does apply to theories that can talk about TMs.
“Turing complete” is a phrase used to describe other models of computation (lamdba calculus, Markov algorithms, etc.) that can do anything a TM can. We have yet to find a model of computation more powerful than the TM which can be finitely described with no “black box” parts.
Lastly, from the standpoint of mathematics, it turns out that one computer program run on a slightly modified (but not more powerful) TM can, if run forever, print every theorem from every theory with a finite set of axioms. Furthermore, if I had a machine that had infinite memory, I could write this program.
Just in case it’s not clear, GIT doesn’t say that a computer can’t find a proof for certain true statements in the right kind of theory. It says that there is no proof.
Well, usually because somebody makes a claim about “all computers” or something like that.
I don’t see how one can argue that any turing-complete system can be crashed, though. It does not seem a reasonable conjecture to me, since the set of probems that are specifically associated with Turing machines are those that are finitely describable and finitely decidable. It is certainly possible to create a non-halting problem for a universal Turing machine, but I wouldn’t call that a “crash”.
If you would, though, then it is pretty easy to demonstrate that any Turing-complete system can be given a non-halting problem.
Well, “statements that it can’t evaluate” strike me as a different thing than “problems that will crash it.” But as I said, that depends on how one wishes to define “crash” for a Turing machine. It is certainly true, though, that any Universal Turing Machine can be given undecideable problems.
The difference is between a formal system that axiomatizes arithmetic and a formal system that can be described by mathematics. Godel’s theorem applies to one but not the other.
I mention that only because I am an incurable pedant, though. As it turns out, Universal Turing machines can model a Peano axiomatization of arithmetic so GIT does apply to Turing-complete systems as a class.
Since I am in full bore-the-crowd mode, though, let me add:
I have seen people link the halting-problem with GIT, but I have never seen a demonstration that they are equivalent, and I would be very surprised if they were. Both served to drive spikes through the heart of the Hilbert Programme, but Godel did it by showing that mathematics would never be consitent and complete while Turing/Church showed that no formal system of first-order predicate logic was both consistent and decidable. Godel came first, and both Turing and Church followed his general method, though Turing’s halting-problem treatment is seen more often that Church’s Lambda calculus.
Damn, I’m in full blown nitpick mode tonight. The “litmus test” of axiomatizing arithmetic works only one way. Any system that does so is subject to GIT. However, not meeting that test does not mean a system is “safe” from GIT. the onus should rest with anyone who claims that GIT holds for such a system, of course, which is why folks generally try to show an equivalence with an axiomatization of arithmetic. Piggyback on thw work of others. It’s the hallmark of a good education.
Sorry–I’ve been running budgets and allocations all week at work. It does bad things to a man.
Lumpy
Not in a general sense. It would certainly be possible to construct a code of laws that was subject ot GIT, but I see no reason why any arbitrary system of laws would be subject to GIT.
A trivial counterexample: “All actions are legal.”
ooops, skipped one. Back to TVAA
Are you certain? This strikes me as very counter-intuitive. I would be interested in seeing the demonstration that any arbitrary method of voting is subject to GIT. At first glance the argument seems unsustainable.
And on preview
Well, I hate do pick nits with you, especially since you beat me to teh thread and posted pretty much every thing of substance that I had to say, but a Turing Complete system is specifically one that can model any other TM (i.e. a Universal turing Machine). Since not every TM is a Universal Turing Machine, (orbifold’s trivial one, for example), this distinction should not be lost.
(Actually, some folks broaden the definition of Universal Turing Machine to include systems that model some other Turing Complete computational model rather than strictly modeling other Turing Machines. This gives rise to some very small Turing Complete Systems that simulate tag systems, about which I know precisely squat other than they let one create really neat Universal Turing Machines.)
Dammit, nothign worse than picking a nit and getting it wrong. that should have read:
[ul][li]a Turing Complete system is specifically one that can model a Universal turing Machine. Since not every TM is a Universal Turing Machine, (orbifold’s trivial one, for example), this distinction should not be lost.[/ul][/li]And it also should have included the note: I know you used an indefinite article to indicate teh general case, I just thought it might be important to highlight the “Universal TM” idea for folks who might not be familiar with theoretical computing.
When I say “Turing Complete”, I am not referring to a particular instance of a model of computation, but rather the category to which it belongs. So we’re both right, just talking about different things.
That’s not correct, is it? I was under the impression that whether GIT applies or not is dependant on the expressive power of the system, not the axioms used, the axioms only deciding if the system is incomplete, contradictory, or both. Or did I completely misunderstand that?
I’ve temporarily given up trying to get my head around the arguments of the “I think therefore I am…” thread and came here for some light reading.
I believe this refers to Arrow’s Paradox (AKA Arrow’s Impossibility Theorem) that “demonstrates the impossibility of designing rules for social decision making that obey a number of ‘reasonable’ criteria.” (from www.wikipedia.org/wiki/Arrow’s_paradox)
Ultrafilter: How can we consider AI without considering systems capable of representing the natural numbers? If the AI couldn’t understand arithmetic in any form or manifestation, it would seem rather odd to consider it an intelligence. Pocket calculators would be more sophisticated.
Regarding voting: It’s not directly related to GIT per se, but there is a proof that any voting system used to indicate rational preferences (“rationality” being a technical term that indicates the preferences meet certain qualifications) between options will always have a set of circumstances where the outcome is counter-intuitive and “wrong”. No “perfect” voting system is possible.
