I explain Gödel's famous theorem at a high level. This form of the theorem is due to Chaitin. References and history can be found here: en.wikipedia.o....
Your video is so great! But I actually interpret Gödel's incompleteness theorem as good news for science. The theorem says that, for any fixed checker C, there is a statement S that C cannot prove. But given S, we can update C to C', which can prove S. For example, a human can learn, update their brain configuration from C to C', and give a good explanation for S. For another example, a mathematical foundation can update its foundation from C to C', which can derive S. My interpretation: There will never be a human with perfect knowledge or a final mathematical foundation that can prove everything. In fact, if there is one, progress is impossible in some sense as it is already perfect. With the incompleteness theorem, we actually know that, no matter how much we have learned, there will be infinitely many new things that we can learn. We can improve indefinitely. Please let me know if you think this interpretation is flawed.
Yes, maybe. But if there is a lesson that can help the human checker learn, then you could call that lesson the first part of the proof, and the theorem again applies. So if you think of the checker as the code of our brains when we are born, then there is a truth that cannot be proved no matter how much we are taught during our lives. Now the reality is that our brains are not a closed system with input and output… and our brains themselves change during our lives. So maybe we can think of the "program" as a simulator for the molecules inside our brain, and the initial configuration of that system is hardcoded in the program. Then during our entire lives, the program takes as input all interactions that our brain has with the outside world, and simulates the changes to the structure of the brain until the actual proof shows up, and then it simulates that too. The proof discussed in the video applies to this situation if the program is of finite length and all the input to it is of finite length. So, unless some step of these simulations cannot be carried out by programs, you have that there is a truth that we will not be able to verify!
Isn't the statement a proof, and a traditional proof is simply a duplicate of S in another form? Doesn't the statement prove the method of the proof? Which of them, statement or proof, has the honour or right to be considered as THE Proof?
How is program A shorter than L if A had to contain L to perform operations on its data? At the very least there is one comparison between two data variables x and L. Maybe you don't actually need to store L but only its log10(L) numbers of digits and when a comparison needs to be done you just perform arithmetic on **parts** of L's digits to conclusively verify that len(x) < L
We are not claiming that program A is shorter than L. We are claiming that program A is shorter than n. Also, the length of the program has nothing to do with x or L. The length of the program is the length of the code that describes the for loops etc. x and L are variables in the program, and their size is not relevant to the length of the program. Here n is fixed during the execution of the program, and n is hardcoded into the program using its digits. Hope that makes sense.
So, given a checker 'C', there exists a statement 'S' that is true such that for all proof 'p' C(S,p) ≠ 1 But what about: For all true statement 'S', there exists a checker 'C' and a proof 'p' such that C(S,p) = 1?
Set C to be the program that always outputs 1 and p to be the empty string, and you find your checker. You want your checker to actually reject false statements to be meaningful. Now, you could require that the C rejects all false statements and accepts S, but such a C also always exists: C just checks whether the input statement is S, and outputs 1 when that’s true.
@@anuprao11 Indeed the checker must be meaningful enough to prove basic arithmetic as of Godel's original theorem statement. And, of course, you want to have a checker that is somewhat arbitrary above arithmetic but fixed: for every Checker C (aka formal system) there is some true but unprovable statement S, but of course, by including S as an improvement (axiom) of the checker, you have now a new checker C' that can trivially prove S, but then there is another statement S' that is true but unprovable by C'
There are some things stronger than proof or knowledge. For example, pain. We don't "know" we are in pain, and our certainty is weak in the face of the experience itself.
Your disappointment was misplaced. Did you notice that Godel's theory used a pseudo-mathematical gesture that cannot be simulated by any mathematical or physical process such as a computer program? He employed a self-identifying demonstrative gesture. Self reference, such as "This sentence..." (whether S is true or false), is not a physical or mathematical gesture, it cannot be represented in computing or by any combination of mathematical elements or semiotic indices - mathematical symbols do not "point" to sentences or places on a page! Which is "this sentence.."? Mathematics does not tell us this. The gesture relies on tradition and expectation, on phenomenalistic object behavior, not the physical object behavior of mathematics. Godel's idea, built on a trite "paradox", which in phenomenalism is no paradox at all, was a pig in a poke. Mathematician's don't make good philosophers, most of the time anyway.
It’s not so complicated! The statement I presented here is self-contained, crystal clear, unambiguous and does not require any further interpretation. There is no gesturing or pointing required.
"there is a truth that cannot be proven" is actually a consequence of the extra assumption that a statement must be true or false. What Gödels proofs really say is that (if you have arithmetic) you either have undecided or self-referential statements. To me, this is a proof that you always have statements that can't be assigned the value of true or false meaningfully.
There is no such assumption made here. The theorem says that there is a true statement that cannot be proved, not that there is a paradox that cannot be proved. The statement that we found is either true or false: it does not reference itself.
@@anuprao11 the theorem in the video is a proof by contradiction which demonstrates that C cannot have finite length. Its an uncomputable function, and so it has infinite kolmogorov complexity. There are no true, unprovable statements. Thats a gross misunderstanding of godel incompleteness perpetuated by model theorists. The godel statement is not true in every model, and so its not true in the theory. Its just unprovable.
There is a truth that cannot be proved? I think you are reading too much into GIT. Fermat's Last Theorem is true, but it can't be proven in ZFC Set Theory.
@@anuprao11 There may well be truths the can't be proven. The statement sounds similar to Fitch's Paradox of Knowability. However, Gödel's Incompleteness Theorem doesn't say there are general "Truths" that can't be proven. He only says that higher order systems of logic (such has Peano Arithmetic), are incomplete. There is nothing GIT that says the sentence G can not be proven (or disproven) in some other system of logic (or even Math).
That’s not an accurate quote. What I said was that we do not know of any physical phenomenon that cannot be simulated by programs. If you disagree with that, I’d love to hear about a physical process that’s impossible to simulate with programs.
Let me suggest there are four way - theoretically, scientifically, religiously, or quadradically
Your video is so great!
But I actually interpret Gödel's incompleteness theorem as good news for science.
The theorem says that, for any fixed checker C, there is a statement S that C cannot prove.
But given S, we can update C to C', which can prove S.
For example, a human can learn, update their brain configuration from C to C', and give a good explanation for S.
For another example, a mathematical foundation can update its foundation from C to C', which can derive S.
My interpretation:
There will never be a human with perfect knowledge or a final mathematical foundation that can prove everything. In fact, if there is one, progress is impossible in some sense as it is already perfect.
With the incompleteness theorem, we actually know that, no matter how much we have learned, there will be infinitely many new things that we can learn. We can improve indefinitely.
Please let me know if you think this interpretation is flawed.
Yes, maybe. But if there is a lesson that can help the human checker learn, then you could call that lesson the first part of the proof, and the theorem again applies. So if you think of the checker as the code of our brains when we are born, then there is a truth that cannot be proved no matter how much we are taught during our lives. Now the reality is that our brains are not a closed system with input and output… and our brains themselves change during our lives. So maybe we can think of the "program" as a simulator for the molecules inside our brain, and the initial configuration of that system is hardcoded in the program. Then during our entire lives, the program takes as input all interactions that our brain has with the outside world, and simulates the changes to the structure of the brain until the actual proof shows up, and then it simulates that too. The proof discussed in the video applies to this situation if the program is of finite length and all the input to it is of finite length. So, unless some step of these simulations cannot be carried out by programs, you have that there is a truth that we will not be able to verify!
Isn't the statement a proof, and a traditional proof is simply a duplicate of S in another form? Doesn't the statement prove the method of the proof? Which of them, statement or proof, has the honour or right to be considered as THE Proof?
The statement is not the proof of the method.Rather the rigorous method is the proof of the statement.
Lovely proof
How is program A shorter than L if A had to contain L to perform operations on its data? At the very least there is one comparison between two data variables x and L. Maybe you don't actually need to store L but only its log10(L) numbers of digits and when a comparison needs to be done you just perform arithmetic on **parts** of L's digits to conclusively verify that len(x) < L
We are not claiming that program A is shorter than L. We are claiming that program A is shorter than n. Also, the length of the program has nothing to do with x or L. The length of the program is the length of the code that describes the for loops etc. x and L are variables in the program, and their size is not relevant to the length of the program. Here n is fixed during the execution of the program, and n is hardcoded into the program using its digits. Hope that makes sense.
So, given a checker 'C', there exists a statement 'S' that is true such that for all proof 'p' C(S,p) ≠ 1
But what about:
For all true statement 'S', there exists a checker 'C' and a proof 'p' such that C(S,p) = 1?
Set C to be the program that always outputs 1 and p to be the empty string, and you find your checker. You want your checker to actually reject false statements to be meaningful.
Now, you could require that the C rejects all false statements and accepts S, but such a C also always exists: C just checks whether the input statement is S, and outputs 1 when that’s true.
@@anuprao11 Indeed the checker must be meaningful enough to prove basic arithmetic as of Godel's original theorem statement. And, of course, you want to have a checker that is somewhat arbitrary above arithmetic but fixed: for every Checker C (aka formal system) there is some true but unprovable statement S, but of course, by including S as an improvement (axiom) of the checker, you have now a new checker C' that can trivially prove S, but then there is another statement S' that is true but unprovable by C'
We actually know things that cannot be computed.
There are some things stronger than proof or knowledge. For example, pain. We don't "know" we are in pain, and our certainty is weak in the face of the experience itself.
Your disappointment was misplaced. Did you notice that Godel's theory used a pseudo-mathematical gesture that cannot be simulated by any mathematical or physical process such as a computer program? He employed a self-identifying demonstrative gesture. Self reference, such as "This sentence..." (whether S is true or false), is not a physical or mathematical gesture, it cannot be represented in computing or by any combination of mathematical elements or semiotic indices - mathematical symbols do not "point" to sentences or places on a page! Which is "this sentence.."? Mathematics does not tell us this. The gesture relies on tradition and expectation, on phenomenalistic object behavior, not the physical object behavior of mathematics. Godel's idea, built on a trite "paradox", which in phenomenalism is no paradox at all, was a pig in a poke. Mathematician's don't make good philosophers, most of the time anyway.
It’s not so complicated! The statement I presented here is self-contained, crystal clear, unambiguous and does not require any further interpretation. There is no gesturing or pointing required.
"there is a truth that cannot be proven" is actually a consequence of the extra assumption that a statement must be true or false. What Gödels proofs really say is that (if you have arithmetic) you either have undecided or self-referential statements. To me, this is a proof that you always have statements that can't be assigned the value of true or false meaningfully.
There is no such assumption made here. The theorem says that there is a true statement that cannot be proved, not that there is a paradox that cannot be proved. The statement that we found is either true or false: it does not reference itself.
A statement cannot be said true unless it is proved.If you trust in the truthfulness then it is provable.
@@anuprao11 the theorem in the video is a proof by contradiction which demonstrates that C cannot have finite length. Its an uncomputable function, and so it has infinite kolmogorov complexity.
There are no true, unprovable statements. Thats a gross misunderstanding of godel incompleteness perpetuated by model theorists.
The godel statement is not true in every model, and so its not true in the theory.
Its just unprovable.
There is a truth that cannot be proved? I think you are reading too much into GIT. Fermat's Last Theorem is true, but it can't be proven in ZFC Set Theory.
I defined exactly what I meant by "cannot be proved" in the video! The result is much stronger than saying that a truth is not provable in ZFC.
@@anuprao11 There may well be truths the can't be proven. The statement sounds similar to Fitch's Paradox of Knowability. However, Gödel's Incompleteness Theorem doesn't say there are general "Truths" that can't be proven. He only says that higher order systems of logic (such has Peano Arithmetic), are incomplete. There is nothing GIT that says the sentence G can not be proven (or disproven) in some other system of logic (or even Math).
Sounds like you are talking about an older proof of GIT. The proof I explained is due to Chaitin. It is stronger.
@@anuprao11yeah, is more deep what you are saying
Anyone who thinks "there is nothing in the world that can evade the simulation of a program" is painfully naive, for starters.
That’s not an accurate quote. What I said was that we do not know of any physical phenomenon that cannot be simulated by programs. If you disagree with that, I’d love to hear about a physical process that’s impossible to simulate with programs.
@@anuprao11 Then why did you speak it?
@@James-ll3jb it’s taken out of context.
@@anuprao11 Whatvis the context if not your own stated one of quote unquote THE WHOLE WORLD!
Science is mere description, and explains nothing, friend. Try Nietzsche.