Great proof at the end, but it wasn't a proof by contradiction; it was a proof of a negative statement (there is not a finite number of primes). Most mathematicians are classically inclined, so they won't notice the difference. But many computer scientists and some mathematicians are interested in constructive mathematics and this proof is constructively acceptable although a proof by contradiction would not be.
Nice video. Complexity measures and psuedorandom sequences is a nice research area. Though from what I have seen it is surprisingly difficult to compute the Kolmogorov Complexity for a specific number; it is mostly a theoretical complexity used in proofs. Compare that to linear complexity, lempel-ziv complexity (used in data compression), and auto/cross correlation where you can find it by writing a computer program. More on the theoretical side, I've seen complexity measures where you define an equivalence relation and then create a measure based on the number of equivalence classes. I enjoy it. It's fun.
Thanks! Ya kolomogorov complexity being undefinable is definitely a practical probelm even if it ends up being useful in a bunch of theoretical applications (like the infinitely many primes proof here). Ironically I’m going to cover liv zemple for a different purpose in an upcoming video
Pi has to be totally irrational because otherwise there could be resonant feedback between surface waves and impact waves and the universe would self resonate to oblivion. By making sure there are NO harmonics which overlap there can be no resonance. Almost like an inverted prime. No amount of multiplying this number by any other number will get you an integer.
This one great trick to increase comments and boost the video in the algorithm is to make a basic mental math error in the first 2 minutes of a video:D I should tell Mr. Beast
6:52 i think comparison with x is log n, nothing defines the input length. Can x be 0, 00, 000, 0000, etc. Therefore comparison for equality is log n. The encoding details are crucial and the encoding later proposed is arbitrary length which is good but in the example you assume minimal bit encoding. The output is a problem too. Is it assumed to be at the start of the tape, as seems to be implied? Any information for locating or deciphering the output is also part of the complexity. But i dont recall this important aspect noted.
Not all problems that take exponential time are NP problems. They are only NP if you can verify the solution in constant or log time. Chess for example is not an NP problem. I can give you the evaluation for a position and it will still take exponential time to verify it. Sudoku is NP coz if you have the solution you can verify it instantly.
@popcat2309 I didn't say that. I said NP problems can be solved in exponential time. Learn to read and comprehend. Generalized chess on an nXn board is exponential time. You are picking on random points that are irrelevant
@popcat2309 you dont remotely even understand complexity and shouldn't be talking about it. Chess or any fixed size game are O(1) with a constant which at least in our best known algorithm which is exhaustive search or a table base and is galactic in magnitude. Be careful on here, know it all are more often than not, know nothings.
oh geeze. I have been informed by the masses that 2^5 is in fact 32, and not 16. Looking forward to the comments section on this one lol:D
Hey, so 2^5 is actually 32, not 16. Just thought to let you know you made an error. :)
That adds the Dr. Bezett unpredictability to the Kolmogorov randomness ;-)
@@Finkelfunkwhat would I do without you 😂
ох 😊
A Grothendieck prime- lol
I almost had an argument with myself in my head if that number is 16 or 32, lol. Glad you corrected it in description.
haha i'm trying to make y'all crazy:D
That typo will not let you go, I can tell you straight up.
Haha I say it like 30 times in the video too:D
The situation with 2^5= 16 reminds me anecdote about special number 57, which is called Grothendieck prime
The shirt would be way funnier if it said "EAT SLEEP M∃TH REPEAT"
hey now you're just trying to get me in trouble:D
Great proof at the end, but it wasn't a proof by contradiction; it was a proof of a negative statement (there is not a finite number of primes). Most mathematicians are classically inclined, so they won't notice the difference. But many computer scientists and some mathematicians are interested in constructive mathematics and this proof is constructively acceptable although a proof by contradiction would not be.
That is a really awesome proof of infinitely many primes!! So unexpected
Isn’t it cool?
Nice video. Complexity measures and psuedorandom sequences is a nice research area.
Though from what I have seen it is surprisingly difficult to compute the Kolmogorov Complexity for a specific number; it is mostly a theoretical complexity used in proofs. Compare that to linear complexity, lempel-ziv complexity (used in data compression), and auto/cross correlation where you can find it by writing a computer program. More on the theoretical side, I've seen complexity measures where you define an equivalence relation and then create a measure based on the number of equivalence classes.
I enjoy it. It's fun.
Thanks! Ya kolomogorov complexity being undefinable is definitely a practical probelm even if it ends up being useful in a bunch of theoretical applications (like the infinitely many primes proof here). Ironically I’m going to cover liv zemple for a different purpose in an upcoming video
Pi has to be totally irrational because otherwise there could be resonant feedback between surface waves and impact waves and the universe would self resonate to oblivion.
By making sure there are NO harmonics which overlap there can be no resonance.
Almost like an inverted prime.
No amount of multiplying this number by any other number will get you an integer.
Repeating the loop "2^5 =16" efficiently increases the number of comments. 🙄
This one great trick to increase comments and boost the video in the algorithm is to make a basic mental math error in the first 2 minutes of a video:D I should tell Mr. Beast
2:20 2^5 is not 16 🤔
oh geeze
2^5=32
Whats the catch with 2^5 and 16 though? I didn't understand
oops, just a typo. 2^5=32!
@@DrTrefor 32 factorial?? 😂
@@DrTrefor btw i respect and love your videos so much professor you're one of the best ones 🙌 love from India 🇮🇳
6:52 i think comparison with x is log n, nothing defines the input length. Can x be 0, 00, 000, 0000, etc. Therefore comparison for equality is log n. The encoding details are crucial and the encoding later proposed is arbitrary length which is good but in the example you assume minimal bit encoding. The output is a problem too. Is it assumed to be at the start of the tape, as seems to be implied? Any information for locating or deciphering the output is also part of the complexity. But i dont recall this important aspect noted.
Where can I learn more about this subject area
Doubling is such a bad word choice. To some it is a math operation. You are duplicating each bit of x.
wouldn't trying to find a best f also run into P vs NP?
NP problems are decidable in exponential time. Here it is not even decidable. You are confused
Not all problems that take exponential time are NP problems. They are only NP if you can verify the solution in constant or log time.
Chess for example is not an NP problem. I can give you the evaluation for a position and it will still take exponential time to verify it. Sudoku is NP coz if you have the solution you can verify it instantly.
@popcat2309 I didn't say that. I said NP problems can be solved in exponential time. Learn to read and comprehend. Generalized chess on an nXn board is exponential time. You are picking on random points that are irrelevant
@popcat2309 you dont remotely even understand complexity and shouldn't be talking about it. Chess or any fixed size game are O(1) with a constant which at least in our best known algorithm which is exhaustive search or a table base and is galactic in magnitude. Be careful on here, know it all are more often than not, know nothings.
Is it normal?
we don't know!
wouldn't the complexity of a random string be log(y) because that is the least amount of bits you need to use
oh i got confused because there weren't absolute values around the strings so i thought we looked at them as numbers
Ya that’s right, difference between the length of the number and the full number