Gödel's Incompleteness Theorem

Apr 2007
2,140
0
I was thinking that if in the future, where quantum computers will maybe be developed, the Gödel's Incompleteness Theorem will be changed, since the algorithmic function in quantum computer science will be much more complex and powerful. Please post some thoughts on this.
 
Nov 2006
848
0
I'm a figment of my own imagination :?
Gödel showed that every consistant formal system must be incomplete. Specifically, he constructed a statement (originally in the formal system behind the Principia Mathematica) that could not be simultaneously true and provable within that system, and showed that this type of construction can be generalized to any sufficiently powerful system. Making a formal system more powerful does not break out of this trap.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
johnny said:
I was thinking that if in the future, where quantum computers will maybe be developed, the Gödel's Incompleteness Theorem will be changed, since the algorithmic function in quantum computer science will be much more complex and powerful. Please post some thoughts on this.
The incompleteness theorem remains unchanged. Many lower bounds for classical computers, though, no longer apply -- as long as we're willing to accept randomness. Of course in practical computation randomness does seem a powerful tool -- compare the speed of probable-prime tests with error < 1e-100 to primality proving programs.
 
Oct 2007
1,701
3
Chicago
johnny said:
I was thinking that if in the future, where quantum computers will maybe be developed, the Gödel's Incompleteness Theorem will be changed, since the algorithmic function in quantum computer science will be much more complex and powerful. Please post some thoughts on this.
Any type of computing machine (Turing Machines, binary computers, analog computers, etc, etc) can be shown to compute the same things... just at different speeds. So, even though quantum computers will be exponentially more powerful, they can't compute anything a normal computer would be unable to compute, given enough time.

A decent introduction to computability is Computability and Unsolvability by Martin Davis.
 

CRGreathouse

Forum Staff
Nov 2006
16,046
936
UTC -5
cknapp said:
Any type of computing machine (Turing Machines, binary computers, analog computers, etc, etc) can be shown to compute the same things... just at different speeds. So, even though quantum computers will be exponentially more powerful, they can't compute anything a normal computer would be unable to compute, given enough time.

A decent introduction to computability is Computability and Unsolvability by Martin Davis.
I mostly agree with you, but one quibble: quantum methods don't actually provide an exponential speedup, even though they can in a sense provide an exponential increase in the number of states. Accessing those states individually is not possible. An n-qbit computer is more powerful than a traditional computer of the same speed, but less powerful than a traditional computer 2^n times faster.
 
Oct 2007
1,701
3
Chicago
CRGreathouse said:
I mostly agree with you, but one quibble: quantum methods don't actually provide an exponential speedup, even though they can in a sense provide an exponential increase in the number of states. Accessing those states individually is not possible. An n-qbit computer is more powerful than a traditional computer of the same speed, but less powerful than a traditional computer 2^n times faster.
Right... Thanks for the correction. ;)
 
Jun 2007
46
0
Richmond, VA
In addition to the very good Martin Davis book, a simpler and highly readable book is Newman and Nagel's Godel's Proof, 1954.
 
Dec 2007
687
47
roadnottaken said:
Gödel showed that every consistant formal system must be incomplete. Specifically, he constructed a statement (originally in the formal system behind the Principia Mathematica) that could not be simultaneously true and provable within that system, and showed that this type of construction can be generalized to any sufficiently powerful system. Making a formal system more powerful does not break out of this trap.
don't worry, all you have to do to prove the truth of some statement is to prove that this statement is undecidable, piece of cake :D
 
Dec 2007
687
47
Phrzby Phil said:
Al-mahed - please explain. Thanks.
Gödel's first incompleteness theorem states that:

For any consistent formal, computably enumerable theory that proves basic arithmetical truths, an arithmetical statement that is true, but not provable in the theory, can be constructed. That is, any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete

If an statement is false one can prove it.

If an statement is true one may prove or not. If there is a proof the statement is not undecidable, if you show that the statement is undecidable there is no proof of the truth and if there is no proof of the truth the statement is true.

An statement is undecidable only if it is true. So if one prove that an statement is undecidable the truth of the statement is proved, altough the truth itself cannot be proved using the consistent formal theory axioms itself.