Interest Haiku #15: Undecidability
Wednesday, December 15th, 2004 12:20 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
flwydundecidability:
If statement is true,
It must be false. But if it's
False it must be true.
For those of you just tuning in, this is part of an ongoing series in which I explain each of my LJ interests.
Gödel's Undecidability Theorem was perhaps the most important mathematical discovery of the 20th Century. It proves that any formal system complex enough to describe arithmetic is either inconsistent or incomplete. A formal system is a set of axioms and rules which can be used to prove statements, such as 1 + 1 = 2. In an incomplete system, at least one statement which is intended to be true cannot be proven. In an inconsistent system, at least one statement can be proven both true and false. This is a Bad Thing, because then you can prove any other statement you want.
An immediate consequence, directly applicable to my profession, is the following corollary: you cannot write a program to determine whether a program will terminate when given its own source code as input. If you could write such a program, call it self_loops(prog), you could write a program like so:
What happens when that program is fed its own source code? It's undecidable. And, as a consequence, you can't write a program which will determine any input/output properties of all programs. You can do a good job, but there will always be some programs that will stump you.
Undecidability is essentially a formal version of the liar's paradox. It's also a rigorous proof that God cannot create a rock so heavy he cannot lift it. Furthermore, God cannot both have complete freedom and complete foreknowledge of his own actions. If God knows what he will do, he is not free to do something else. Furthermore, I ca do something God cannot do. I can truthfully assert the sentence "God cannot truthfully assert this sentence." One nice thing about Paganism is your gods don't have to be all-powerful... or even perfect.
A similar concept that I'm rather fond of is uncertainty. One of the most important discoveries in 20th Century physics is that we cannot simultaneously know exactly where an object is and what its exact velocity is. The more certain we are of its position, the less certain we are of its velocity. The mere knowledge that a billiard ball is on a pool table means that it must be moving at least 10-26 meters per second, or so.
For a book-length treatment of this subject, complete with Lewis Carroll references, I recommend Douglas Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid.
I'm not sure I'm done with this entry, but I think so.
If statement is true,
It must be false. But if it's
False it must be true.
For those of you just tuning in, this is part of an ongoing series in which I explain each of my LJ interests.
Gödel's Undecidability Theorem was perhaps the most important mathematical discovery of the 20th Century. It proves that any formal system complex enough to describe arithmetic is either inconsistent or incomplete. A formal system is a set of axioms and rules which can be used to prove statements, such as 1 + 1 = 2. In an incomplete system, at least one statement which is intended to be true cannot be proven. In an inconsistent system, at least one statement can be proven both true and false. This is a Bad Thing, because then you can prove any other statement you want.
An immediate consequence, directly applicable to my profession, is the following corollary: you cannot write a program to determine whether a program will terminate when given its own source code as input. If you could write such a program, call it self_loops(prog), you could write a program like so:
godel(prog) {
if (self_loops(prog))
exit;
else
while (true); // loop forever
}What happens when that program is fed its own source code? It's undecidable. And, as a consequence, you can't write a program which will determine any input/output properties of all programs. You can do a good job, but there will always be some programs that will stump you.
Undecidability is essentially a formal version of the liar's paradox. It's also a rigorous proof that God cannot create a rock so heavy he cannot lift it. Furthermore, God cannot both have complete freedom and complete foreknowledge of his own actions. If God knows what he will do, he is not free to do something else. Furthermore, I ca do something God cannot do. I can truthfully assert the sentence "God cannot truthfully assert this sentence." One nice thing about Paganism is your gods don't have to be all-powerful... or even perfect.
A similar concept that I'm rather fond of is uncertainty. One of the most important discoveries in 20th Century physics is that we cannot simultaneously know exactly where an object is and what its exact velocity is. The more certain we are of its position, the less certain we are of its velocity. The mere knowledge that a billiard ball is on a pool table means that it must be moving at least 10-26 meters per second, or so.
For a book-length treatment of this subject, complete with Lewis Carroll references, I recommend Douglas Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid.
I'm not sure I'm done with this entry, but I think so.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2004-12-15 08:03 am (UTC)Is it a proof that God can't be omnipotent, or is it just a proof that the word "omnipotent" is mostly meaningless and stupid? I guess it amounts to basically the same thing.
no subject
Date: 2004-12-15 03:16 pm (UTC)You need to end this with
Date: 2004-12-16 04:00 am (UTC)To be perfectly correct and elegant. And don't forget Metamagical themas, either. Lovely work.
(This statement is not at the end of my entry).
no subject
Date: 2004-12-16 07:40 am (UTC)And may I say, your GF's LJ Icon is HAWT! =D
no subject
Date: 2005-04-05 10:22 am (UTC)Theological Pastiche
In each religion
So many good traditions
Why choose only one?