4 ms·
> there are statements which are unequivocally true, but which cannot be proved in any known formal system No. You are misunderstanding Godel's theorem. For
by lisper 9y ago
> there are statements which are unequivocally true, but which cannot be proved in any known formal system
No. You are misunderstanding Godel's theorem. For any given formal system there exists a Godel sentence which the system cannot prove. But the Godel sentence for every system is different. Moreover, there is no algorithm for constructing a Godel sentence. If there were, then a TM could follow that algorithm to construct its own Godel sentence.
So every formal system has a (different) Godel sentence, but there does not exist a universal Godel sentence that is unprovable by all formal systems.
- enugu 9y agoConstructing the sentence is algorithmic. The key part is asserting that the sentence is true. For instance ZFC will prove that A:(ZFC cant prove GodelStatement(ZFC) OR ZFC is inconsistent).GodelStatement is an algorithmic function which takes a list of axioms in some formal framework. Now, lets make ZFC' which is ZFC + 'ZFC is consistent'. ZFC' can prove A(as it contains ZFC) and uses the consistency of ZFC to prove A':(ZFC cant prove Godel(ZFC)) . Similarly, a program decides a set of problems(like does this Turing machine halt or does this diophantine equation have solutions) with access to its source code will be able to algorithmically generate the problem instance on which it will not halt. You can modify the program to create a new program which will use this information, but it will be a new program.
- lisper 9y ago> Constructing the sentence is algorithmic. No, it isn't. But it's a non-trivial point. > Similarly, a program decides a set of problems(like does this Turing machine halt or does this diophantine equation have solutions) with access to its source code will be able to algorithmically generate the problem instance on which it will not halt. You can modify the program to create a new program which will use this information, but it will be a new program. So this all depends on what you consider a "new program". Suppose we write a program that actually does this: analyzes its own code, algorithmically produces the Godel sentence for that code, then modifies its code to include that as an axiom, forever. That program is a program, and that program will also have a Godel sentence, but one which it cannot construct using that algorithm. You need a different algorithm to construct Godel sentences for programs that constructs Godel sentences on programs that don't construct Godel sentences. The result is a hierarchy of Godel-sentence constructors. At any level in the hierarchy the procedure is algorithmic, but going from one level to the next is not. It's similar to the process of constructing the hierarchy of ordinals, which is also provably non-algorithmic.
- enugu 9y agoThere is a program, G, which will take as input the source code of the program, P (in some fixed language) and output Turing machine, T which doesnt halt, such that either P will fail to say T doesnt halt, or P has mistakes(claims halting for some Turing machines when they dont halt). Some programs P can algorithmically run P', P'' etc, but as long as that process is part of the source code of P, G will work.
- lisper 9y agoSure. So? How does that in any way refute what I said?
- enugu 9y agoPoint in my first post was that G is algorithmic. What you are referring to is the repeated extension of G which gets into issues of ordinals.
- lisper 9y agoYes, but I'm the one who made the original claim that "there is no algorithm for constructing a Godel sentence". So I'm the one who gets to say what I meant by that :-)
- mcguire 9y agoTrue. Both haves of what I asked for are stronger than what Godel demonstrated. But for this argument to be applicable to the Theory of Mind, it seems to me that it is exactly what Lucas and Penrose are claiming to exist. If the only un-provable sentences are Godelian constructions, the whole issue isn't philosophically interesting. But that's not true, to my understanding. So, there are statements that cannot be proven in, say, ZFC. Some of these statements are, I assume, "interesting"; they aren't simply constructs that are designed to be unprovable. Finally, for Lucas and Penrose's arguments to be meaningful, some of those statements should be obviously true or false---that is the only way for the human mind to not be limited in the way ZFC is limited. If the truth of the statement is not obvious, then I'm not clear on how the human mind is stronger than the formal system in question. If the truth is obvious, but the statements are all variations on "I am lying" designed specifically for a given formal system, then I don't see how this is an actual interesting property of minds.
- moefh 9y ago> If there were, then a TM could follow that algorithm to construct its own Godel sentence. I don't understand what's the problem here. TMs are allowed to be inconsistent. There's a TM that outputs every single finite string. What would even count as its Godel sentence? In fact, there is an algorithm that constructs the Godel sentence given a consistent formal system capable of arithmetic. That algorithm is spelled out in Godel's original proof. Now, of course, a TM can only do that to its own formal system if it's inconsistent itself, which means the "Godel sentence" it output is meaningless.
- lisper 9y ago> TMs are allowed to be inconsistent. Sure, but that's an uninteresting case. Any inconsistent system that includes basic propositional logic asserts all statements to be true. So in these discussions consistency is generally assumed.