why are the implications of this theorem so vast? it seems for a consistent system we've proved that the sentence G in question which reads "G is not provable" must be true, i.e. we've found a true but unprovable statement. in other words all we've shown is a trivial, self-referential statement is true but unprovable. what's the big deal?
The only problem that can occur is in the creation of an endless recursion loop. If the program, while testing its own algorithm, decides that it must account for what happens when the algorithm tests itself, then it must test that situation by having the algorithm test itself while the algorithim being tested is also testing itself, and on, and on.
In other words, the program can never make a decision as long as it is testing a program that does not stop.
On the other hand, if the program is clever enough to decide if another program will stop simply by inspecting it's algorithm, then we have a different situation. It will then look at its own algorithm and decide that the algorithm is designed in such a way that it can stop. And so it will keep running.
Another problem. You say that the program stops when it finds a program that does not stop. How does it find a program that does not stop? If it finds it by running the program, then it would never stop because the program that it is running continues forever and the first program that is running it cannot stop because it can never know if the program that it is running will stop. This means that the testing program cannot do its job even without testing itself. (continued)
Your explanation doesn't make sense. On the one hand you say that the program is designed to find every program that does not stop, on the other hand you say that the program stops when it finds just one program that does not stop. If you are going to test every program, you cannot, by definition, stop after finding just one program that doesn't stop. There seem to be more explanation problems further down the line, but let's fix this one and then go from there.
You say that the program designed to test every program for whether it stops or not, stops when the input code is a program that doesn't stop. But why wouldn't this evaluation-program stop anyway with just a short notice: either "The program you inserted stops." or "The program you inserted doesn't stop."??
Then, if you inserted its own code into it for evaluation, it would stop and state that the code you've inserted stops at some point...
"Clever computer which has a program to test every other program to see whether or not they will stop." Not sure I understand, But I don't think that it is possible to write such a program.
Didn't Alan Turing go over this? You can't know in advance if a program will fail to find a solution.
The question "What two equal integers add to three?" is a false question, with no solution. The computer will try to calculate every possibility ad infinatum.
@AcePilot101 you are not far from what this proof suggests... Godel was a Platonist mathematician. Truth exists befor we know it, we simply discover it. not sure about the god thing, but Godel does present a Mathematical proof that God does exist some time in his life.
@hiestd Is that like the mathematical proof a bumble bee can't fly? How in the hell could math prove an existence? Math may suggest an existence but the proof must be in reality not math.
@FartsOutDust1901, I guess the dumb fuck operates under the assumption,"real" and "exist" are contextually equals. Thus, he cannot believe there is a mind, but only a brain. There are many of this kind.
"Don't let go" by a 80's band from Liverpool called "Pink Industry". Too far ahead of their time to be very popular then and none of their material is available now except as very expensive collector's items or via the internet. They are very easily the best thing about a number of the presentations I've uploaded.
@Frege100 so is Godel saying nothing is or can be perfect on its own, and requires reliance on another set of logics. If so, would it be fair to say in order to identify/prove/validate something from a 1st point of view perspective needs help from a 3rd point of view perspective. I've personally had a mental problem in highschool by always trying to look at things at a 3rd point of view perspective. I think I later on lost my self-conscience but gained an amount of insight.
@rainzoro he's saying that axiomatized arithmetic languages are either consistent or complete. so, if you have a consistent system, it will be incomplete. but, you can prove the statements by creating a larger system around the original system (an extension I believe) and use the larger system to prove undecidable systems in the original system. The only problem is, now in this new system, there are new undecidable propositions....
I am a bit confused. At 1:08 you say the cleverer computer has a program designed to test every OTHER program (my emphasis) then you have it testing itself. WHY?!?
exactly but, it is possible to write such a program (just simply apply a range technique. Kind of confuses me and I'm a theorist in this field. A better example is writing a program which checks for solutions for a^3 + b^3 = c^3 cause that will never halt.
I am very familiar with the subject matter of this video, as my postgraduate degrees are in set theory and model theory. So I can follow it, but others may not be able to because of minor errors of terminology. For example, it is really about Godel's incompleteness thm, not his completeness thm (yes, there is one, and it does not contradict the incompleteness thm; the premises are different). I can't explain the difference in the space I have here.
i'm just curious about Godel's incompleteness theorem. Is there a way ( simple or complicated ) to know whether a statement is provable or not in a certain formal language? Take for example the continuum hypothesis in set theory. And we have certain conjectures like Goldbach Conjecture. Could it be possible that Goldbach Conjecture is undecidable within the current axioms of number theory or other branches of mathematics?
The short answer is no. To be able to tell whether a given statement is provable would be like the computer program that can tell whether a given program ever stops. In particular, however, it has been proven that, if set theory is consistent, the continuum hypothesis is not provable; neither is its negation. The latter was proven by Godel in 1930; the former, by Paul Cohen in 1963. The Goldbach Conjecture cannot be similarly undecidable, because a single counterexample would decide it.
@maths486 there are ways of proving if something is not provable. one has to prove it is not provable, and not disprovable, though. I'm pretty sure its not simple...
who is the track by. i've often wondered if maths relies on interpretation and not logic. i'm specifically thinking of the "monty hall" problem and the conclusions derived from so many academics being wrong.
@hume12345 The Monty Hall problem? A lot of academics get that one wrong? Well I guess I can believe that, it's kind of tricky. Bayes theorem is kind of tricky at first too. People don't quite think it through because they think "oh I know this, this is just basic probability." I think that's what happens with the Monty Hall problem too. In both cases though if you actually trace out what's happening at each step, it's pretty easy to understand. Humans often jump to conclusions though.
If I had made this video, I surely would have mentioned Effective Procedures and emphasized that over "computer program".
My reasoning here is that "computer program" implies a finite amount of computing time. Whereas an Effective Procedure is allowed to progress infinitely and still be "effective."
Theoretically, a computer program could run forever. In practice, it would be necessary to make sure the computer has an uninterrupted supply of power, and it might need to be paused a few times per century to allow maintenance to be done on the hardware, etc.
Not a bad explaination - you start with Turing's Halting Problem, which is more of a pragmatic problem of self-reference in terms of computational science than much to do with Godel's theorem (which seems a bit of a jump when you start to introduce it), but the rest of the video is quite kosher (if running slightly parallel to the original proof, but I understand why ;) ).
Could you please answer something for me? Is there an error in logic here, regarding the future tense of stopping, (i.e.; systems which will stop vs. systems which will go on forever)? It seems to me that the proper logical distinction would be systems which "are stopped" (sorry but I couldn't phrase it any better), and systems which are not stopped. I was thinking that the future doesn't really have a place in logic, much as the concept of infinity doesn't. It's either open or closed.
I don't know if that makes any sense or not. It seems to me that each person's concept of infinity is deceptively personal and unique. Although seeming to be ubiquitous. What it really seems to mean, in the phenomenological sense, is a state of waiting, unknowing, suspended conclusion. I mean this in the "immediate" sense as it is experienced right now. Neither a computer program, nor an Effective Procedure can determine that which will or will not stop.
Regarding infinity - there are general consensus' on the meaning of what is/are infinite - positive natural numbers, decimal places of pi (we hope ;-) ), prime numbers (within or without Riemann...), etc.
I can't say I've considered the 'infinite' as a phenomenological form, but the question posed; 'is my infinite the same (or bigger!) than yours?' is an interesting one. Again, comments welcome...
Thank you for your help! Unfortunately, I never really studied logic in depth and lack the terminology to express what I'm trying to say. It is fascinating though.
I think that the term 'will stop' is overly ambiguous - it's a common problem when dealing with Modal and Temporal logics - does 'will stop' mean 'will stop eventually in the future' or 'it is necessary that it will stop'? I think the latter is more appropriate, but feel free to disagree!
There are temporal logics that deal with the modalities of the future and past, but these are different from the normal modalities of necessity and possibility.
The concept of infinity very much does belong in logic. It is defined by saying that a set is infinite if it has a one-to-one correspondence to a proper subset of itself. For example, the positive integers 1, 2, 3, ... is a proper subset of the non-negative integers 0, 1, 2, .... The correspondence is defined by the simple formula n+1. And there is no error in logic (maybe of English grammar) in saying that a program will either eventually halt, or it won't.
nice video.. and i do love logic.. :)
lovelplants 1 month ago
Nice summary, thank you
klimaxg 2 months ago
why are the implications of this theorem so vast? it seems for a consistent system we've proved that the sentence G in question which reads "G is not provable" must be true, i.e. we've found a true but unprovable statement. in other words all we've shown is a trivial, self-referential statement is true but unprovable. what's the big deal?
TheShankman 3 months ago
The only problem that can occur is in the creation of an endless recursion loop. If the program, while testing its own algorithm, decides that it must account for what happens when the algorithm tests itself, then it must test that situation by having the algorithm test itself while the algorithim being tested is also testing itself, and on, and on.
vsaluki 10 months ago
In other words, the program can never make a decision as long as it is testing a program that does not stop.
On the other hand, if the program is clever enough to decide if another program will stop simply by inspecting it's algorithm, then we have a different situation. It will then look at its own algorithm and decide that the algorithm is designed in such a way that it can stop. And so it will keep running.
vsaluki 10 months ago
Another problem. You say that the program stops when it finds a program that does not stop. How does it find a program that does not stop? If it finds it by running the program, then it would never stop because the program that it is running continues forever and the first program that is running it cannot stop because it can never know if the program that it is running will stop. This means that the testing program cannot do its job even without testing itself. (continued)
vsaluki 10 months ago
Your explanation doesn't make sense. On the one hand you say that the program is designed to find every program that does not stop, on the other hand you say that the program stops when it finds just one program that does not stop. If you are going to test every program, you cannot, by definition, stop after finding just one program that doesn't stop. There seem to be more explanation problems further down the line, but let's fix this one and then go from there.
vsaluki 10 months ago
You say that the program designed to test every program for whether it stops or not, stops when the input code is a program that doesn't stop. But why wouldn't this evaluation-program stop anyway with just a short notice: either "The program you inserted stops." or "The program you inserted doesn't stop."??
Then, if you inserted its own code into it for evaluation, it would stop and state that the code you've inserted stops at some point...
vivvpprof 10 months ago
Yes.. It would be vast indeed.
Good vid keep it up!
messakg123 1 year ago
I understood about 60% of this video this time.
An improvement on my previous 40%.
seniorbooboojuice1 1 year ago
Godot's 'Sentance G' reminds me of Gene Roddenberry's Kirkian logic statement "I always lie."
ERROR! ILLOGICAL!! STERILZE!!!
But this begs the question... Has anyone ever determined the numerical equivalent of sentance G?
L00NGB00W 1 year ago
Hmm.
"Clever computer which has a program to test every other program to see whether or not they will stop." Not sure I understand, But I don't think that it is possible to write such a program.
Didn't Alan Turing go over this? You can't know in advance if a program will fail to find a solution.
The question "What two equal integers add to three?" is a false question, with no solution. The computer will try to calculate every possibility ad infinatum.
L00NGB00W 1 year ago
Thanks.
Math is beauty.
Quinzio 1 year ago
oh my gosh my mind hurts
angwird12 1 year ago
What about emergence and evoltution of new "things" ? Aswell as the observer ? Where are they ?
etiennealive 1 year ago
All you need to know about logic.
God is the Spirit of TRUTH, Satan is the Master of lies.
Satan told Adam and Eve that God was a liar and this lead to the fall of man.
We've been in trouble ever since but Jesus came to set us free.
Repent of your foolish pride and sins and enjoy eternal life in Jesus Christ!
AcePilot101 1 year ago
@AcePilot101 Shh the adults are trying to watch something amazing here. Come back when you have a semblance of intelligence.
crazycanook102 1 year ago 2
@AcePilot101 lol
Pwnagemerchant 1 year ago
@AcePilot101 lol?
pplus0440 1 year ago
@AcePilot101 you are not far from what this proof suggests... Godel was a Platonist mathematician. Truth exists befor we know it, we simply discover it. not sure about the god thing, but Godel does present a Mathematical proof that God does exist some time in his life.
hiestd 11 months ago
@hiestd Is that like the mathematical proof a bumble bee can't fly? How in the hell could math prove an existence? Math may suggest an existence but the proof must be in reality not math.
crossoldman 7 months ago
@crossoldman actually there are many mathematical proofs of existence.
FartsOutDust1901 3 months ago
@FartsOutDust1901, I guess the dumb fuck operates under the assumption,"real" and "exist" are contextually equals. Thus, he cannot believe there is a mind, but only a brain. There are many of this kind.
Idol2011no 2 months ago
WTF? Sloppy drunk lisanova is featured video on godels theorem?
MarauderU 2 years ago 2
what song is this?
tseliottt 2 years ago
"Don't let go" by a 80's band from Liverpool called "Pink Industry". Too far ahead of their time to be very popular then and none of their material is available now except as very expensive collector's items or via the internet. They are very easily the best thing about a number of the presentations I've uploaded.
Frege100 2 years ago
@Frege100 so is Godel saying nothing is or can be perfect on its own, and requires reliance on another set of logics. If so, would it be fair to say in order to identify/prove/validate something from a 1st point of view perspective needs help from a 3rd point of view perspective. I've personally had a mental problem in highschool by always trying to look at things at a 3rd point of view perspective. I think I later on lost my self-conscience but gained an amount of insight.
rainzoro 1 year ago
@rainzoro he's saying that axiomatized arithmetic languages are either consistent or complete. so, if you have a consistent system, it will be incomplete. but, you can prove the statements by creating a larger system around the original system (an extension I believe) and use the larger system to prove undecidable systems in the original system. The only problem is, now in this new system, there are new undecidable propositions....
hiestd 11 months ago
1:08 = programme only stops if it does not stop. There is the paradox.
Ontologistics 2 years ago
I am a bit confused. At 1:08 you say the cleverer computer has a program designed to test every OTHER program (my emphasis) then you have it testing itself. WHY?!?
agentredlum 2 years ago
Sorry! I should have written "every other programme and itself."
Thanks for pointing it out.
Frege100 2 years ago
I don't understand the problem, why would the program go looking for values of n, such that
n + n > 3
Isn't that already illogical?
Seems like a bad program with an infinite loop, i.e. missing a base case.
MrLosername 2 years ago
exactly but, it is possible to write such a program (just simply apply a range technique. Kind of confuses me and I'm a theorist in this field. A better example is writing a program which checks for solutions for a^3 + b^3 = c^3 cause that will never halt.
Entertainmentwf 2 years ago
it's spelled princeton
solomon1899 2 years ago
I am very familiar with the subject matter of this video, as my postgraduate degrees are in set theory and model theory. So I can follow it, but others may not be able to because of minor errors of terminology. For example, it is really about Godel's incompleteness thm, not his completeness thm (yes, there is one, and it does not contradict the incompleteness thm; the premises are different). I can't explain the difference in the space I have here.
dirtybitbucket 2 years ago
i'm just curious about Godel's incompleteness theorem. Is there a way ( simple or complicated ) to know whether a statement is provable or not in a certain formal language? Take for example the continuum hypothesis in set theory. And we have certain conjectures like Goldbach Conjecture. Could it be possible that Goldbach Conjecture is undecidable within the current axioms of number theory or other branches of mathematics?
maths486 2 years ago
The short answer is no. To be able to tell whether a given statement is provable would be like the computer program that can tell whether a given program ever stops. In particular, however, it has been proven that, if set theory is consistent, the continuum hypothesis is not provable; neither is its negation. The latter was proven by Godel in 1930; the former, by Paul Cohen in 1963. The Goldbach Conjecture cannot be similarly undecidable, because a single counterexample would decide it.
dirtybitbucket 2 years ago
@maths486 there are ways of proving if something is not provable. one has to prove it is not provable, and not disprovable, though. I'm pretty sure its not simple...
hiestd 11 months ago
who is the track by. i've often wondered if maths relies on interpretation and not logic. i'm specifically thinking of the "monty hall" problem and the conclusions derived from so many academics being wrong.
hume12345 2 years ago
@hume12345 The Monty Hall problem? A lot of academics get that one wrong? Well I guess I can believe that, it's kind of tricky. Bayes theorem is kind of tricky at first too. People don't quite think it through because they think "oh I know this, this is just basic probability." I think that's what happens with the Monty Hall problem too. In both cases though if you actually trace out what's happening at each step, it's pretty easy to understand. Humans often jump to conclusions though.
weedipikia 1 year ago
If I had made this video, I surely would have mentioned Effective Procedures and emphasized that over "computer program".
My reasoning here is that "computer program" implies a finite amount of computing time. Whereas an Effective Procedure is allowed to progress infinitely and still be "effective."
otonanoC 3 years ago
Comment removed
dirtybitbucket 2 years ago
This has been flagged as spam show
Theoretically, a computer program could run forever. In practice, it would be necessary to make sure the computer has an uninterrupted supply of power, and it might need to be paused a few times per century to allow maintenance to be done on the hardware, etc.
dirtybitbucket 2 years ago
Not a bad explaination - you start with Turing's Halting Problem, which is more of a pragmatic problem of self-reference in terms of computational science than much to do with Godel's theorem (which seems a bit of a jump when you start to introduce it), but the rest of the video is quite kosher (if running slightly parallel to the original proof, but I understand why ;) ).
Good work!
Sapere Aude,
M.
MCtheMD 3 years ago
Could you please answer something for me? Is there an error in logic here, regarding the future tense of stopping, (i.e.; systems which will stop vs. systems which will go on forever)? It seems to me that the proper logical distinction would be systems which "are stopped" (sorry but I couldn't phrase it any better), and systems which are not stopped. I was thinking that the future doesn't really have a place in logic, much as the concept of infinity doesn't. It's either open or closed.
chickenmcthug 3 years ago
I don't know if that makes any sense or not. It seems to me that each person's concept of infinity is deceptively personal and unique. Although seeming to be ubiquitous. What it really seems to mean, in the phenomenological sense, is a state of waiting, unknowing, suspended conclusion. I mean this in the "immediate" sense as it is experienced right now. Neither a computer program, nor an Effective Procedure can determine that which will or will not stop.
chickenmcthug 3 years ago
Regarding infinity - there are general consensus' on the meaning of what is/are infinite - positive natural numbers, decimal places of pi (we hope ;-) ), prime numbers (within or without Riemann...), etc.
I can't say I've considered the 'infinite' as a phenomenological form, but the question posed; 'is my infinite the same (or bigger!) than yours?' is an interesting one. Again, comments welcome...
M.
MCtheMD 3 years ago
Thank you for your help! Unfortunately, I never really studied logic in depth and lack the terminology to express what I'm trying to say. It is fascinating though.
chickenmcthug 3 years ago
This has been flagged as spam show
I think that the term 'will stop' is overly ambiguous - it's a common problem when dealing with Modal and Temporal logics - does 'will stop' mean 'will stop eventually in the future' or 'it is necessary that it will stop'? I think the latter is more appropriate, but feel free to disagree!
There are temporal logics that deal with the modalities of the future and past, but these are different from the normal modalities of necessity and possibility.
Hope this helps - comments welcome.
M.
MCtheMD 3 years ago
Comment removed
MCtheMD 3 years ago
The concept of infinity very much does belong in logic. It is defined by saying that a set is infinite if it has a one-to-one correspondence to a proper subset of itself. For example, the positive integers 1, 2, 3, ... is a proper subset of the non-negative integers 0, 1, 2, .... The correspondence is defined by the simple formula n+1. And there is no error in logic (maybe of English grammar) in saying that a program will either eventually halt, or it won't.
dirtybitbucket 2 years ago