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.
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.
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.
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?
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.
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.
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.
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)
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.
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.
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 :).
@@Trage339 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)
@@Trage339 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.
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.
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)
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.
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.
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.
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.
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!
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.
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.
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.
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.
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 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).
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
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
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.
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
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.
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.
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.
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.
@@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?
This was 2017 ? His cosmology is a few years out of date. Current understanding is the geometry of the universe is flat and expanding exponentially (WMAP etc.) suggesting it will continue to expand and not slow, stop and contract.
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.
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.
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.
He ignored a lot of modern advances in AI; never really qualified his opinion that computers can't think in a meaningful way, either. Yes the first ever algorithms used to win games used brute force, but even by Deep Blue that was changing (chess having too large a branching factor to brute force) and nowadays we have Alpha Go which performs phenomenally well in Go which has an obscene branching factor so it is definitely doing some kind of thinking akin to humans. Plus he did admit near the start that dangerous autonomous robots are possible with current technology, ignoring the whole thinking part. Then also pointed out we can never prove a program has no bugs, so even without an AI choosing to be harmful for a reason we'd consider "human" it could choose to do something harmful!
AI is dangerous in the same way a car is, or a dam, or a hammer or a fist. The difference being, AI can be let go, a loooooong way away, then the end result happens. Where as most cars only roll down a hill when the breaks are left off.
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.
There are 9.3326 x 10^157 ways of arranging 100 atoms. State space is unimaginably large and effectively infinite and using it for computation and storage will open completely new universes.
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.
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?
Strictly speaking his definition of NP is incorrect or incomplete. A problem is in NP when a (N)ondeterministic computer can find the answer in (P)olynomial time. I believe it's an engineering problem to devise a challenge for which exponential parallelism grants a demonstrable advantage.
I am pretty sure P v. NP is literally just that: the time growth rate it takes to solve a problem >> the time growth rate it takes to check if a problem was solved; meaning the number of steps scales based on the number of inputs in a non-polynomial fashion. His examples are spot on from my understanding of the math. The polynomial time equation was the actual, literal definition of P. If the problem could be solved in P(n) = n^(10^10^10^10^10) + 10^80^80 steps, then it is still a polynomial time even though the computer will never (in reality) be capable of solving it before the universe ends. But NP(n) = 10^n steps is an NP problem. If n is 1, a computer could easily solve the problem. It would take 10 steps. But as n grows, the number of steps don't grow by a power, they grow exponentially. Such is the case with the travelling salesman problem. The shortest distance between many points can be checked by a computer for like 100 points. But every time you add a new point, the computer has to check many, many, many more new possible paths to determine the shortest one. Strictly speaking, his "consequences" of solving the problem was wrong. It doesn't mean that we can find a solution that can be done "quickly", it just means we can find a solution that takes polynomial time rather than non-polynomial time. That polynomial time solution could still take the end of the universe to find, it just won't be in non-polynomial time anymore.
Connor Skudlarek By the way trisecting an angle with a compose and a ruler is just a 12 step problem and is absolutely possible!! Np problems only exist in infinite systems. Any problem in a finite system has a p solution.
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.
A problem with this logic is that Kasparov doesn't have intuition, he has memory of past failure. New players don't have intuition, because they haven't stored memories of previous similar situations and bad responses to them.
Intuition can come from experiences other than playing chess though. You can bring experience from poker to chess, and that is called intuition. You have no experience with this situation (chess), but you have other experiences. Someone might be bluffing with a move, and your intuition (not your experience with chess) might be telling you that the move they just made isn't an aggressive move but a defensive one trying to trick you. Intuition really is an instinctive ability to recognize something, rather than relying on rationality to recognize something. I am sure, even the most advanced chess player, still plays with their gut every so often.
When I got to the end of this I saw that it was a bit long, I hope you find it worth your time and consideration. In so far as there is symmetry between the rules of different games, situations, or systems, strategies can be applied laterally with a degree of success depending on the degree of symmetry. You gave one example, a more general one is the attitude of Winston Churchill. In his early days he flew planes that could only maintain their height by going against the wind. He applied this experience to his life's philosophy, in 'always moving against resistance'. The challenges of the world are sufficiently diverse that the ability to do this has probably proved to have significant survival value. We seek the lesson, the abstracted principle that can be applied elsewhere, and sometimes we find them. Kasparov's memories of past failure may not be restricted solely to chess, but until he has experience in chess, he can not identify symmetries between those experiences and chess. He can't yet apply the abstracted principles he has picked up elsewhere. Once he can begin finding symmetries, which takes a kernel of experience, he can access and benefit from broader experiences of failure. The feeling you get when you 'go with your gut' is a calculation your brain makes, you just can't inspect how it is making it, but you couldn't inspect how your brain adds 2+2 either. The explanation you give for "why" is just a matter of articulation that happens after your brain has already done the work you weren't able to watch. You can't watch how you articulate that very precisely either, even though its something your consciousness plays a bigger role in moving through the steps of. I think this distinction about intuition (and its often vague meaning) is important, because to do otherwise sets our expectations up for failure. I think many people want some reason to believe that we contain something innately valuable, not just to each other, but to the world objectively (and I don't deny the existence of objectivity, either). If that belief is dependent on something we are calling intuition, we may be disappointed when systems are developed which can identify symmetries between different systems and situations. The Go computer, the Chess computer, may then be able to draw from those simplified experiences in its search for battle field tactics, medical diagnosis, or engineering. Then we'll just have to ask ourselves what we are good for all over again.
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.
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...
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 ?
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.
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)
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?
A few things about this talk bugged me. 1.) Going on about encryption. I felt this didn't need much detail. People can read up on asymmetric key cryptography in their own time. All we needed to know was that it uses factoring which is an example of a problem that scales non-polynomially with time as the digits increase. 2.) Turing's conclusion. The conclusion written on the screen was legitimate. But what he says immediately after isn't. The keywords in Turing's conclusion in the Halting Problem is "any and every", but Kevin says "this is why your computer programs crash; they can't find bugs". Which is false. 3.) P vs NP slippery slope. What supersedes the proof that P is or isn't NP was over-dramatized. Proving it either way isn't the ultimate proof; it doesn't just unlock all other proofs for free. The only extra ability you have is in proving that a proof does or does not exist.
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.
But you could trisect by making half angles 3 times. That'll be messy and hard but can be done by compass and ruler just use a large angle and different colors and it'll make sense. For small angles, you'd have to be very careful. Even the half angle can be very tricky for small angles!
No you can't. You half the original angle, then if you half the halves you get quarters. If you half those you get eighths. 2 * 1/8 = 1/4 and 2 * 1/4 = 1/2. You never get 1/3, only 1/(2^n). You could combine these to get 3/8, 5/16, 11/32 and so on, getting close and closer to 1/3, but you never actually get there
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.
"On 8 June 2017, Alphabet Inc. announced the sale of Boston Dynamics to Japan's SoftBank Group for an undisclosed sum." So Google does not have any "killer robots".
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.
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
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.
49:08 After that long video of umms and ahhhs, volume shifts and pitch oscillations...This single moment was surreal.
3 роки тому
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
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.
So what you're basically saying is that a computer or respectively a robot won't kill a human unless it is instructed to. That's what we should worry about.
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 ?
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.
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.
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.
I do not understand people who claim "computers can never think". What are humans but trained, weighted and backpropagated neural nets? If computers can not think, than what are our own neurons doing so differently? ML is currently disjointed in specializations, and at simpler mammal levels of intelligence. It's only thinking in the same way the visual cortex or the memory of a dolphin "thinks". But artificial brains are being pieced together, neural nets are now often joining together for more and more complex tasks.
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.
Google might not have killer robots, but it has AlphaZero. So most of that talk about Kasparov vs. Deep Blue was just obsolete a year later (i.e. in 2018), when that evolution of computers in chess reached a level beyond human comprehension.
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?
Neural network systems learn from experience. If they have enough memory and enough examples of what the programmer wants them to do (carefully trimming out things that the programmer does not want the computer to do, of course, during this learning process), then a neural network system can learn to do ANYTHING!!! It may not be "thinking", but the results will be identical when the program is connected to actual hardware allowing it to do the job. It can also learn from experience while "on the job", though this may be slow at least initially, but "learning how to learn from experience" is also something that can be trained, isn't it? In the end, the "Killer Robot" would be like The Terminator or more probably some other, smaller and faster and harder to detect design optimized to be able to find and kill somebody with minimum chance of being stopped.
32:18 The mistake is *not* that such a program cannot be constructed. The mistake is that the *Turing machine* itself cannot be constructed because the concept of "infinity" is meaningless nonsense. Change "loops forever" to "loops L times, for some very very large L". Then you see the problem of determining whether or not a program loops "forever" is *not* impossible. L could, for all practical purposes, be "forever". For example, L could be Graham's number. Sure, it is non-deterministic, but you have not proven that the outcome cannot be determined. Indeed, if P=NP, and there exist efficient low-coefficient polynomial time algorithms for solving NP-complete problems, then it is entirely possible that I can statically analyze your program and tell you whether or not the program will halt.
You could check whether a program would loop forever though. Any time a computer program similar to those given would repeat any step without altering the values that were previously stored in memory when performing that step, then the program can be identified as one that would loop indefinitely.
Let's see, on one hand: prize-winning, former senior wrangler, professor of mathematics at one of the leading British universities; on the other: random UA-camr. You must be right.
Well, you seem quick to appeal to authority. You do understand that is a common argument fallacy, I trust. The problem here is a failure of logic, not of mathematics. What we have here is someone looking at a problem as a purely math problem and misapplying mathematical concepts rather than looking at it like a philosophy or engineering problem and finding the work-around. The simply fact that we can write a program that should logically loop "forever" (or at least until the power and circuitry gives out) means that we know what elements go into such a program and we could then create a program that could check another program and identify whether those elements exist. And, in fact, plenty of programs for creating computer programming already have such things built-in. If you try to write an infinite loop program like described in this video in most common, consumer coding software, and then try testing it within that software-- instead of permanently locking your computer until you have to reset it, the program will be quite nice to tell you that there is an error and the program will indicate to you that this program would result in an infinite loop. Since such programs do exist, it is quite clear that such programs can exist-- and his claim that no such program could possibly be written is proved wrong because, well... the very thing he claims can't exist does exist.
TheHobgoblyn TheHobgoblyn The fact there exist programs that can show that SOME programs will or will not stop does not show that there can exist a program that can determine whether ANY GIVEN program will halt. An analogy is angle trisection with compass and straightedge. It provably cannot be done for an arbitrary angle but is easy for a right angle. I want to be clear on what you mean by stating that a Turing machine can’t be constructed, they have been constructed. Presumably, you are referring to the physical impossibility of an infinitely long tape. While this is true, it’s not relevant to the proof of the Halting Problem. You claim that infinity is a ridiculous concept. I will acknowledge that there is no problem with analysis of mathematical structures that don’t include infinity, constructivists would agree. But a logically coherent (as far as we know, ht to Kurt Godel) system that includes infinities is equally valid.
You can determine if a program will continue infinitely without accomplishing anything so long as you don't entertain purely imaginary concepts such as a program of infinite length. But there are a finite reasons a program of finite length would loop endlessly without accomplishing anything. And a program can and has been built that can check if any of those finite conditions exist within the program. I can only think of a single possibility that you could not write a program that would be able to check if the program would loop endlessly... and that is if the program was set to do a series of calculations that do never repeat and will only stop once it reaches a particular answer, but the answer cannot be reached through the calculation. Only in such a case could a program not actually know whether or not the program will loop infinitely without actually doing the infinite calculation. And even then it would have to be an infinite calculation that is unknown-- because a detection program can probably detect that one is trying to calculate to the last digit of pi or root 2 or other known irrational numbers and stop the program and report this program would continue indefinitely.
For those looking for an instant answer; understand that this very lecture is an example of the subject of the lecture itself. Mr. Buzzard is attempting to prove something he proved is impossible to prove at the beginning of the talk. You can prove the validity of his statements in the lecture ("P"), but the analysis of what a computer can not do would take an infinite amount of time to compute and definitively prove ("NP") ... so the lecture proves that the lecture is impossible to prove. The only thing that prevents Mr. Buzzard from looping endlessly is the timer on the desk - a real world equivalent to a computer program's "time out" error trap.
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.
The Royal institution has survived men in powdered wigs and tights. I'm sure it will survive this non-fashion statement.
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
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!
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?
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?
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.
16:48
problems reviewed in class: bisect an angle
problems on the test: trisect an angle
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
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)
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 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.
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 :).
@@Trage339 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)
@@Trage339 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.
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.
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)
Thanks to the RI and Prof. Kevin Buzzard for a fast show intro into what's computable and what may not be. Brilliant!
Lord Voldemort in pijamas pants and fine costume explaining awesome things :D
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.
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.
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.
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.
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?
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.
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
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.
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
Those opening 5 minutes were the creepiest and most amazingly scary in all the Ri lectures I have seen :O
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.
It was a very smooth journey from Killer Robots to P vs NP an millennium Price Problem 😁
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
A 4 GHz processor does not process 4 billion instructions per second. You need to look into the CPI and do the maths.
Other than the opening few minutes of FUD, quite a wonderful, general-audience accessible to the idea of P=NP.
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?
A killer robot forced him to wear those pants.
No one would volunteer to do that.
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.
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.
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.
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.
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.
Algorithm at ~29:25 gets stuck in a loop if x=10.
Also 5
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?
This was 2017 ? His cosmology is a few years out of date. Current understanding is the geometry of the universe is flat and expanding exponentially (WMAP etc.) suggesting it will continue to expand and not slow, stop and contract.
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.
I wish I could have understood more than 30% of what he said.
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.
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.
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" ???
Them pants tho😁
Juras Kumar The contrast between his pants and the historical Ri lecture hall.
malporveresto True that. Nice talk tho. Kinda goes against the dangerous AI narrative
Anti Killer Robot Pants. ;)
He ignored a lot of modern advances in AI; never really qualified his opinion that computers can't think in a meaningful way, either.
Yes the first ever algorithms used to win games used brute force, but even by Deep Blue that was changing (chess having too large a branching factor to brute force) and nowadays we have Alpha Go which performs phenomenally well in Go which has an obscene branching factor so it is definitely doing some kind of thinking akin to humans.
Plus he did admit near the start that dangerous autonomous robots are possible with current technology, ignoring the whole thinking part. Then also pointed out we can never prove a program has no bugs, so even without an AI choosing to be harmful for a reason we'd consider "human" it could choose to do something harmful!
AI is dangerous in the same way a car is, or a dam, or a hammer or a fist. The difference being, AI can be let go, a loooooong way away, then the end result happens. Where as most cars only roll down a hill when the breaks are left off.
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.
A computer cannot speak that fast.
Oh ! poor camera operators following this guy arround the stage for one hour...
Mr. Buzzard is trying to show that you can also prove things by talking about them very very quickly.
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.
There are 9.3326 x 10^157 ways of arranging 100 atoms. State space is unimaginably large and effectively infinite and using it for computation and storage will open completely new universes.
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.
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?
Those robots aren't killer robots... they are mostly designed to assist troops by bringing them supplies.
Strictly speaking his definition of NP is incorrect or incomplete. A problem is in NP when a (N)ondeterministic computer can find the answer in (P)olynomial time. I believe it's an engineering problem to devise a challenge for which exponential parallelism grants a demonstrable advantage.
It takes time to calculate an answer. It is fast to see if that answer is correct.
Strictly speaking, a lot of his definitions were incorrect or incomplete. Considering his target autience, however, I wouldn't call them wrong.
I am pretty sure P v. NP is literally just that: the time growth rate it takes to solve a problem >> the time growth rate it takes to check if a problem was solved; meaning the number of steps scales based on the number of inputs in a non-polynomial fashion.
His examples are spot on from my understanding of the math. The polynomial time equation was the actual, literal definition of P. If the problem could be solved in P(n) = n^(10^10^10^10^10) + 10^80^80 steps, then it is still a polynomial time even though the computer will never (in reality) be capable of solving it before the universe ends.
But NP(n) = 10^n steps is an NP problem. If n is 1, a computer could easily solve the problem. It would take 10 steps. But as n grows, the number of steps don't grow by a power, they grow exponentially. Such is the case with the travelling salesman problem. The shortest distance between many points can be checked by a computer for like 100 points. But every time you add a new point, the computer has to check many, many, many more new possible paths to determine the shortest one.
Strictly speaking, his "consequences" of solving the problem was wrong. It doesn't mean that we can find a solution that can be done "quickly", it just means we can find a solution that takes polynomial time rather than non-polynomial time. That polynomial time solution could still take the end of the universe to find, it just won't be in non-polynomial time anymore.
Connor Skudlarek
By the way trisecting an angle with a compose and a ruler is just a 12 step problem and is absolutely possible!!
Np problems only exist in infinite systems. Any problem in a finite system has a p solution.
You are wrong on both counts. Even on a finite system with N elements, there are 2^N - 1 states and you might have to run through all of them.
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.
A problem with this logic is that Kasparov doesn't have intuition, he has memory of past failure. New players don't have intuition, because they haven't stored memories of previous similar situations and bad responses to them.
Intuition can come from experiences other than playing chess though. You can bring experience from poker to chess, and that is called intuition. You have no experience with this situation (chess), but you have other experiences. Someone might be bluffing with a move, and your intuition (not your experience with chess) might be telling you that the move they just made isn't an aggressive move but a defensive one trying to trick you.
Intuition really is an instinctive ability to recognize something, rather than relying on rationality to recognize something. I am sure, even the most advanced chess player, still plays with their gut every so often.
When I got to the end of this I saw that it was a bit long, I hope you find it worth your time and consideration.
In so far as there is symmetry between the rules of different games, situations, or systems, strategies can be applied laterally with a degree of success depending on the degree of symmetry. You gave one example, a more general one is the attitude of Winston Churchill. In his early days he flew planes that could only maintain their height by going against the wind. He applied this experience to his life's philosophy, in 'always moving against resistance'. The challenges of the world are sufficiently diverse that the ability to do this has probably proved to have significant survival value. We seek the lesson, the abstracted principle that can be applied elsewhere, and sometimes we find them.
Kasparov's memories of past failure may not be restricted solely to chess, but until he has experience in chess, he can not identify symmetries between those experiences and chess. He can't yet apply the abstracted principles he has picked up elsewhere. Once he can begin finding symmetries, which takes a kernel of experience, he can access and benefit from broader experiences of failure.
The feeling you get when you 'go with your gut' is a calculation your brain makes, you just can't inspect how it is making it, but you couldn't inspect how your brain adds 2+2 either. The explanation you give for "why" is just a matter of articulation that happens after your brain has already done the work you weren't able to watch. You can't watch how you articulate that very precisely either, even though its something your consciousness plays a bigger role in moving through the steps of.
I think this distinction about intuition (and its often vague meaning) is important, because to do otherwise sets our expectations up for failure. I think many people want some reason to believe that we contain something innately valuable, not just to each other, but to the world objectively (and I don't deny the existence of objectivity, either). If that belief is dependent on something we are calling intuition, we may be disappointed when systems are developed which can identify symmetries between different systems and situations. The Go computer, the Chess computer, may then be able to draw from those simplified experiences in its search for battle field tactics, medical diagnosis, or engineering. Then we'll just have to ask ourselves what we are good for all over again.
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.
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...
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 ?
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.
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)
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?
A few things about this talk bugged me.
1.) Going on about encryption.
I felt this didn't need much detail. People can read up on asymmetric key cryptography in their own time. All we needed to know was that it uses factoring which is an example of a problem that scales non-polynomially with time as the digits increase.
2.) Turing's conclusion.
The conclusion written on the screen was legitimate. But what he says immediately after isn't. The keywords in Turing's conclusion in the Halting Problem is "any and every", but Kevin says "this is why your computer programs crash; they can't find bugs". Which is false.
3.) P vs NP slippery slope.
What supersedes the proof that P is or isn't NP was over-dramatized. Proving it either way isn't the ultimate proof; it doesn't just unlock all other proofs for free. The only extra ability you have is in proving that a proof does or does not exist.
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.
This was the best introduction of this problem to a lay audience that I have ever seen.
But you could trisect by making half angles 3 times. That'll be messy and hard but can be done by compass and ruler just use a large angle and different colors and it'll make sense. For small angles, you'd have to be very careful. Even the half angle can be very tricky for small angles!
No you can't. You half the original angle, then if you half the halves you get quarters. If you half those you get eighths. 2 * 1/8 = 1/4 and 2 * 1/4 = 1/2. You never get 1/3, only 1/(2^n). You could combine these to get 3/8, 5/16, 11/32 and so on, getting close and closer to 1/3, but you never actually get there
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.
"On 8 June 2017, Alphabet Inc. announced the sale of Boston Dynamics to Japan's SoftBank Group for an undisclosed sum." So Google does not have any "killer robots".
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.
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
This was about 10 minutes of material stretched into an hour.
what? I think its the other way around . He compressed a multi hour lecture into a single hour, didnt you see how fast he talked?
the distance is always "the length from the pencil tip to the spiky bit." words to live by
Whenever someone say "well a computer can't do this!" it usually doesn't take long before someone makes a computer do it. This won't be an exception.
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.
49:08 After that long video of umms and ahhhs, volume shifts and pitch oscillations...This single moment was surreal.
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
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.
His description of how chess engines work was totally without any background knowledge.
So what you're basically saying is that a computer or respectively a robot won't kill a human unless it is instructed to. That's what we should worry about.
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 ?
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.
Drinking game, each time he walks around the table..... Take a shot.
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.
I do not understand people who claim "computers can never think". What are humans but trained, weighted and backpropagated neural nets? If computers can not think, than what are our own neurons doing so differently? ML is currently disjointed in specializations, and at simpler mammal levels of intelligence. It's only thinking in the same way the visual cortex or the memory of a dolphin "thinks". But artificial brains are being pieced together, neural nets are now often joining together for more and more complex tasks.
"We do not know." is a very unsatisfying answer.
Science "do not know" things more than "we know". Thats beauty of science. There are a lot of things to figure out.
"Better the Devil you know", then.
It could take too long to be a successful scientist.
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.
Quantum computing will finish the problem of the P vs NP !! next question please !!
Am I the only one who still wants the "last 2 slides" with jokes?
Google might not have killer robots, but it has AlphaZero. So most of that talk about Kasparov vs. Deep Blue was just obsolete a year later (i.e. in 2018), when that evolution of computers in chess reached a level beyond human comprehension.
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.
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
Neural network systems learn from experience. If they have enough memory and enough examples of what the programmer wants them to do (carefully trimming out things that the programmer does not want the computer to do, of course, during this learning process), then a neural network system can learn to do ANYTHING!!! It may not be "thinking", but the results will be identical when the program is connected to actual hardware allowing it to do the job. It can also learn from experience while "on the job", though this may be slow at least initially, but "learning how to learn from experience" is also something that can be trained, isn't it? In the end, the "Killer Robot" would be like The Terminator or more probably some other, smaller and faster and harder to detect design optimized to be able to find and kill somebody with minimum chance of being stopped.
At the moment no one has been able to train a NN to detect whether a number is divisible by 7. So your claim seems pretty strong.
Is this the first time a lecturer at the RIi has thrown a jacket over his jim jams to give the lecture?
32:18 The mistake is *not* that such a program cannot be constructed. The mistake is that the *Turing machine* itself cannot be constructed because the concept of "infinity" is meaningless nonsense. Change "loops forever" to "loops L times, for some very very large L". Then you see the problem of determining whether or not a program loops "forever" is *not* impossible. L could, for all practical purposes, be "forever". For example, L could be Graham's number. Sure, it is non-deterministic, but you have not proven that the outcome cannot be determined. Indeed, if P=NP, and there exist efficient low-coefficient polynomial time algorithms for solving NP-complete problems, then it is entirely possible that I can statically analyze your program and tell you whether or not the program will halt.
You could check whether a program would loop forever though. Any time a computer program similar to those given would repeat any step without altering the values that were previously stored in memory when performing that step, then the program can be identified as one that would loop indefinitely.
Let's see, on one hand: prize-winning, former senior wrangler, professor of mathematics at one of the leading British universities; on the other: random UA-camr. You must be right.
Well, you seem quick to appeal to authority. You do understand that is a common argument fallacy, I trust.
The problem here is a failure of logic, not of mathematics. What we have here is someone looking at a problem as a purely math problem and misapplying mathematical concepts rather than looking at it like a philosophy or engineering problem and finding the work-around.
The simply fact that we can write a program that should logically loop "forever" (or at least until the power and circuitry gives out) means that we know what elements go into such a program and we could then create a program that could check another program and identify whether those elements exist.
And, in fact, plenty of programs for creating computer programming already have such things built-in. If you try to write an infinite loop program like described in this video in most common, consumer coding software, and then try testing it within that software-- instead of permanently locking your computer until you have to reset it, the program will be quite nice to tell you that there is an error and the program will indicate to you that this program would result in an infinite loop.
Since such programs do exist, it is quite clear that such programs can exist-- and his claim that no such program could possibly be written is proved wrong because, well... the very thing he claims can't exist does exist.
TheHobgoblyn TheHobgoblyn The fact there exist programs that can show that SOME programs will or will not stop does not show that there can exist a program that can determine whether ANY GIVEN program will halt. An analogy is angle trisection with compass and straightedge. It provably cannot be done for an arbitrary angle but is easy for a right angle.
I want to be clear on what you mean by stating that a Turing machine can’t be constructed, they have been constructed. Presumably, you are referring to the physical impossibility of an infinitely long tape. While this is true, it’s not relevant to the proof of the Halting Problem. You claim that infinity is a ridiculous concept. I will acknowledge that there is no problem with analysis of mathematical structures that don’t include infinity, constructivists would agree. But a logically coherent (as far as we know, ht to Kurt Godel) system that includes infinities is equally valid.
You can determine if a program will continue infinitely without accomplishing anything so long as you don't entertain purely imaginary concepts such as a program of infinite length. But there are a finite reasons a program of finite length would loop endlessly without accomplishing anything. And a program can and has been built that can check if any of those finite conditions exist within the program.
I can only think of a single possibility that you could not write a program that would be able to check if the program would loop endlessly... and that is if the program was set to do a series of calculations that do never repeat and will only stop once it reaches a particular answer, but the answer cannot be reached through the calculation.
Only in such a case could a program not actually know whether or not the program will loop infinitely without actually doing the infinite calculation. And even then it would have to be an infinite calculation that is unknown-- because a detection program can probably detect that one is trying to calculate to the last digit of pi or root 2 or other known irrational numbers and stop the program and report this program would continue indefinitely.
For those looking for an instant answer; understand that this very lecture is an example of the subject of the lecture itself. Mr. Buzzard is attempting to prove something he proved is impossible to prove at the beginning of the talk. You can prove the validity of his statements in the lecture ("P"), but the analysis of what a computer can not do would take an infinite amount of time to compute and definitively prove ("NP") ... so the lecture proves that the lecture is impossible to prove. The only thing that prevents Mr. Buzzard from looping endlessly is the timer on the desk - a real world equivalent to a computer program's "time out" error trap.