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)
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.
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.
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 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?
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
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.
No it doesn't. Assuming you typed in "53" initially like he did in the talk, the computer would print a 0, and then x would decrease by 1 (to 52 in this case). This would keep happening over and over again *until* x=1. At this point, after printing a 0, x would be decreased to zero. Because zero is not less than zero, the program would finish instead of going back to step three. This kind of function is called a loop. Loops in computer programming are fine. Infinite loops however, are not.
@@HotCrossJuns Yes it does instead. Try putting in 0. The program prints a 0, when it shouldn't have printed any. Teh correct formulation would be: while (x-- > 0) { print("0") }
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)
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.
8:53 According to the Wikipedia article on Deep Blue, it used an algorithm called alpha-beta pruning, which allowed it to ignore branches where its opponent would absolutely take advantage of mistakes. I know it's a small point, but it seems to be essential to your argument that the computer wasn't really thinking. I downvoted this video partly because of small stuff like that, but also because of larger problems like how you don't give a formal definition of thought. If you don't have a proper definition, how can you be sure that computers can't do it? And if you aren't sure, why was it included in this talk? That said, this was still interesting food for thought. Thanks.
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.
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.
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.
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.
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 ?
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?
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).
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.
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
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.
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 ?
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.
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.
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.
@10:00 mark, he says that his unloading the dishwasher, robotically, while thinking about something entirely different is an example of 'thinking'. That's just nonsense. Anyone who knows anything about modern operating systems knows that the computer can be set up so that some background task(s) run whenever there are IDLE CPU CYCLES.
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.
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
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.
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.
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
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?
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?
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.
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.
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.
I have a question regarding integer factorization: what about Shor's algorithm? Does it not prove that integer factorization can be solved in polynomial time? The way I understand it is that it can, we just have to overcome the technical (engineering) difficulties of building reliable quantum computer (unlike the prototypes we have now). Maybe I am missing something :)
In sudoku make 1 equal and range of possibilities from all the possibilities in a single sudoku cell. This implies so many 1’s per adjectent row column and subgrid and you can compare your 1 assumption or multiple 1 assumptions at once against other groupings upgrading the data where applicable until the grid is solved or you run into a conflict (too many 1’s in a row subgrid or column discovered) and you may be able to solve sudoku in p time.
It's probably adderall actually, his eyes are pretty pinned out. Cocaine usually makes the pupils huge. Adderall does too, but people that take it all the time sometimes get small pupils instead. Now you know!
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?
30:34 is some ugly spaghetti code. It's not such a "complicated logic puzzle". This is called accidental complexity, and it's being used to present the problem as something harder than it is. Replace it by: 1. Let x be a number typed by the user. 2. Switch of x: Case (10 < x < 100) or (x < 10): x = 100): Go to 3. Case else: x = 100 -the first switch case is reachable with: *x
"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".
the traveling salesman is said to be NP how do you quickly check a suggested path is optimal should there not be a set of problems outside NP that can not be solved or checked quickly
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.
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...
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.
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.
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.
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.
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.
@The Grapist: Of course it is. It's intended to be of interest to laypeople, not to experts in the field. I think, he does a brilliant job of verbalizing the whole thing for its target audience without dumbing it down.
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.
49:15 ... The product of P*Q is 2623, and suppose we do not know what "P" and "Q" actually are? ... The square root of 2623 is 51.21523... and 52 x 52 = 2704, subtract 2623 from 2704, and the remainder is 81, which we know is 9 x 9. so 52 + 9 = 61 - "P" and 52 - 9 = 43 = "Q". ...So what about 2183, the square root of that is 46.722585.... So let's try 47 x 47 = 2209, subtract 2183, and we get 26 as remainder, That is NOT a square number, so let's try 48 x 48 = 2304, now we subtract 2183, and leave a remainder of 121... Now that IS a square number 11 x 11 = 121. ... 48 +11 = 59 = "P" and 48 - 11 = 37, = "Q", de-multiplication of this small dual-prime composite number solved. So what about gigantic Dual-Prime Composite Numbers? That is only a slightly more difficult problem. First we need to discover an approximate "Aspect Ratio" of the P*Q Rectangle, It might be very long and thin, Oops! that makes it very easy to factor! DO NOT DO IT! we only have to keep stacking up these long thin rectangles till they are almost square. .. The best is like The Bitcoin 256 Bit Dual Prime. ... So we need to steal the million or so Bitcoins that have gone walkabout, OZ Aboriginal style! ... That is actually another piece of cake. ... But it does require a bit of Goldilocks Hot and Cold Porridge testing, to establish the good, better, best Aspect Ratio. Any number of countless millions of suitable aspect ratios will be perfectly adequate! ... A The Product of a small and very large rectangle area, with very similar aspect ratios, will result in a very square large pseudo-square rectangle. ... Those missing Bitcoins we hope are destined for good charitable purposes, so we will not reveal too many tips here! Elementary Algebra is all that is required. We will already know the exact value of each side of our similar aspect ratio rectangle, and neither side need be a prime number. ... If you do figure this out, and give the proceeds to charity? you will be blessed!
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.
![Lp. Сердце Вселенной #60 РОЖДЕНИЕ ЛОЛОЛОШКИ [Финал] • Майнкрафт](http://i.ytimg.com/vi/YoR0pAV9FVQ/mqdefault.jpg)
You can tell it's a proper math talk when the slides were made in LaTeX.
not just latex but beamer too!
If it's in LaTeX, it must be true
I almost left because of the pants then I saw the slides and decided to stay.
Nothing about this was proper math
And because he couldn't be bothered figuring out how to make animated/interactive slides - what a nightmare
Dude walked 10K laps around that damn table.
In his pajama pants, no less.
That's quite a choice in trousers to wear for a lecture at the Royal Institution
Proving that maths geeks are fabulous!
He didn't choose them; the RI randomly issues a 'uniform' to its lecturers.
I couldn’t help but think of a certain investigator in Alan Moore’s From Hell.
They're pyjamas. He also missed his morning coffee.
@@suntexi wrong, he wears crazy trousers to all his imperial lectures
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)
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!
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
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
16:48
problems reviewed in class: bisect an angle
problems on the test: trisect an angle
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?
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?
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.
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.
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.
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.
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.
Algorithm at ~29:25 gets stuck in a loop if x=10.
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.
Thanks to the RI and Prof. Kevin Buzzard for a fast show intro into what's computable and what may not be. Brilliant!
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.
Lord Voldemort in pijamas pants and fine costume explaining awesome things :D
Those opening 5 minutes were the creepiest and most amazingly scary in all the Ri lectures I have seen :O
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.
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
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.
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?
It was a very smooth journey from Killer Robots to P vs NP an millennium Price Problem 😁
34:15 what about all the programming consoles and IDEs that tell you "error, infinite loop". How do they know that?
You can find if some subset of programs will halt or not. But you can not do that for ALL possible programs.
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?
For the program at 29:19, the answer I got was that if x
I wish I could have understood more than 30% of what he said.
@41:29
The expanded version of program 2 has a bug!
No it doesn't. Assuming you typed in "53" initially like he did in the talk, the computer would print a 0, and then x would decrease by 1 (to 52 in this case). This would keep happening over and over again *until* x=1. At this point, after printing a 0, x would be decreased to zero. Because zero is not less than zero, the program would finish instead of going back to step three. This kind of function is called a loop. Loops in computer programming are fine. Infinite loops however, are not.
@@HotCrossJuns Yes it does instead. Try putting in 0. The program prints a 0, when it shouldn't have printed any. Teh correct formulation would be: while (x-- > 0) { print("0") }
41:26 what if the user types in 0? This still prints 1 zero
*computer breaks down*
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)
A 4 GHz processor does not process 4 billion instructions per second. You need to look into the CPI and do the maths.
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.
A killer robot forced him to wear those pants.
No one would volunteer to do that.
8:53 According to the Wikipedia article on Deep Blue, it used an algorithm called alpha-beta pruning, which allowed it to ignore branches where its opponent would absolutely take advantage of mistakes. I know it's a small point, but it seems to be essential to your argument that the computer wasn't really thinking.
I downvoted this video partly because of small stuff like that, but also because of larger problems like how you don't give a formal definition of thought. If you don't have a proper definition, how can you be sure that computers can't do it? And if you aren't sure, why was it included in this talk?
That said, this was still interesting food for thought. Thanks.
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.
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.
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.
Other than the opening few minutes of FUD, quite a wonderful, general-audience accessible to the idea of P=NP.
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.
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 ?
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?
Oh ! poor camera operators following this guy arround the stage for one hour...
1) Please forgive my limited understanding
2) Are entropy and the arrow of time physical clues for N not equal NP ?
Does multiplication increase the entropy of the universe and factorisation reduce it?
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.
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.
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.
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.
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 ?
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.
Thanks!
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.
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.
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.
@10:00 mark, he says that his unloading the dishwasher, robotically, while thinking about something entirely different is an example of 'thinking'. That's just nonsense. Anyone who knows anything about modern operating systems knows that the computer can be set up so that some background task(s) run whenever there are IDLE CPU CYCLES.
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.
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
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.
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.
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
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?
Mr. Buzzard is trying to show that you can also prove things by talking about them very very quickly.
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?
This was the best introduction of this problem to a lay audience that I have ever seen.
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.
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.
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.
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.
I have a question regarding integer factorization: what about Shor's algorithm? Does it not prove that integer factorization can be solved in polynomial time? The way I understand it is that it can, we just have to overcome the technical (engineering) difficulties of building reliable quantum computer (unlike the prototypes we have now). Maybe I am missing something :)
In sudoku make 1 equal and range of possibilities from all the possibilities in a single sudoku cell. This implies so many 1’s per adjectent row column and subgrid and you can compare your 1 assumption or multiple 1 assumptions at once against other groupings upgrading the data where applicable until the grid is solved or you run into a conflict (too many 1’s in a row subgrid or column discovered) and you may be able to solve sudoku in p time.
a computer couldn't do coke, if u catch my drift.
things change. fast. google sold boston dynamics.
i don't get your coke thing. and yea i knew everything this guy was saying already. but I'm kinda a geek so i guess that's different from most people
he means the presenter is completely turnt out on coke
It's probably adderall actually, his eyes are pretty pinned out. Cocaine usually makes the pupils huge. Adderall does too, but people that take it all the time sometimes get small pupils instead. Now you know!
you cant get adderall easily in the uk or anything similar
Klaus Gartenstiel that's what you say until they start raping car batteries and shooting thunder juice.
49:08 After that long video of umms and ahhhs, volume shifts and pitch oscillations...This single moment was surreal.
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
30:34 is some ugly spaghetti code. It's not such a "complicated logic puzzle". This is called accidental complexity, and it's being used to present the problem as something harder than it is.
Replace it by:
1. Let x be a number typed by the user.
2. Switch of x:
Case (10 < x < 100) or (x < 10):
x = 100):
Go to 3.
Case else:
x = 100
-the first switch case is reachable with:
*x
"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".
the traveling salesman is said to be NP
how do you quickly check a suggested path is optimal
should there not be a set of problems outside NP that can not be solved or checked quickly
Traveling Salesman is not NP. I cannot be solved quickly and cannot be checked quickly either.
Those robots aren't killer robots... they are mostly designed to assist troops by bringing them supplies.
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.
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...
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" ???
Can a computer ask a new unprogramed question?
And then generate an app or program that could answer that question?
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.
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.
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.
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.
lectures like this are why it's hard for me to sit through one-hour lectures... I kept hoping that it's gonna get better. it didn't :(
Why should it get better? It's an hour of information you may or may not need. If you need it sit it out, if not go home. It's that simple.
it's surface level all the way through
Get better? What are you talking about?!
@The Grapist: Of course it is. It's intended to be of interest to laypeople, not to experts in the field. I think, he does a brilliant job of verbalizing the whole thing for its target audience without dumbing it down.
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.
49:15 ... The product of P*Q is 2623, and suppose we do not know what "P" and "Q" actually are? ... The square root of 2623 is 51.21523... and 52 x 52 = 2704, subtract 2623 from 2704, and the remainder is 81, which we know is 9 x 9. so 52 + 9 = 61 - "P" and 52 - 9 = 43 = "Q". ...So what about 2183, the square root of that is 46.722585.... So let's try 47 x 47 = 2209, subtract 2183, and we get 26 as remainder, That is NOT a square number, so let's try 48 x 48 = 2304, now we subtract 2183, and leave a remainder of 121... Now that IS a square number 11 x 11 = 121. ... 48 +11 = 59 = "P" and 48 - 11 = 37, = "Q", de-multiplication of this small dual-prime composite number solved. So what about gigantic Dual-Prime Composite Numbers? That is only a slightly more difficult problem. First we need to discover an approximate "Aspect Ratio" of the P*Q Rectangle, It might be very long and thin, Oops! that makes it very easy to factor! DO NOT DO IT! we only have to keep stacking up these long thin rectangles till they are almost square. .. The best is like The Bitcoin 256 Bit Dual Prime. ... So we need to steal the million or so Bitcoins that have gone walkabout, OZ Aboriginal style! ... That is actually another piece of cake. ... But it does require a bit of Goldilocks Hot and Cold Porridge testing, to establish the good, better, best Aspect Ratio. Any number of countless millions of suitable aspect ratios will be perfectly adequate! ... A The Product of a small and very large rectangle area, with very similar aspect ratios, will result in a very square large pseudo-square rectangle. ... Those missing Bitcoins we hope are destined for good charitable purposes, so we will not reveal too many tips here! Elementary Algebra is all that is required. We will already know the exact value of each side of our similar aspect ratio rectangle, and neither side need be a prime number. ... If you do figure this out, and give the proceeds to charity? you will be blessed!
the distance is always "the length from the pencil tip to the spiky bit." words to live by
Is this the first time a lecturer at the RIi has thrown a jacket over his jim jams to give the lecture?
"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.
I think we missed the Joke slides he mentioned earlier :'(
hahaha...So people definitely lie :P
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.
His description of how chess engines work was totally without any background knowledge.
Did they leave treats hidden around the desk?