posted
Yeah, I've got two completely unrelated questions. First, there's a word - I know there is - for having the quality of having different forms based on the environment that the thing is expressed in, but I can't remember what it is. I think it might be epigenetic but the definitions that are coming up don't fit what I'm thinking. In one way it would be like the undifferentiated embryonic cells taking on their form based on the cells surrounding them and in other it would be like a way of saying that the urge to obtain food would prompt someone to go fishing, or hunting, or go to the supermarket, depending on the environment they find themselves in. Does anyone know what that word is?
Second, I've come across Gödel's incompleteness theorems a couple of times and they're just not clicking for me. Does someone understand them and can they explain them to me?
posted
I understand the results of Godel's incompleteness theory, and can follow the process he used, but can't really follow it step by step.
(Who am I kidding? I can't follow it at all step by step.)
The essence of the Godel theory is that a sufficiently powerful logical system will never be complete. That is, there will always be true statements about the system that cannot be proven from within the system. Essentially, it was a daggar aimed at Russel's "Principia Matematica."
The best explanation I've seen is Hofstadter's "Godel, Escher, Bach." Even though I have serious questions about his ultimate conclusions, his analysis of the theory is quite good.
Check out this link if you haven't come across it already:
Summary of Hofstadter's take on it:
quote:All consistent axiomatic formulations of number theory include undecidable propositions ...
Gödel showed that provability is a weaker notion than truth, no matter what axiom system is involved ...
A decent summary of the proof:
quote:The proof of Gödel's Incompleteness Theorem is so simple, and so sneaky, that it is almost embarassing to relate. His basic procedure is as follows:
1. Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all. 2. Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine. 3. Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true." 4. Now Gödel laughs his high laugh and asks UTM whether G is true or not. 5. If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements. 6. We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true"). 7. "I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."
Think about it - it grows on you ...
If I had to sum it up, it would be that "not all things that are true can be proven." Which shouldn't sound at all strange coming from my mouth. Posts: 26071 | Registered: Oct 2003
| IP: Logged |
posted
The first I don't know, but I might be able to help with Gödel. He is basically saying that in any axiomatic system that contains basic arithmetic, there exist mathematical propositions which are true, but cannot be proven. Let me take Euclid as an example. (Euclid doesn't contain arithmetic, but it's the only part of mathematics that most people learn as an axiomatic system, so it suits my purpose.) Gödel is saying that you can set up some proposition in ordinary plane geometry that is true, but cannot be proved from Euclid's axioms. And even if you adopt this proposition as a new axiom, there exists another true proposition, not provable from your new set of axioms. And so on.
The proof is kind of complex, but rests basically on finding a way to express the old liar paradox mathematically, ie "This sentence is false".
Does that help you any? I should note that we are not talking about sentences of fact, here, such as "Evolution occurs" - this obviously cannot be proved mathematically anyway, only scientifically. We are talking about purely mathematical statements, like 2+2=4 only more complex. (In fact, 2+2=4 is unprovable, and is usually accepted as an axiom.) That is, even within mathematics, there are true statements that cannot be proven. This was and remains a pretty major statement, philosophically.
Posts: 10645 | Registered: Jul 2004
| IP: Logged |
posted
Damn, Dagsie beat me, though he cheated with his copy-and-paste. Incidentally, Dags, "Not all true statements are provable" applies only to mathematics. Statements of fact, such as "God exists" are only empirically verifiable anyway.
Posts: 10645 | Registered: Jul 2004
| IP: Logged |
posted
Oh yeah, that reminds me, I've got to read Gödel, Escher, and Bach. I understand the philosophical point and implications of the theorems, I just don't get the how you get there, although that explanation is pretty clear. I'm going to have to think about it, becasue right now it sounds a lot like the old "The next thing I say is true. The last thing I said was false." paradox and even I can program a computer with enough reflexivity to overcome that. But then we're talking about UTM (Why did they have the T stand for Truth as opposed to Turing, by the way? I know Gödel preceded Turing machines, but did the UTM concept too?) and there are different rules there.
Posts: 10177 | Registered: Apr 2001
| IP: Logged |
posted
I can answer the question about Godel, or give it a try. The Incompleteness Theorem rocked the mathematical world to its foundations. Before that time, mathematicians had thought that all of formal thought, all reason, all logic, all the deep understanding of philosophy could be encoded in formal systems similar to Euclidean Geometry (which you might be familiar with from school) or Propositional Calculus, or other more powerful systems, all of which were characterized by axioms, laws, and theorems, and in which truths were formally provable inside the system.
What Godel did was to show that in any formal system of enough power (and those without enough power were incomplete from being not powerful enough) it was possible to encode statements in the system which had meaning on two levels at once. They were both statements inside the system and they were statements ABOUT the system. He showed that it was always possible to construct such statements which would be true, but which would nevertheless be unprovable inside the system.
So what the statement, in essence, said is "I am not proveable inside system X". If it was false, of course, then it meant something false was provable which would undermine the whole system. But if it's true then it's nevertheless a truth about the system that we outside the system can see is true and yet from inside the system it's absolutely unprovable.
Therefore it showed that all such systems are incomplete. That there are truths about the system which the system does not contain. So formal logical systems were sort of dethroned by that as methods to arrive at all truth. And that's why it was so revolutionary. As revolutionary, in its way, as Copernicus dethroning the Earth from the center of the Universe.
Kurt Godel was a very brilliant man, though he was strange in many ways. He died of starving himself to death for fear of being poisoned. But he was an amazing guy who changed the way we think about the universe as fundamentally as did Einstein or Newton.
Edit: oh wow, you guys beat me to it while I was writing. Posts: 6246 | Registered: Aug 2004
| IP: Logged |
Yes, but you being a theist, I don't trust you any further than I can see you, so I spell things out.
Posts: 10645 | Registered: Jul 2004
| IP: Logged |
posted
Yeah, I understand UTMs. Well, the theory anyway. Their application into number theory is something I haven't completely come to grips with yet, as is evident here.
Sidenote: Did other people read Cryptonomicon?
Posts: 10177 | Registered: Apr 2001
| IP: Logged |
quote:I understand the philosophical point and implications of the theorems, I just don't get the how you get there, although that explanation is pretty clear. I'm going to have to think about it, becasue right now it sounds a lot like the old "The next thing I say is true. The last thing I said was false." paradox and even I can program a computer with enough reflexivity to overcome that.
The way he gets there is by assigning all statements that can be made within the context of the system to numbers. Then he maps G to a number and not G to a number. Then he does some "thing" (this part I've never been able to articulate, but I can grasp it in the abstract non-lingual portion of my brain) to show that G both equals and doesn't equal not G (or, more accurately, that proving G = not G also proves that G <> not G).
But the "thing" that he does is consistent within the postulates of the system, and that's what I can never explain.
Posts: 26071 | Registered: Oct 2003
| IP: Logged |
posted
Of course, its not actually as universal as all that -- its "not all things in sufficiently complex formal systems that are true can be proven". Formal system here means one where the rules/axioms may be encoded by a computer.
The thing is, the universe may just not be a formal system (and isn't, in a real technical sense, as far as we can tell), so Godel's theorem likely doesn't apply. Well, that's his first one.
His second theorem proves that for certain sorts of formal systems with numbers (including any you've run into) its complete consistency cannot be proven within the system.
Of course, it may turn out that systems we thought were complex really aren't, which would mean that Godel doesn't apply.
I don't believe FOL falls under either of his theorems, either.
Godel's theorem is often (mis)applied to AI. People say that because there's something computers can't prove that means they're lesser than humans. Well, I can easily write a sentence that you can't prove yet know is true -- "MrSquicky will never prove this sentence is true". If you prove it true, you haven't, and if you don't, you have.
Posts: 15770 | Registered: Dec 2001
| IP: Logged |
posted
AK -- actually, mathematicians don't much care about Godel. They're pretty certain his theorems are only true in their weakest sense, anyways. That is, there's nothing necessarily contradictory in the formal systems.
Mathematicians have long had to deal with stuff they can't do (in the nobody can do them sense), anyone with high school calculus should be able to churn out at least a few unsolvable integrals, for instance, even though the integrals can be proven to exist.
Godel's Incompleteness theorems are just a minor extension on the realms of impossibility.
edit: beyond those in that area of mathematics, of course, who care about him just like they care about all the other major developments in that area
Posts: 15770 | Registered: Dec 2001
| IP: Logged |
posted
But mathematicians did care about what Russell was doing, and many of them thought it would succeed. Of course, Russell was applying his rigid determinisim to mathematics for more than mathematical reasons. But without Godel's theory, it's impossible to say how long mathematics might have been diverted down that road.
Posts: 26071 | Registered: Oct 2003
| IP: Logged |
posted
Some mathematicians. Mathematics had just reached a high enough level, though, that the areas were starting to diverge, and most were working on their own tangents instead of paying attention to Russell's esoteric obsessions.
Posts: 15770 | Registered: Dec 2001
| IP: Logged |
posted
Squick, when you read GEB, the part that helped me visualize this the most was the concept of a record player that can play any sound in the world. You'll know it when you get to it.
Posts: 26071 | Registered: Oct 2003
| IP: Logged |
posted
Russell, everything I've read said it was huge, an enormous overturn of the ascendancy of logical formal systems, the queen of mathematics, and therefore, many believed, of rational thought.
I've read that it was comparable to what Copernicus did to the position of Earth at the center of the universe, or what Einstein did to the immutable Time and Space of Newton, or what Darwin did to the position of humanity in nature. That it had profoundly disturbing philosophical connotations to belief systems held dear before.
From this perspective it's no big deal, just as we accept today that the Earth revolves around the Sun without a qualm. However to those involved at the time, it was revolutionary.
I agree with you that it has no implications whatsoever for strong AI, though.
Posts: 6246 | Registered: Aug 2004
| IP: Logged |
posted
Dunno who you're hearing that from, but the mathematicians and mathematical historians I know think of it as one of many fascinating proofs. Could be the philosophers took it a lot harder.
Posts: 15770 | Registered: Dec 2001
| IP: Logged |
posted
Probably not what you really want but "undifferentiated embryonic cells taking on their form based on the cells surrounding" is known as regulative development. And otherwise: Environmentally-controlled gene expression or selection is often referred to as ecogenetic. Environmental-triggering of abnormal gene expression is teratogenic.
Posts: 8501 | Registered: Jul 2001
| IP: Logged |
posted
I read Cryptonomicon after reading Snow Crash, and thoroughly enjoyed both. Stephenson doesn't really write endings, but I don't feel I need them so it's okay.
Posts: 10886 | Registered: Feb 2000
| IP: Logged |
posted
The description of Pearl Harbor from Waterhouse's PoV is absolutely priceless... one of my favorite 3-4 pages of writing, ever.
Posts: 3846 | Registered: Apr 2004
| IP: Logged |
posted
fugu, have you read Hofstadter's "Godel, Escher, Bach"? I expect my information about Godel's incompleteness theorem and its effect on the mathematical thought of the time came mainly from there. Seems like Bertrand Russell and Alfred North Whitehead were two of the prominant mathematicians of the day who took it hard.
See the Principia Mathematica for more information about this. They had attempted to codify all of mathematics and logic into a formal system, and eliminate nasty paradoxes and so on, by a strict hierarchy of types. Goedel sort of exploded all hope that Truth could be contained in any such system. It didn't make what they did invalid, but it made it much less interesting, perhaps.
Posts: 6246 | Registered: Aug 2004
| IP: Logged |
posted
AK, I've read almost every Hofstadter book out there. Bertrand Russell was more famously a philosopher than a mathematician, and Whitehead was a mixture of both. Their pursuit of the Principia was motivated at least as much if not more by their philosophical leanings than their mathematical ones, the more "pure" mathematicians of their age weren't of the same sort at all.
I'm also quite familiar with the general aims of the principia, and even before godel many mathematicians were skeptical it could be done. This wasn't something seen as a part of a miraculous unifying of mathematics in progress, this was a try to take an ideal of their philosophy, that codification, unification, and paradox elimination could take place, and make mathematics fit it.
Posts: 15770 | Registered: Dec 2001
| IP: Logged |
Man, we need some sort of reverse lookup dictionary where you can describe in a vauge way the word you wnat and it'll give you your options. Theasaurus's only work for words and they've not been working for me here.
The thing that kills me is that I know this word exists. I've read it or heard it used in conversation before. The concept is an important one in the work I'm doing but it not particularly congruent with the dominant philosophy. Ah well, maybe I'll make up my own word. How about scenamorphic or fantomorphic (Latin and Greek wrods for background, respectively, added to morphic)?
Posts: 10177 | Registered: Apr 2001
| IP: Logged |
posted
Polymorphic works for your first example, but not your second.
I looked up the word I thought you were talking about (knew I'd heard or read it recently) -- turned out it was epigenesis. So if you don't think that definition matches, I cannot help you.
Posts: 9866 | Registered: Apr 2002
| IP: Logged |
posted
I have GEB, Metamagical Themas, and The mind's I
The mind's I is the only one that I easily got into and was engrossed in reading. The others I kind of forced myself to keep chugging through
Posts: 2532 | Registered: Jul 2001
| IP: Logged |
dkw, I don't know, it might be epigenetic. The definiton is pretty close and maybe the word has been adapted into this specific context. I guess I was hoping someone could say "Oh yeah, that's definitely it." or "No, here's the word you want." I do appreciate people looking and I imagine I'll use epigenetic until someone looks at me funny and says "No, that's not the right word."
Posts: 10177 | Registered: Apr 2001
| IP: Logged |
posted
Part of the coolness goes to kq. She's the one who showed it to me when my mind drew a blank around "syntax". Posts: 4519 | Registered: Sep 2003
| IP: Logged |
quote:1 : development of a plant or animal from an egg or spore through a series of processes in which unorganized cell masses differentiate into organs and organ systems; also : the theory that plant and animal development proceeds in this way -- compare PREFORMATION
It would be the word to use if you want to emphasis that things that started the same developed in different ways. It doesn't specify that the differentiation was caused by the surroundings, though.
Posts: 9866 | Registered: Apr 2002
| IP: Logged |
quote:Part of the coolness goes to kq. She's the one who showed it to me when my mind drew a blank around "syntax".
So noted. I'll adjust my chart accordingly.
dkw, Yeah, the word I'm thinking of specifically means that the form that something takes is heavily determined by the environment it is expressed in. Of all the definitions I've read, the epigenetic one comes closest, but still...
I hate being the guy who is using a big word that doesn't mean what he thinks it means. It can destroy your credibility.
Posts: 10177 | Registered: Apr 2001
| IP: Logged |
posted
How cool to find other Hofstadter fans! I've read all of them as well. Russell, don't you even live in the same city as him? So you could like stalk him and stuff <laughs>, or perhaps even more fun, go and hear his lectures.
If I was doing artificial intelligence phD work I would so want him for my advisor. Such a brilliant guy!
Posts: 6246 | Registered: Aug 2004
| IP: Logged |
Printer-friendly view of this topic
![[Smile]](smile.gif)
![[Big Grin]](biggrin.gif)
