What Computers Can't Do - with Kevin Buzzard
Вставка
- Опубліковано 31 тра 2024
- Kevin Buzzard explains one of the biggest unsolved problems in theoretical computer science - the P vs NP problem.
Watch the Q&A here: • Q&A - What Computers C...
Subscribe for regular science videos: bit.ly/RiSubscRibe
Today’s computers are lightning-fast. But sometimes we want to make sure that they can’t solve a particular task quickly (perhaps for security purposes). This issue lies at the heart of the P vs NP problem, one of the most famous conundrums in computer science, which Kevin Buzzard will explore in this Discourse. Can every problem whose solution is quickly verifiable by a computer, also be quickly solved by a computer?
Kevin Buzzard is a British mathematician and currently a Professor of Pure Mathematics at Imperial College London. He specialises in algebraic number theory.
The Ri is on Twitter: / ri_science
and Facebook: / royalinstitution
and Tumblr: / ri-science
Our editorial policy: www.rigb.org/home/editorial-po...
Subscribe for the latest science videos: bit.ly/RiNewsletter - Наука та технологія
You can tell it's a proper math talk when the slides were made in LaTeX.
not just latex but beamer too!
If it's in LaTeX, it must be true
I almost left because of the pants then I saw the slides and decided to stay.
Nothing about this was proper math
And because he couldn't be bothered figuring out how to make animated/interactive slides - what a nightmare
Dude walked 10K laps around that damn table.
In his pajama pants, no less.
That's quite a choice in trousers to wear for a lecture at the Royal Institution
Proving that maths geeks are fabulous!
He didn't choose them; the RI randomly issues a 'uniform' to its lecturers.
I couldn’t help but think of a certain investigator in Alan Moore’s From Hell.
They're pyjamas. He also missed his morning coffee.
@@suntexi wrong, he wears crazy trousers to all his imperial lectures
16:48
problems reviewed in class: bisect an angle
problems on the test: trisect an angle
As a philosophy graduate who had never encountered the computer science P vs NP problem before watching this, I first read the description to be the formal logic "P or Not P," and the concept of computers struggling with that made me chuckle.
I thought the end joke was going to be "and now I have a pee problem" or "to pee or not to pee". :D
As a Phil grad, how is it possible you've never heard of P vs Np
I love this channel. I try to watch and fully understand/comprehend at least 3 of the lectures posted here, per week, choosing a variety of topics to learn a little more about diverse subjects. Taking them in and taking time to digest and contemplate them, at my own rate, is making a big difference in the way I see and deal with the world at large. Expanding one's "horizons" in ANY way is never a bad idea IMO.
This is great 👍
Four years later, we are pleased to inform you that the Royal Institution has been shuttered in an attempt to heal the wounds left by 200 years of colonizing the world with accurate and predictive scientific theories. With luck, we shall all soon return to our collective indigenous roots of poking each other with sharp sticks. We appreciate and fully validate your lived experience while we undergo this transformation.
@@amarissimus29 Abyssus Abyssum Vocat.
As far as i can remember that "killer robot" is ment to be "just" a transporter thingie, replacing a mule/horse/camel (or human) carying heavy objects on terrain where regular 4WD vehicles can't go, no weapons added (for now)...
We have way more effective (and likely cheaper/less complex=less worry if they get shot down) flying killer robots-drones.
Automated cars are also killer robots though.
I don't think it was meant to be a very serious exploration of Google's plans for global domination
The problem with saying that computers can't 'think' is that you are comparing something that is known very well (what computers do), with something about which we know almost nothing (how humans think). Neuroscientists have literally just scratched the surface on the subject of human thinking and we may find, as we dig deeper into human thinking, that at the bottom there lies a series of basic operations akin to computer instructions, that is every bit as predictable. A comparison such as that, between something known and something unknown is essentially meaningless. Anyone claiming to have an opinion on the subject really has nothing more than a guess - and not even an educated one.
The reason why we feel intuitively that human thinking must be very different to what computers do is down to the old saying 'familiarity breeds contempt'. Our familiarity with computers leads us to downplay what they do, while our unfamiliarity with human thinking (as in how it works) leads us to treat it with a degree of awe and wonder that may not be due.
Agreed. The argument here that computers cannot think is very weak. We believe from Church-Turing that a computer can perform any algorithm. So the question is simply whether or not human minds follow an algorithm, and the answer is.... we don't know nearly enough about the human mind yet to know whether or not it does (but we certainly haven't discovered anything yet that would preclude it following an algorithm). I find that even the best arguments against computers ever being able to do all the things a human mind can do ultimately rely on an assumption that there is something "special" about human minds (which has yet to be scientifically demonstrated) that computers lack the ability to do.
@Epsilon Theta If the indeterministic functions can be modeled by deterministic functions with random inputs, then we could still make an algorithm that performs that behavior.
Epsilon Theta I’m not asserting that computers are capable of human cognition, just that the argument against it is very weak. Although I would remind everyone that computers have been made to do a great many things that most people once thought they would never be able to do. That said, could you cite this Penrose paper? I’m curious to take a look. (Although, I will note that cognition would have to be doing something different from *Turing’s* (and Church’s) definition of “algorithm”... I’m not sure if this way AI defines it is any different...)
Yeah, as far as I'm concerned there's zero reason a computer *couldn't* think.
Humans think. Humans are able to think because of our brains/nervous systems. A nervous system is a physical object whose behaviour is governed by physical laws.
Computers can model and simulate physical laws and their effects on matter to an effectively arbitrary level of accuracy (the limits of which all have to do with scope and processing power- you can't make an "oracle" that can perfectly predict the universe without using at least as much matter and energy as the universe).
Hence, if a computer was given enough accurate data/parameters, it could simulate a human brain with total or near-total accuracy.
A simulated brain that produces behaviour identical to or comparable with that of a "real" brain is effectively indistinguishable from a "real" brain if you look at the output behaviours.
It doesn't matter how the behaviours are generated, ultimately; if you were extremely patient and had an infinite lifespan I'm sure you could simulate a person and a little box environment for them to live in using a sufficiently large number of rocks assembled into logic gates.
Furthermore, our brains are not terribly efficient. Its fairly rare for nature to produce something in "the most efficient way possible", and I feel confident saying that cognition is likely one of those things it has failed to produce efficiently. Thus, there are probably ways to get human-like behaviour and "thought" out of a system less complex/resource hungry/large than a human brain.
We don't know how _yet,_ but there's nothing we know about physical laws that would imply its impossible.
Even a "dumb" system can produce incredibly complicated behaviours and react to stimuli in "intelligent" manners, too. Just look at an ant nest.
@@DarkestMirrored
Beautifully stated! Couldn't have said it better myself!
The first description of AI with the conclusion that computers can't think is awfully outdated. For a less outdated comparison we shouldn't be comparing Garry Kasparov vs Deep Blue, we should be comparing Lee Sedol vs Alpha Go. The main difference here being, alpha go uses an artificial neural network -- the search space is too large to simply use a brute force approach. So Alpha Go makes decisions in a manner that resembles intuition, it picks the moves it "thinks" will be best based on games it has previously played/seen and it narrows the search space by only evaluating moves it "thinks" are most relevant.
Whether or not it's _really_ thinking to me seems to just be a matter of semantics. I've yet to see a list of criteria for "thinking" that is demonstrably applicable to biological neural networks (brains) but not applicable to artificial ones.
I think the IBM Jeopardy challenge was way cooler.
Agreed. The argument here that computers cannot think is very weak. We believe from Church-Turing that a computer can perform any algorithm. So the question is simply whether or not human minds follow an algorithm, and the answer is.... we don't know nearly enough about the human mind yet to know whether or not it does (but we certainly haven't discovered anything yet that would preclude it following an algorithm). I find that even the best arguments against computers ever being able to do all the things a human mind can do ultimately rely on an assumption that there is something "special" about human minds (which has yet to be scientifically demonstrated) that computers lack the ability to do.
Indeed, it seemed to me that this guy is at least a decade late on AI technology.
Adding to AlphaGo, there is now AlphaStar that is an amazing starcraft player which is arguably an even stronger feat for an AI.
Nothing has changed in that regard, AlphaGo still doesn't think, it solves a different problem much more efficiently, (IE finds a local minimum of a function, using multiple layers). AlphaGo doesn't decide to take a toilet break and go for a smoke, it just solves a complex system without using brute-forcing. There's only an "illusion" of thinking, because of the way those beautiful mathematical tricks are applied, but in reality that is in fact the opposite of thinking as a process.
@@ziocletouk It processes input in the same way our neurons do though.
But yes, they are currently not powerful enough to be considered "thinking" yet.
But what is "Thinking" though?
Surely it's not about going to toilets and wanting to smoke, since humans though before the invention of either. And those processes are merely how we learnt to respond to stimuli like "I feel pressure in the bladder" or the neuroreceptors need their dose of dopamine.
In the end we are a very large neural nerwork, with biologically pre-configured settings and with many inputs (our senses), while DeepMind only has a single specific input and a much smaller network.
But would we be considered "thinking" without all our senses?
Here is a though experiment for you: Immagine a baby that is just born without senses (he cannot see, feel, hear, smell,...) would he be "thinking" even if we wait 30 years? If yes, can you describe what his thoughts would be?
Thanks to the RI and Prof. Kevin Buzzard for a fast show intro into what's computable and what may not be. Brilliant!
first 35:00 minutes some computer history working up to explain The Halting Problem. Then the rest is, "We have yet to prove is P=NP or (P not = NP)".
Thank you for saving one hour of my life!
My issue with the halting problem is that you can't write a computer program that checks any computer program for bugs. But a human can check any computer program for pugs. So human thought is not the same as a computer?
Yes, humans can check any computer program for bugs, but i don't think anybody has found a way (an algorithm) to eliminate all bugs, without error, meaning not leaving any out. People would pay a lot of money for that, if the method was somewhat fast. Only if this is the case, does this specific argument for human thought being different from that of a computer hold.
" human can check any computer program for bugs"... well can they? Once those programs get thousands of lines of code (or tens of thousands, hundreds of thousands) humans need assistance of computer to see where the bug in the code is.
There are so many different possible types of bugs. Humans have advantage of being able to look at things in more abstract way instead of testing every possible input, but I think it is just temporary till computers are "taught" to look for the same things humans look for.
Jesper Birch there are programming techniques that rely on brute force to weed out bugs, things like genetic algorithms and self programming neural networks can solve problems in peculiar and innovative ways (they aren't capable of finding said problems yet, but wait)
It remains very difficult (maybe impossible) to prove that a thing does not exist. I demonstrated this in teaching logic by telling students that I might have hidden a $100 note somewhere in the room. They were charged with proving that I hadn't. Of course, no class could ever do it. Now I know why; it's a problem in NP. If I give them the location, they can easily check to see if the money is there. If they can't find it, I can always note a place where they haven't looked.
Well only 3 years later.
But to my understanding that only works if the room is not set or is sufficient big.
If the room size is set you can say they could check every bit of space in the room where a (maybe folded but intact) $100 note fits. (as long as the room is not too big)
The problem you "want" for NP would be specified as "Can you proof that i did not hid a $100 note in ANY (but still given) room.
Ps. thats my understanding but i am pretty sure of it. And hopefully i made it clear enough what i mean :).
@@Rosskoish Even within a finite space, be that physical or virtual or conceptual, there is always a stone unturned. The $100 note could be in my pocket, a place the students cannot lawfully search. But it's still in the room.
@@rangersmith4652 But if it's in your pocket and you do not allow the students to check there, it's not NP either.
Remember a solution has to be verifiable (in polynomial time but doesn't matter for that example). If you do not allow the students to check your pockets they could not verify the answer "it is in my pocket" even when the answer is given.
For the space yes it can't be too big to be searched in a reasonable time but in that example it's hard to specify that. Let's just say they would have their whole life.(or atleast a couple of hours/days to turn every stone around)
@@Rosskoish Let's assume they have enough time to check every conceivable location and that it is not on my person. There will always be some place in the room they don't check because their search will always exclude all locations that are inconceivable (to them) simply because they're -- inconceivable to them. A typical classroom is physically much more complex than one would tend to think, providing a lot of possible hiding places. All I have to do to keep them from finding the money is put it in a place they will not think about as a possible hiding place. That is to say, as long as my imagination is more vivid then theirs, they will not think of looking in the spot I used, and they will only find the money by pure chance. If I tell them where it is, they can quickly go there and find it, verifying the solution -- NP. But any declaration that the money is not in the room remains invalid.
There are many impossibility results, which proves it is often possible to prove an impossibility.
In many cases the trick is to find a property of the kind of object you are studying that remains invariant under the transformations you allow. If you can then show that the value of this property differs between your starting point and your end point, you have proven the impossibility of getting from the start point to the end point.
The idea that proving P=NP true would lead to all these shocking consequences (e.g. encryption breaking) assumes that any proof of P=NP would be 'constructive' i.e. that the proof itself would outline *how* (construct) we could quickly prove (move to P) something that's quickly verifiable (NP). This would be some general schema or framework applicable to any NP problem, like a computer program.
Proofs, however, needn't be constructive: they needn't actually design some process to achieve the desired outcome but, rather, show its truth based on general principles. Mathematicians don't all agree that a P=NP proof would necessarily be constructive.
So, even if P=NP is proven to be true, if the proof is non-constructive then we needn't immediately worry about chaos ensuing. Designing methods for 'cracking' individual NP problems might take an unreasonably long time (indeed, we've failed to do so for many basic ones so far e.g. factoring), so the impact would be limited.
if p = np is someday proven the prove itself will give way how the complex np problem becomes p. so ya the proof will be enough to cause the breakdown. what you suggested is if someone finds an example that would not break things. but example and proof are two different things.
damn i had to check my youtube speed cause i was SURE it was running at 1.5 speed ^^
haha, me too! ;) As a non native English, I couldn't follow him even on 0,75 speed, because he often cuts off half words. I just know, because many times his "talking" was inserted in written form as well.
Mitzos SirReal: Thanks for the idea. I found it much easier to follow at 0.75X normal. I'm a southerner.
:P compared to my aunt he speaks rather slow. Heck when she speaks Spanish the native speakers tell her to slow down.
Sounds normal on 0.75 haha
haha. I thought the same. even now I'm actually watching it in 1.5:p It becomes completely comical! :P
Finally someone using beamer for a maths-based presentation. LaTeX for life!
same here, doing them now with html5 never a powerpoint guy
.. only present total garbage!
@@paradigmnnf bruh what?
As an extra note: If you're looking for prime factors, then as you are testing whether a divisor is composite or not, the shortcut is that you have to test only up to the square root of the number you are factoring. e.g. SQR (100) = 10, which means to find all prime factors for 100, all you have to do is test the prime numbers between 2 and 10 (2, 3, 5, 7) And that's GAG (Good As Gold)
This is a great talk on many levels! If we are only talking about classical computers, then one way to stop computers from getting stuck in infinite loops is to have 3 (or more) computers. One to do the calculations now, one to do the calculation with a delay and at least one to watch for the signs of an infinite loop in the 1st one. If the 1st one goes into a loop it then tells the other calculating computer to stop.
cs.stackexchange.com/questions/32845/why-really-is-the-halting-problem-so-important
Best operational research lecture ever.. I had a course @university and had a crush on the topic but never had a chance to think to it in these terms. Amazing lecture.simple yet perfectly explaining examples. I'll suggest to collegues
It's funny, the description of how the computer doesn't "think" was to point out that Kasparov wouldn't exhaustively go through each potential next move in his mind, he would employ some intuition and other "thinking stuff", whereas the computer basically exhaustively goes through each move until it finds the next best one to play.
This is in fact not what the computer does. The whole point of computers playing chess is because of this fact. Chess has too large a search space to simply blast out a tree and collapse back on to the highest scoring leaf.
Yeah, I didn't think that was a very convincing argument either, and the distinction between proper thinking and running through all options isn't at all self-evident. Both Kasparov and the computer are obviously using shortcuts for efficiency, but the simplicity of chess's rules doesn't afford them a lot of leeway and they're basically evaluating the pertinence of potential moves in the same way.
I bit my tongue when he said the halting problem being intractable is "theoretical computer science" and was differentiating this from mathematics. Computability is part of mathematics.
Thanks for this Nice Lecture. Excellent Quality & Content
Those opening 5 minutes were the creepiest and most amazingly scary in all the Ri lectures I have seen :O
really good rundown of some big issues in the history of computational theory
Great speaker, very energetic which is what you need when dealing with complex and dry subjects.
IMO quite the opposite.
Speaking way to fast while running around means that after no more that 10min I stopped his ramblings and started to read the comments.
Going by the amount of dislikes I fancy others may also hold that view.
"dry subjects" ???
He seems to take a very limited view of what an algorithm is, suggests that we don't operate in quite that way, then concludes that computers can't think. Maybe he only means "computers as we have traditionally known them so far can't think", but I suspect he's going for a much stronger statement without giving an argument.
Yeah, was a bit lost on why he went down some AI theory. Humans are just a complex interaction of multiple programs.
Some of our base programs include: hunger, thirst, sex drive. If I am hungry, I will want to eat. If I am to eat, then I will eat food. This hunger program will interact with other programs, such as economic programs that might tell me to eat instant ramen instead of eating a 3-course meal at an expensive restaurant.
There is very little reason to believe AI won't exist. Of course it will, and it will eventually get so complex that we can't understand it. In fact, I think AI will get to a point of becoming an NP problem to try understanding, like we are.
I think the point he was trying to make was that computers are not capable of abstract thought or reasoning (yet) and thus can't be used to solve certain problems that would require such an ability rather than the brute force way of solving problems computers currently use. The good news is that quantum computers will be a reality soon and might be the answer.
Lord Voldemort in pijamas pants and fine costume explaining awesome things :D
Really enjoyed this. Thanks!
It was a very smooth journey from Killer Robots to P vs NP an millennium Price Problem 😁
Thank you so much. I think I finally understand how public key encryption works.
wondering why there are so many thumbs down? I love how many examples he was showing! I always wanted to put together these examples and it has been done in one lecture under one theme! thank you!
I went to check how many thumbs down there are unfortunately I do not have that luxury anymore
It's because, half the time, he's waffling on about his highly unvalided opinions as though it were fact. Already, 5 years later, his ideas seem increasingly wrong.
@@kylethompson1379 which ideas for example? I skipped some parts (atleast didn't listen properly) but I don't know which you mean?
First half of the talk: "If I define thinking as something only humans can do, I can then state authoritatively that computers can't do it. I will fail to mention that modern agents approximate more and more the methods (that we think) a human uses to think."
The second half of the talk is actually a pretty good description of complexity problems, but slightly lacking in that it doesn't mention the existence of EXP or greater problems.
In the Q&A video - Ri has uploaded it separately; do check it out - Prof. Buzzard answers questions on quantum computers, NP-hard problems, chaos theory and weather forecasting, cracking Bitcoin encryption etc.
After years of watching these, I just now tonight saw the final end card that declares these videos are released under a Creative Commons license. That is so, so cool. I ❤️ the RI
What that?
Calculations are numerically quantized identities of the connection process-properties of e-Pi-i interference states of infinity, so only the "surface" properties of any number combination of quanta is a "local" result, (slightly similar to the tip of the iceberg and relative melting proportionate multi-phase rates in air and water). Abstract mathematical calculations are speculative suggestions that require either the discovery of natural occurrences that are "ruled" by laws, or testing by naturally occurring components, as the problem has been explained.
Digital Computing is a process of finding the Central Limit of 1-0Duration, polynomial "fractal" convergence +/-. QM-Time is one Principle of analog logic.
Otherwise, the current expectations of the discovery methods will continue?
Still a great lecture...
Other than the opening few minutes of FUD, quite a wonderful, general-audience accessible to the idea of P=NP.
Trisecting can be achieved at the third order of the method shown. First half, second level one quart, third level on twelfth, every fourth intersection is one third of the angle.
Great! A wonderful lecture!
Run in a loop : abs(ln(n)) Start with n=2 & reinject the result in the formula & so on . Can you tell the value after a million step without running it ? Does it ever stop ? Does it repeat itself ?
If P=NP then it doesn't mean that we suddenly obtain a P algorithm for every NP problem. It only says that an algorithm must exist, not what it is, or how to find it, or that we will find it, or how long it will take to find it if we ultimately do. All it does is guarantee that we are not wasting our time by working on the problem.
If P!=NP, it does not mean that all problems currently thought to be NP have no P, only that *some* NP problems have no P. This would also not mean that all encryption algorithms are unbreakable or even that any currently used encryption algorithm is unbreakable. This is because a given encryption algorithm may rely on a problem that turns out to have a P algorithm even if there remain other problems that are NP and not P. Furthermore, even if the encryption algorithm relies on a problem that is not P, there could still be flaws in the algorithm that allow the asymmetry to be sidestepped. This is why encryption algorithms can be considered 'broken' even though they make use of NP problems for which there exists no known P. All it would say is that there *can* be unbreakable encryption algorithms, not that any given algorithm is unbreakable, or that any known algorithm is unbreakable, or how to find an unbreakable algorithm, or if we ever will find such an algorithm.
If P=NP then we actually *already have* a P algorithm for every NP problem. What it does is to iteratively try every other algorithm for not-too-long. If the other algorithm runs for too long, kill it and try another one. If the other algorithm gives an answer, check it for errors. If correct then we're done, otherwise start over with a different algorithm. If we've tried all algorithms, start over from the beginning with a little bit more time allowed.
Since the problem is in NP and P=NP, then some P algorithm exists, and our program will eventually try that algorithm out with enough time allowance, and it will give a correct answer. So as you can see, our "super-algorithm" isn't very clever and even though it runs in polynomial time, it's going to be a very big polynomial so it will still be extremely slow in practical terms. It's called Levin Search if you want to google more about it.
Im sure Turing's proof was rigorous and valid, and understand that maybe there wasn't time to delve into that detail, but I felt that the proof presented was poor. By definition, a program is bad if there is at least one input that will cause it to run an infinite loop. But this doesn't mean it always runs in infinite loops. Some inputs, maybe even and infinite number of inputs will cause the program to terminate after a finite number of calculations. My point is, K is a bad program, since inputing a good program causes it to go in an infinite loop. So when feeding K into itself, there is no contradiction, the output will be a termination after finite calculations. On this occasion, K did not end in an infinite loop, but its still a bad program because when it receives a good program, it will result in a loop. I just thought it was worth pointing out that this logic doesn't quite work.
This was the best introduction of this problem to a lay audience that I have ever seen.
This was an excellent talk.
I have a question regarding integer factorization: what about Shor's algorithm? Does it not prove that integer factorization can be solved in polynomial time? The way I understand it is that it can, we just have to overcome the technical (engineering) difficulties of building reliable quantum computer (unlike the prototypes we have now). Maybe I am missing something :)
I think your example about the K program is wrong or incomplete.
Considering that a program could be good or bad with different inputs(as evidenced by the program K itself), a program that determines if a program is good or bad would ALSO have to take in that programs inputs. So when you feed K into K, you'd also have to pass what you were passing to K, which if it had inputs(as K does) would also have to take the inputs into that function. So somewhere in the call stack there would either be missing parameters, or a scalar value.
I think the reason we can't write a program that perfectly checks other programs for bugs is because the input space is infinite, which means the method checking for infinite loops would always be an infinite loop itself.
If you limit it to programs that have no inputs(and would be valid single inputs for K) then I'm pretty sure you can build something that checks any code for bugs.
Thoughts are welcome if I've missed something obvious here...
What you've missed is that K doesn't take any input. Program Y takes input (another program X) and says whether X is good or bad.. K does the following: ask Y if K is good or bad, and depending on the answer, do the opposite - thus showing that the answer given by Y is wrong.
@@Grrblt I think you might have misunderstood something. K takes a program as input. As the quote in 33:09 states, it receives a program as input and behaves differently whether you input a good or a bad one.
The definition of "good" and "bad" seems to me like it's not specific enough in the video. You're right, if a program is good or bad is highly dependent on the input. If you define "bad" as crashing for any input, then K could just be a bad program, as K not crashing for the input K doesn't make it a good program. I think you're right, the proof might be incomplete.
The solution is to look at programs input into themselves. So you would have to make another program P that checks for any input X, If X input into itself would make it crash. Then P input into P cannot give a valid answer.
I can recommend this video:
ua-cam.com/video/92WHN-pAFCs/v-deo.html
@@Pascal6274 K itself doesn't take an arbitrary program. It only ever needs to know about program Y, and itself. Y is the one that takes an arbitrary other program. If Y works as claimed, it can answer the question "is program K (with no inputs) good or bad?"
That is the way this proof is *supposed* to work. If his slides claim differently then he has added unnecessary complexity and, I think, in this case actually broken the proof.
Before you watch, be aware that he mentions "polynomial time" in the 45. minute for the first time. :) However there he gives a pretty clear explanation for someone like me, who just wants to refresh his memories from the university after 16 years.
The many Halting problems can be solved with morphic code.
Prime Factorisation can be achieved very fast using multi modular arithmetic and the the floor of Triangle Number root.
As for an NP complete problem that can be solved via reduction by using multi dimensional asymmetric counting so a single number would be represented with 2 or more numbers which could in turn become the single number again so 1={1,1}, 2={1,2}, 3={2,1}, 4={1,3}, 5={2,2}, 6={3,1}, 7={1,4}, 8={2,3}, 9={3,2}....
Consequently the 2 output numbers could become 4 output numbers and those 4 numbers could become 8 output numbers and then you could take your 8 output numbers and go backwards to get your original number. You could even switch the pairs around going down to 8 numbers and and use another switching pattern to get you too another number where by you would need the key as to what switches had been made in order to know the original number this would be an symmetric method. To make such a form of asymmetric you simply embed standard RSA encryption into the step coding. Both the Symmetric and Asymmetric ciphers would be a EXP complete problems not anywhere near P time So even though P=NP it is still very possible to have both workable asymmetric and symmetric encryption that is very hard to decode.
This is amazing!!
Turing's conclusion that you cannot construct a computer program that will say whether any program will not get into an infinite loop is a lot like Russell's example of the set of all sets that are not elements of themselves. It seems to have the same basic structure. That set cannot exist, because if that set is in the set it is out, and if it's out of the set, it's in.
Regarding the beginning of the talk, and how computers cannot think, apparently he has never seen AlphaGo or AlphaGo Zero or anything else going on in modern machine learning.
what is not thinking ! man !
Yes, especially Kevin Buzzard.
AlphaGo doesn't really think. Artificial Neural networks are basically just a form of directed brute force at their core.
So is your own brain though.
@@Reddles37 I'm not convinced that is true, although you make a good point. In some ways it's like an infinitely fast computer that encompasses all human experience. But would a neural network be capable of concieving something outside human experience? Could it, for example, replace Einstein and Mozart and van Gogh? Write all those papers and all that music? Could it really lay claim to all that creativity? It's not as if they have an infinite amount of time. Let's say there are only 237 years before human extinction (an estimate based on unpublished data that is by definition inarguable). Could they do it by then?
I like it learned slot about computers that I didn't know.the difference between us and computers is that we can change our minds every millisecond.
For the program at 29:19, the answer I got was that if x
Quantum computing will finish the problem of the P vs NP !! next question please !!
excellent lecture.
1) Please forgive my limited understanding
2) Are entropy and the arrow of time physical clues for N not equal NP ?
49:08 After that long video of umms and ahhhs, volume shifts and pitch oscillations...This single moment was surreal.
Bisect the triangle.
measure a distance up each side of the angle , put a line across the two points , bisect this line and connect this point with the starting point . No need for the compasses at all ?
I think that is should be able to bisect the angle with just a ruler. make the angle, measure x amount of space up each edge of the angle, say 4 inches. Mark the ends of the 4 inches and draw a line between them. Measure the line between the marks, and you will come up with some length. divide the length in half and measure that much and add a dot at that point. Now draw a line from the base of the angle and the dot. Done... right?
i find it kinda scary but also really cool that we have to ask this question
Algorithm at ~29:25 gets stuck in a loop if x=10.
Also 5
If one looks at the history of self driving cars, at least the early iterations, it could be argued that they qualify as "killer robots". It's just that the killing part and the target part are pretty much random.
A killer robot forced him to wear those pants.
No one would volunteer to do that.
The angle trisection proof had me intrigued so I looked into it a bit more.
Turns out you CAN trisect an angle using nothing but a straight edge and a compass. Archimedes did it, but his method uses a mark on the ruler. You could put the compass next to the unmarked ruler to get the same result as a marked ruler. The 1837 proof relies on a imaginary nerf compass that collapses when lifted from the page and as such cannot measure distances.
An imaginary collapsing compass couldn't bisect an angle either, since you need to draw two circles the same size.
"Because it is defined in simple terms, but complex to prove unsolvable, the problem of angle trisection is a frequent subject of pseudomathematical attempts at solution by naive enthusiasts. These "solutions" often involve mistaken interpretations of the rules, or are simply incorrect." Wiki
Trisecting an angle using compass and ruler and without somehow cheating is impossible. The proof involves showing that the numbers/length you can construct with compass and ruler are combinations of +,-,*,/ and ✓. These numbers will be the root of a polynomial with integral coefficients of degree a power of two. If you could trisect an angle, you could construct the third root of two with ruler and compass, which is a root of x^3-2, which is a polynomial of degree 3. So this is not possible.
I wish I could have understood more than 30% of what he said.
Wonderful lecture! I would like to raise two questions here:
1) To succeed in proving P equals NP does not equal the success in finding the polynomial solution for a formerly NP problem, is that correct? In plain words, even if I can prove P equals NP today, it doesn't mean that a cancer curable medicine will be available tomorrow, right?
2) Can Americans understand this London English in throat cutting speed without any difficulty? I am a non-native English speaker and basically can only understand
Is this question is about whether or not some problems scale too quickly to be solved in a reasonable amount of time (a never-ending computing power deficiency), or whether or not we can find lesser-scaling methods of solving the problems? Or is it both?
Upon looking a bit deeper you can realize that these are the same problem
To find a definitive answer to the question does P=NP. One must first understand the limitations of the system in question. In the case of computers, current technology has its limitations but future technology may have different capabilities and limitations, perhaps less, which then changes the equation but not necessarily changing the answer. Regardless, we must ask the question and find the answer to know for sure.
P=NP is a purely theoretical problem defined by Turing Machines. It has nothing to do with our current state of technology.
Computers can become more human-like when programmed to stop algorithms given a certain number of trials or errors, or to apply probabilities to multiple processes that computer then shuffles to select to minimize run time based on lots of IF Then analysis...and then can be artificially effective like a non bot
I have seen people get stuck in thought loops...
Friend of mine took too much LCD and just kept repeating the same thought process for hours. It was terrifying... to realize we are just biological computer programs
That's why I recommend OLED, it provides way better psychedelic experience
Makeshift Altruist LCD?????
@@KatKevaKelise MN....@0
Your friend should try an e-ink panel next time
Maybe you were the one stuck in a loop. How can we tell.
do not understand the mathemtics but am aware of the implications. got ample words for it.
There are a couple of mistakes in this lectures. An example is at about 1:00:10, "guaranteed cannot be solved quickly". This is not true. If P=NP than there definitely exists a way that the problem can be solved quickly. If P not equal to NP than that doesn't rule out the existence of such a solution, we just cannot be sure. His slides include the word "probably" but that is not how he said it.
You cannot trisect an arbitrary angle however trisection of a sixty degree angle with a compass and a ruler may be possible.
Take an angle of 180° and construct three adjacent sixty degree angles.
Does multiplication increase the entropy of the universe and factorisation reduce it?
And then there are the problems for which you can prove that it's impossible to prove them.
Also, even if you found some random problem in NP that is not in P, that doesn't mean internet security is safe.
It seems to me that it would be easy to invent a computer controlled armored machine that kills everything. The difficult thing would be trying to get it to make decisions on who to kill and who to leave alone. Too many variables. (i.e. Self driving cars that can handle every scenario is a similar problem)
Such passion.
:)
Boston Dynamics "Big Dog" is designed to be a robotic pack animal, not to kill things. It's no more a killer than a burro.
It's just a question of time until someone puts a grenade launcher on it.
Amazing talk. Kevin Buzzard is the boss!
Boston Dynamics were designing and building amechanised Sgt Reckless. Its purposuse is to carry heavy,
ammunition, food, water, mortars, mortar rounds and other materiel over terrain. Not really a killer. You showed an RC version which can hardly be called a robot.
around 50:00 Yes, computers cannot solve EVERY problem, but for the class of problems that can be solved by computers, they work well enough for use as a tool to solve those problems and save true consciousness to focus on other aspects of the higher dimensional problem.
29:19 :
1. Set x to user input
2. If x == 10 then crash, else go to step 3
3. If x < 100 then go to step 4, else go to step 6
4. Double x
5. Go to step 2
6. Print "hello"
7. Exit
This means that if you input 10, 5, 2.5, 1.25, ... Then it'll crash, otherwise it'll reach 100 and exit
Don't forget about zero and negative numbers as inputs. These will cause an infinite loop as x remains at zero or gets progressively smaller in value. (i.e., 0*2=0, -n*2=-2n)
this guy propably was behind that one black mirror ep with the boston dynamics killer robots
A 4 GHz processor does not process 4 billion instructions per second. You need to look into the CPI and do the maths.
Great vid!
It's quite confusing for regular people to claim that's it's "what computers can't do".
It's more general than that, it's about the limits of computing and logical processes, it also applies to humans which in technical terms are also computers (as in, we compute data).
Also every cell in your body is a turing machine as well
@@phizzhead53 no?
What do you imagine inputs and outputs to cells are?
If you can't tell if you are interacting with a computer. Then whatever the computer IS doing. Produces the same results. Much ado about nothing.
Question: If we could prove that P=NP, why does that imply that all the 'difficult problems' would be suddenly become 'easy'?
We would still have to discover what the solution was to each difficult problem.
For example. if P=NP, then factoring large numbers could be done in Polynomial time. We wouldn't know how to do it, but we would know that we COULD do it, if we discovered the correct method.
Addiction is evidence that human thought can proceed rationally and get caught in a loop, awareness of the loop isn't the problem. A computer isn't told not to get caught in a loop. Compilers and runtimes can preempt complex recursive traps, in the same way people do, and in fact are better at it. Time constraints employ a heuristic, if people write one into a program it's seen as a patch or hack, when ironically this is an example of human thought management
Proving that P = NP represents the computational (and socioeconomic) equivalent of vacuum decay in physics: catastrophic and irreversible disassembly. So, we are able to know that there exists a possible state of meta-mathematical knowledge in which a proof indicates the hard end of secure online transactions, encryption and unproblematic personal privacy assurance, or it does not. There would be good things, certainly, but only at a cost of extinguishing the computationally-facilitated financial, security and privacy systems (such as they are) that currently exist.
There is a one million dollar prize up for grabs in this space. Personally, and given these high stakes, I think it is probably worth much more than a million dollars for someone NOT to find a solution but, just as with the intial testing of hydrogen bombs and the fact that it was unknown if they might generate an accelerating chain reaction that incinerated the entire atmosphere of our planet, caution is generally not the first consideration in matters of curious invention.
Oh ! poor camera operators following this guy arround the stage for one hour...
If P=NP - does it mean L=NL?
If L=NL - does it mean P=NP?
Does solving one of these 2 problems leading to solve the other one?
Do they have same kind of decision algorithm?
On the video it is suggested that Deep Blue was brute forcingly going through even "silly" configurations in its search, but that would have been a gross understatement and a harsh insult against the Deep Blue engineering team. Reality was very far on the contrary - Deep Blue software was running the most sophisticated levels of chess search algorithms at the time, which certainly did not spend time looking at silly configurations. Of course even the fact that Deep Blue used an efficient and well researched chess search algorithm does not dispute or alter the point that the lecturer was making about the question whether the computer was "thinking" or not.
An infinite loop is not a crash, a crash happens when the computer program cannot continue. Having accidentaly written infinite loops into programs that ran for over 6 days and only stopped because the operators needed to shut the machine down for weekly maintenance I can guarantee an infinite loop is NOT a crash.
34:15 what about all the programming consoles and IDEs that tell you "error, infinite loop". How do they know that?
You can find if some subset of programs will halt or not. But you can not do that for ALL possible programs.
Wait, I found a way to trisect an angle with a ruler and a compass. I haven’t been able to probe it, but it works somehow.
Angle ABC is given. Draw Circle DB with D being on one of the angle’s sides. Mark E where the Circle DB intersect the other side of the angle. Construct equilateral triangle DEF with F being farther away from B than D or E. Find the midpoints of DF and EF, and label these G and H, respectively. Draw GB and HB and, voila, trisected angle. If you do all this properly, you get three equal angles, all which can be physically measured to be exactly 1/3 of the original angle, but you should leave appropriate room for error unless you did every step perfectly. If anyone can somehow disprove it, I’d be very happy to hear, and if anyone can prove it I’d be happier. This only works with angles 180 degrees or less, though. If you want up to 360, you can bisect that angle and complete the proof on the two new angles, and take the trisecting lines which would be most applicable because I can find no better way of describing them
Accurate to the math but also fairly intelligible, which is a hard balance to set. Nice!
It's not that it's always difficult to solve an NP problem. There are methods that solve them quickly. The problem is that these methods don't work quickly on all inputs. If on some input it takes long to find a solution, you have no way to know if a solution doesn't exist, or it just will take a hundred years of calculations. However, many practical NP problems can be solved quickly, or sometimes a slightly suboptimal solution is fine.
1. Atanasoff & Berry constructed and operated the FIRST electronic digital computer at Iowa State University from 1939-1942.
Nobody was interested in the least.
2. Turing's proof that the "Halting Problem" was impossible to solve has this (not too obvious corollary): It is impossible to predict the result of an algorithm (computer program) without actually running the program. If this is not clear to you, think about it for a few minutes and it will suddenly clarify itself.
3. Programs that can run in Polynomial Time may sound like they are computable IN PRACTICE, but this is not really true. Example: Suppose that a program with N (at least 10) as an input runs in N^(9999) time [N to the power 9999] then it will prove to be insoluble in practice since 10^(9999) Planck time units is far longer than the lifetime of the Universe so far. In the real world, depending upon the program, a program that runs in Linear time (power 1) is nearly always (with obvious exceptions) able to finish, while a program that runs in Polynomial Time where the degree of the polynomial is larger than 10 or so, will never get done. From a PRACTICAL point of view, a program that runs in Polynomial Time may very well be intractable, even when the degree of the polynomial is fairly small.
"It is impossible to predict the result of an algorithm (computer program) without actually running the program."
I would argue that this statement only holds for a subset of algorithms.
Take an algorithm that takes an input as counter for a loop and adds one to a variable (starting at 0) on every loop. At the end it prints the variable.
You don't need to run through all the loops to predict the result.
Steven Wolframs idea of irreducible complexity comes to mind here. I would guess your statement holds only true for algorithms with that property.
@@fromvoid3764 I should have written:
"It is impossible to predict the result of an ARBITRARY algorithm (computer program) without actually running the program."
Sure, trivial programs such as STOP can be predicted. What is impossible is to predict the results of an ARBITRARY program without actually performing the calculations. Only an infinitesimal fraction of algorithms can be predicted. The rest, 99.9999999999999999999...% cannot be predicted.
yeah, there are many algorithms that according to complexity theory are the best but nonetheless are never used in practice because they are only better than other algorithms for extremely large n.
Also the distinction between polynomial and non-polynomial is too crude for being useful in practice, in real life something that runs in O(n^3) or O(n^4) is already close to being useless.
@@aufdermitte7143
A fact conveniently ignored by theorists.
The analytical engine was not built by Babbage because the accuracy required for the engineering of the components was beyond the limits of the time. It was built by a university team in the 20th century.
how they even find such a great speakers...
@41:29
The expanded version of program 2 has a bug!
No it doesn't. Assuming you typed in "53" initially like he did in the talk, the computer would print a 0, and then x would decrease by 1 (to 52 in this case). This would keep happening over and over again *until* x=1. At this point, after printing a 0, x would be decreased to zero. Because zero is not less than zero, the program would finish instead of going back to step three. This kind of function is called a loop. Loops in computer programming are fine. Infinite loops however, are not.
@@HotCrossJuns Yes it does instead. Try putting in 0. The program prints a 0, when it shouldn't have printed any. Teh correct formulation would be: while (x-- > 0) { print("0") }
HOw many times do we have to hear this same thing - computers can't (fill in blank). I can vividly recall earnest claims that computers could never do - get smaller, go faster, win at various games, drive a car, give diagnoses, fly planes, we will never have a gig of memory, learn handwriting, translate in real time,..... They may not have emotions but they can sense them. They may not care if you live or die but they can offer counsel. They may have no musical preference but they learn yours.
This is different though. This is about a fundamental law of nature rather than what our current technology is capable of.
Twenty ago, it would not have been unreasonable to believe that it was "impossible" for a car to move faster than the speed of sound - but now, of course, the Bloodhound project, with state-of-the-art technology, is aiming to smash that barrier and it looks quite plausible.
However, you can pretty confidently say that a car will never travel faster than the speed of *light*. No matter how advanced our technology gets, we will never be able to do that.
That last part about the light may not be true. ua-cam.com/video/94ed4v_T6YM/v-deo.html
Actually, if any of the 10 billion or the farthest galaxies have civilizations with cars they are moving faster than light. (OK , they are creating space-time where the rules don't apply - LOL) A history of science is a warning about making emphatic "that's impossible" statements. Just 150 years ago the idea of safe, cheap water on tap, abundant food, free entertainment 24/7, quick travel anywhere on Earth, free visual chat with anyone on the planet you would have been considered insane.
I should have said that it is intellectually dishonest to declare something impossible based on current technology. Our history is replete with claims broken and forgotten - PCs, anesthesia, vaccines, planes, tv, radio, electric, steam, nuclear, solar power, the human genome. Experts declared all these "impossible" but we quickly forget the invalid forecasts when they become part of everyday life.