Does anyone have any expertise or insight to Godel’s Incompleteness Theorem?
This is what it is:
http://mathworld.wolfram.com/GoedelsIncompletenessTheorem.html
Google it on Mises.org. Hoppe has some brief commentary on it in his Economic Science and the Austrian Method. As an aside, it’s interesting with regard to its applicability in the case of ontological dualism.
-Jon
I don’t know the proof, but the theory simply says that any axiomatic number system is incapable of proving that it can either prove or disprove any proposed expression in this number system.
In other words, no system can prove its own completeness while remaining consistent.
G. theorem shows that science is always inconclusive and there will be always certain amount of subjective belief in scientific truth.
To prove that a theorem is “true” you verify that theorem is derivable from axioms or from other true theorems derived from axioms, if so you assert that theorem is true. To prove that theorem is “false” you show that asserting it to be true you would contradict axioms or any other true theorem derived from axioms. Notice that also “false” theorems are derivable from axioms, you arrive at false theorems from denial of axioms or true theorems. Thus suppose theorem A, if there exist at least one true theorem which A contradicts the A is false otherwise (if none of true theorems or axioms are contradicted) A is true. It is obvious that theorem cannot be both true and false.
Suppose you want to describe world in its entirety, you want to be able always to tell what happens next. It was believed that world observes the laws of LOGIC. Logic is no more no less then finding the true or false theorems in the sense described in second paragraph above. First you state your axioms and then you develop your theorems, development of theorems is very primitive thing which can be done by little kid or monkey or computer it is just applying certain transformation (or rule of inference) on base axioms, first you have just axioms, then you apply transformation first time, you get your first set of theorems, then you apply same transformation on axioms and your first developed set of theorems, you get then another set of theorems, you can continue that way ad infinitum ….., this way you will be able describe all the happening in the world. Notice that suddenly the notion of “infinity”, of “every-thingness” has pop up here, and this were the problem starts.
So we naively think that every theorem is derivable from axioms and it cannot be both true and false. Goedel proved that it is not so.
There is a branch of LOGIC called formal logic. In formal logic you use instead of words logical symbols, e.g. instead “word” implication you use symbol “->” instead the world “relation” you use symbol “R”, instead of word assertion you use symbol “|-“, a theorem expressed formally is just ugly juxtaposition of formal symbols having no meaning for layman not knowing meaning of particular symbols.
To be able to prove something about formal logic (and hence about logic itself), Goedel would define precise mapping of logical symbols to numbers, e.g. instead of “->” he would use “1”, instead of “R” he would use “2”, instead of “|-“ he would use “3”, having that mapping defined he was able to prove certain things about any logical formal system just by “playing” with numbers which stand for the symbols. He proved that there does not exist logical formal system dealing with numbers which can be both complete and consistent. In every such a system there will be theorems derivable from its axioms which are both true and false, so you are left with 2 choices either reject such theorems in which case your system will be incomplete (it will not contain some theorems derivable from axioms), or you can accept such theorems in which case your system will be inconsistent (it will contain theorems which are both true and false).
Numbers are in their nature infinite. Instead using the words of natural language or symbols of symbolic language you can use numbers, think that for every word or symbol you will use certain precise number. Goedel proved that no matter how hard you will try to avoid contradict yourself there will always be possibility of contradictory statements.
Hence it follows ,that no scientific or economic theory cannot be completely showed to be true, it can only be BELIEVED to be true.
Yes, I know a little about Godel’s incompleteness theorems (there are two).
The easiest way for a lay-person (like myself, my interest in the subject is purely amateur) to understand his theorem is to start with Russell’s paradox. Russell’s paradox is the following:
Consider the set V = { x : x is not an element of x } (Read: “V is the set of all sets which are not members of themselves”).
Is V an element of itself? If we say yes, it is, then it is not an element of itself since that is the definition of V. If we say no, it is not, then it must be an element of itself because it is the set of all such sets. Either way, we arrive at a contradiction. Therefore, there is no set V. This is a set theoretic form of the liar’s paradox, “This statement is not true.”
Godel was contemplating issues of provability, particularly the attributes of consistency and completeness. A formal system is consistent if no contradiction can be proved within it. It is complete if every true theorem in the formal system is provable. It is obvious why consistency is a desirable property of a formal system. Completeness is a desirable property because a logically complete formal system would be mathematically universal - every true math theorem could be proved without a need to invoke new axioms, such as the axiom of choice.
Stripping away the formal arguments, Godel’s theorems rest on what could be called “Godel’s paradox” (though he nowhere lays out such a paradox in plain language), namely, “This statement is not provable” instead of the liar’s paradox, “This statement is not true.” Godel first established a method to be able to say “this statement” in formal logic (to create self-reference) and then found a method to assert non-provability. Godel reasoned that such a statement is in fact true. “This statement is not provable” is true if the system in which it is asserted is consistent. However, since it is true, it is therefore not provable. And since it is not provable, there is at least one true statement in every consistent formal system which is not provable. Therefore, every consistent formal system is incomplete (cannot prove every true statement).
Godel’s first incompleteness theorem states that a formal system (of “sufficient” power) is consistent if and only if it is incomplete. You can’t have both. From Wikipedia, “for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true,[1] but not provable in the theory.” The second incompleteness theorem states that a formal system (again, of “sufficient” power) can prove its own consistency if and only if it is inconsistent.
Contemporary mathematician Gregory Chaitin has significantly extended Godel’s results to show that almost all statements in any formal system (of sufficient power) are not provable! He says it this way, “Most mathematical theorems are true for no reason.” In fact, everything I know about Godel I’ve learned through Chaitin’s writings. You can read the argument I’ve presented here in Chaitin’s words here and you can watch a video on his groundbreaking mathematical constant (the “Halting Probability” or Omega) here (you can skip the first 4 minutes of gratuitous self-aggrandizement by the introducer).
Clayton -
Russell’s ‘paradox’ is nonsense.
That’s not a paradox - just cheap self-reference.
Take it up with Russell, Godel, Turing and Chaitin. 
Clayton -
I don’t know any real paradox. All paradoxes are not paradoxes anymore once you take a deeper look into them, but they’re used to prove a point, no matter how stupid they look.
It’s not worth it =] As a side note, a statement like “pigs fly” can be true or false. But a statement like “this statement is true” can’t be true or false. A bunch of words can’t say anything about themselves. The statement is effectively meaningless.
Well, I’ve read and understand Godel’s proof. What specific flaw do you find in his proof that has escaped the mathematical establishment for 77 years?
Clayton -
Maybe the mathematical establishment has the same love for truth as the economic establishment does ?
The thing is, you can’t analyze logic using logic. It’s just self-recursive nonsense. Just like asking, " What’s the meaning of the word meaning ? "
Feel free to consider me part of the ignorant and unwashed masses, of course =]
I think some clarification is in order.
-
There is nothing wrong with Gödel’s Incompleteness Theorem.
-
There is nothing wrong with Mises’ Action Theorem.
-
There is nothing wrong with Praxeology (The Action Theorem applied)
There is a reason the Action Theorem is not analytical a priori, but synthetic a priori.
Mises, Rothbard, Hoppe would all agree that the validity of the Action Theorem does not rest on pure formal logic. Once validated, however, it becomes possible to deduce praxeological laws logically.
Perhaps we should add Alonzo Church just for good measure? Entscheidungsproblem and all that.
Godel’s Incompleteness Theorems are about the limits of formal systems, not an attempt to bootstrap logic.
Clayton -
Thank you for the YouTube reference Clayton. Chaitin, in part 7, mentions something very exciting to me. The lower bound complexity of his flip-a-coin Turing machine is maximally unknowable. Please correct me here because I’m not a computer scientist, but what this means is that you cannot compress the bit stream output from this program into less bits, e.g. knowing the first 100 bits cannot tell you anything about the 101st bit. Thus it is, by his own definition of randomness, random; correct?
So, let us for the sake of argument disregard John Searl’s idea of the mind not being able to be modeled as a Turing machine, and assert the opposit: The human mind/brain is a Turing machine. Next, let us imagine someone being truly able to model this machine. Lastly we monitor the bit stream output. The question then becomes: Would the lower bound complexity of this modeled mind be maximally unknowable?" If so, would it be random as Chaitin would define it? And, if random, would we not have found a foundation of free undetermined thought, free undetermined action. That is, anyone trying to predict human action with claimed full certainty would be unscientific?
I know I have moved into counterfactuals here, but if you could give an affirmation of my thoughts above, Clayton, I would appreciate it very much. In a sense my thoughts could be formulated as such: “Assume we created Artificial Intelligence, would there not be a possibility to use AI to disprove someone trying to negate the idea of free thought and free action?”
Nothing cheap about self-reference, at all. The central lesson of Turing’s and Church’s research is that a sufficiently powerful formal system is capable of self-simulation* (Turing’s universal machine or Church’s fixed-point operator can self-simulate) and this is what enables us to say “this statement” in formal mathematics.
As Chaitin discusses in the YouTube lecture I linked, Turing’s argument is the most straightforward (compared to Godel’s and Church’s). In essence, Turing proposes what could be a physically realizable device (in every respect except having infinite tape) and asks what is essentially a question of physical science: Is there a method to decide whether such a device halts or not by inspecting its tape, short of running the machine for an indeterminate amount of time and waiting to see whether it halts or not? The answer - which is ultimately equivalent to Godel’s Theorem - is no. Turing shows that there are unsolvable problems (Godel had showed there were unprovable truths). If you accept the Church-Turing thesis, then these unsolvable problems are completely unsolvable in a classically physical world (it turns out they are unsolvable in a quantum physical world, too). By reasoning about an imaginary physical device, Turing avoids the problem of self-reference completely. The culprit (as was suspected from the time of Cantor) is not self-reference. The culprit is randomness, but that would be an entirely new thread.
Clayton -
*Please do not confuse self-simulation with semiotics and other blatantly circular nonsense. There is a world of difference between self-simulation and self-interpretation.
It is amusing that people sometimes use Goedel’s proof as a proof against apriorism in general, though. Perhaps because they’re positivists (even if not consciously) and have a messed up notion of knowledge. It does have some interesting applications in the philosophy of the mind, in favour of dualism.
-Jon
Hmmm, I’m not sure he says anything about the output of individual Turing machines on the basis of their input. A highly random Turing machine could have an incredibly dull and predictable output, e.g. just printing ‘1’ indefinitely.
I think of the mind as a Turing machine, though not in the usual, corny AI sense.
Well, be careful here. The machine is the model. We cannot model it in terms very much simpler than itself if it is very complex, and the human brain is the most complex object we know of in the physical universe. This is why Calculus or DiffEq isn’t much help in predicting human behavior.
No. But Chaitin says something far more interesting later (I think end of pt. 7, beginning of pt. 8) that is what I think you’re driving towards (and which I personally find very exciting): you cannot prove that an N-bit program is elegant (incompressible, random) with less than N-bits of “axioms” or “assumptions.” Another way to say this is that an N-bit compression program can only compress, in computable time, strings whose Kolmogorov-Chaitin complexity (KC complexity) is less than N-bits.
Now, induction and compression are integrally linked - to “comprehend” data in the Kolmogorov-Chaitin sense is to compress it to its shortest form, that is, to discover the underlying law or theory that explains the data (by compressing out all the redundancies and leaving only the structure). If we imagine the human brain (which is obviously an induction machine) as a compression program with N bits of KC-complexity, then the human brain cannot compress strings (data) whose KC complexity is N-bits or greater. Since the human brain is itself N bits of KC complexity, this means that the human brain cannot self-predict (non-determinism, free choice) and that speaking of an ultimate “theory” of the human brain is nonsense even in a deterministic universe. Any detailed model of the brain could not be much smaller (in bits of complexity) than the brain itself. Determinism, in itself, is no help to prediction when you are at the limits of computability. In other words, the future behavior of deterministic systems can be strongly unknowable to non-omniscient observers.
This does not exclude the possibility of attaining speedups through simulating the operation of the human brain (e.g. in silico), or of partial “compression” (i.e. explanation) of the operation of the human mind. But the age-old fantasy of commoditizing thought is just that, in my opinion: fantasy. The human brain has none of the features of highly compressible objects, and there’s no reason to believe there’s very much hidden redundancy within it (evolution is rarely wasteful), so I don’t see humans improving upon the brain in any other than simple speed-up or fixing obvious evolutionary mistakes.
Another way of saying it is this: evolution gave us N-bit brains, so we live in an N-bit world whether we like it or not.
(NOTE: The above paras are 100% my own metaphysical speculations spun off from Chaitin’s work… I have found no such metaphysical speculations affirmed by any other more reputable sources… read at your own risk.)
Again, you have to be careful, because strings of complexity less than N-bits may be predictable or ‘patternful’ to the N-bit complexity human brain. It’s not because the brain itself is maximally incompressible that we cannot model its future behavior. Rather, it is because it is of no more complexity than itself.
I don’t think we have to invent AI to know that. Unless there’s some god-like humans out there with significantly more complex brains than the rest of us in the unwashed masses, human behavior is ultimately unpredictable (therefore gives the illusion of “free choice” even in a deterministic universe) by humans.
BTW, there could be some synergy between computability theory and the Misesian calculation problem. 
Clayton -
Thank you Clayton. A very helpful reply. I’m on unfamiliar ground but it made sense. Just to be clear, I agree we do not have to invent AI to know about free choice. I was just thinking along the lines of: “Even though you are certain about a theory, and thus about the outcome of an experiment designed to test it, it could still be exciting to observe the outcome” (if that even makes sense, lol).
oops
Clayton -
Are you a Gauge Institue guy, Juan? lol