TEDxQueensU - Selim Akl - Unconventional Computing
[Music] [Applause] [Music] thank you very much I'm uh thrilled to be here uh and I'm happy that you are all here you don't have to be here here and you are here so I'm I'm used to lectures where people have to be there so um and Now for Something Completely Different uh I'm a computer scientist and uh today I'd like to um question some of the uh conventional wisdom associated with computers and computation in general and let me start with our U Latin Moto in the school of computing which is suum ero computo I am therefore compute and the Moto really speaks at different levels at one level it says really what our identity is I am a computer scientist Computing is what I do my professional existence is to study the science of computing the theory and the practice I am therefore I compute but at the deeper level it says being is computing and this is the deeper level that I would like to talk to you about and challenge your understanding of what computers are and what computation is so which bring me to the question what does it mean to compute what is computation is it calculation 2 + 2al 4 is this what computers do just add numbers or is it uh logical operations A and B imply C what about text image and Sound Processing are they computations what about reading input from the outside world the the th theat in your house reads the temperature is this a computation what about affecting the outside world your thermostat tells the furnace to uh raise the temperature or lower it is this a computation or is computation limited to what mathematical models the mathematicians tell us that here is a model of a computer there is something called recursive functions that some people tell us is exactly what computers do recursive function are these referential self-referential uh processes like the pictures of Maurice aser everybody knows the pictures of aser they are pictures inside the pictures inside the picture and some people tell us that computers only do that recursive functions how about the neurons in our brains are they Computing or are they doing something magical what about physical phenomena like in the spring a flower opening is that process a computation what about chemical reactions are they considered computations what about cell multiplication DNA replications electrons spin deep deep in the heart of matter do they qualify so this is a long list so I'll get to the question are are they all computations perhaps some of them are not but if you tell me some of them are not you'll have to tell me why they are not computations more importantly have I exhausted the list or are there other things out there that we can also call computations I would like to argue that computation is ubiquitous to be is to compute and we will explore this notion throughout my next few minutes Computing permeates the universe and drives it every atom every molecule every cell everywhere at every moment is performing a computation for human from Human cognition to photosynthesis in plants all the way to the migration of butterflies every transformational process involves a computation does the atom the molecule or the cell know that it is Computing we don't care we will never know and we should not really care whether the atom or the molecule or the cell or any of the constituents of the UN Universe knows that it is performing a computation is no more relevant than your computer on your laptop knowing that it is Computing the important thing is that the computational Paradigm is a very powerful but very simple explanation of the processes of Nature and it allows us to understand how nature works I can explain Nature by saying acquiring manipulating and transforming and transmitting information is all what nature does and this is how we can better understand the world that surrounds us being is Computing here are two physicists so you don't say that I am a computer scientist and therefore I think that everything is a computation here are two physicists and let's see what they are telling us Tomaso tool says in a sense Nature has been continually Computing the next state of the universe for billions of years or we have to do and actually all we can do is hitch a ride on this huge ongoing computation David Deutsch think of all our knowledge generating processes our whole culture and civilization and all the thought processes in the minds of every individual and indeed the entire evolving biosphere as well as being a gigantic computation the whole thing is executing a self- motivated self-generating computer program which brings us to Conventional versus unconventional here are conventional computers everything you work with today is conventional from a huge uh supercomputer to your laptop to the the chip in your toaster they are all conventional computers and what do they do everything we do today is conventional from word processing to email to science math and Engineering it's all conventional computations is anything wrong with conventional computers no they have served us very well and they will continue to serve us for a while but they are reaching the limit you may not know it but they are reaching the limit when it comes to processing huge amounts of data and Performing huge numbers of number crunching in a reasonable amount of time our computers today are hitting a wall for example I work with surgeons in the kgh suppose that a surgeon wants to perform a surgery on a patient but before performing the surgery you would like to practice on a three-dimensional model of the patient that involves every every uh component of the patient's body and then be able to rotate it in real time and execute an operation on it no computer today can do this for this surgeon conventional computers are hopeless for solving unconventional problems the previous one that we talked about the threedimensional model was a conventional problem there's nothing magical about it but then there are things that are unconventional and these pose an even bigger problem to today's computers here are some unconventional computations when the data you are working with change with the passage of time or when you have deadlines that you have to meet or when the laws of nature interfere and control the computation you are working with imagine you're working on your laptop and there is something outside that's affecting your computation and so on what are unconventional computers that will be able to handle all these uh all this world parallel computers analog computers biological computers quantum computers and accelerating I'm going to try and cover a little bit of these so it's a January morning and just woke up and um there's a pile of snow in your driveway and you're trying to clear it and it looks hopeless because the snow keeps falling and you are slow in the meantime your neighbor comes out with his four kids and they clear their driveway in no time at all they drive to work and come back and you are still shoveling and by the way I I want to give credit for these slides to my uh daughter Sophia here she came from Montreal to listen to me so thank [Applause] you which brings me to parallel Computing why why be happy with one laptop you can put a whole bunch of them to work on your problem and that will speed things up and why restrict yourself to 25 you can have a 100 or a thousand or a million or a trillion there are a trillion Angels on the head of a pin you make them smaller and smaller and smaller Nature has done it before this is the leaf of a plant and on the surface of the leaf are little mouths and these mouths are called stomata from the Greek and their job is to open wide to let carbon dioxide in and however they want to be careful not to let precious water vapor out how they do it is by beautiful magnificent dance around the leaf every one of these stom looks around it and if the ones around it are closed it opens if the ones around it are open it closes and they go around this in a what we would call a distributed parallel algorithm enough to make a computer scientist Green With Envy how does nature compute well this is a big question so we can narrow it down for example does nature use infinite Precision real number when it's it's doing its own computation numbers like this well our computers today cannot handle infinite Precision real numbers they have a word size 32 bits or whatever and that's it 64 bits that's it can I hope for a an unconventional computer that would do it let's look at this interval those of you who are mathematicians will know that the interval from 0 to one is an infinite interval in fact for every two numbers in that interval there's an infinite number between them and infinite number of numbers between every two numbers can I Traverse this Infinite Space in constant time well I can suppose I can rig my computer to behave like this ball that is going on this smooth incline the smooth incline has an infinite number of points and yet the ball touches them all and doesn't M A doesn't miss a single one of them I've done it I've traversed an infinite an infinite SE quence in finite time now I'm going to ask you what is the meaning of life and I don't mean in a philosophical or religious way let's ask in a biocomputational way if you want I I just invented this word these three fellows were given the Nobel Prize for um medicine in 1962 when they discovered the structure of DNA but if you read the citation what does it say it says that they were given for their discoveries concerning the molecular structure of nucleic acids and its significance for information transfer information transfer that's the secret that's the meaning of life information and computation is the answer and I'm going to try and convince you very quickly information is fundamental to all life on Earth every cell in our body is packed with information and our cell has a little computer in it and that computer has one instruction make a copy of yourself make a copy of yourself and you keep doing this because the moment you lose this information you die and we eat in order to keep the cell doing this we keep providing energy so that the cell can keep copying itself I am therefore I compute indeed here it is that magic uh molecule the secret of life it's copying itself right now so that you can continue to live one gram of DNA can hold as much information as a trillion compact discs if you fill this Auditorium with compact discs one gram of DNA will do the trick and if you compare a DNA computer with a conventional computer the DNA computer wins hands down we can solve very complicated Problems by encoding the data in the DNA and in fact I had a student here build a DNA computer in a test tube and we solved a problem of breaking a cipher just as a proof of principle and if DNA is not small enough for you you can go down way down to the level of the atom Richard feeman said there is plenty of room at the bottom so let's suppose I encode the zer ones in an atom okay I will use one atom to be either a zero or a one I can put the entire knowledge of humanity in a cube .1 mm to the side all right every book that was ever published can be encoded in this little Cube all right let's move to Quantum Computing your computers today work with zero and one is either zero or one at any given time in a Quantum world it is zero and one at the same time it's not to be or not to be it is to be and not to be spin up or spin down no it's going to be spin up and spin down at the same time and why is that interesting well if one bit which we call a q bit affectionately if one bit can be zero and one at the same time imagine a register of three they can be in eight possible States simultaneously if 1,24 of them can be in two to the 1,24 states simultaneously a number that boggles the mind and why is that good well go back to parallelism they can do a tremendous amount of work simultaneously one example is factoring I can factor a number as huge as this one with a quantum computer very quickly if you have a 1024-bit number using today computers and the best algorithm it would take you two to the two to 221 years which is longer than the universe has been around on a quantum computer it would take one second and we developed uh a new game of chess here at Queens each each piece is in a superposition of two pieces and you don't know what they are until you touch the piece to move it and it will tell you I'm a queen or I'm a I'm a pawn or I'm a bishop and then you will have to move it as a pawn or a bishop but then it will again assume a superposition and you will not know what it is solar energy we were talking about um saving the universe so um we all put solar cells on our roofs and we are trying to be smart a solar cell has an efficiency at best if you are engineered very well of 27% going back to the leaves leaves have an efficiency of 99% they absorb the the the if they absorb the energy of the of the Sun in a very efficient way and this is all due to some bacteria called the fmo bacteria the eore bacterium allows the photon that hits the the leaf to travel very quickly to the reaction Center the CPU of the leaf and turn itself into chemical energy and it does this by virtue of the quantumness it explores all possible paths that lead to the central processing unit and finds the shortest one and goes there directly okay how many times have you looked at this and wondered did my computer crash or is it doing work still should I abort the process or maybe wait in one second it will tell me it's done wouldn't it be nice to have a little device which tells you this program is going to crash don't run it or this program is going to go forever don't run it or this program will do just nicely run it theoretical computer scientists tell us this is hopeless you cannot do it you cannot have a device like this but I can I can have a computer that doubles its speed at every step so I can have on the side another machine that is called an accelerating machine and it executes the first step in 1 second the second step in half a second the third step in a quarter of a second and the mathematicians among among you will tell you that the sum of this series is two in two seconds I know the answer I can go on and run my my program in confidence or not run it if it tells me it's going to run forever and we did many many other things um we we used slime mold real slime mode on a real map of Canada to compute the highway system of Canada and it replicated the highway system we put we put uh the mold in Toronto and food in the major centers and the mold expanded and recreated the highway system of Canada exactly as we use it today if you can get your hand on a black hole you can do some very interesting computations or you can harness time travel for uh your purposes and you can see all this on my web page we have algorithms that work very well just if we have a time machine but our computers Universal we saw that computation is universal our our computers themselves Universal well here is the conventional wisdom today any computation that can be performed by any physical Computing device can be performed by any universal computer as long as the latter has sufficient time in memory true well the idea here is that they are all the same they're going to simulate each other other whatever you can do on your cell phone you can do on your toaster you can do on your camera you can do on your laptop your pwn top or whatever true false no finite computer can be Universal here is my challenge you can find this on my web page and try to solve it I will put a a monetary prize on it there are clocks hanging on the wall and they are ticking away as you are going to perform your computation and they are producing random numbers they are not even ticking as clocks they are producing random numbers and the challenge is I want you at a moment I will Define I want you to compute the average of all the times shown all right but remember the moment you start reading them they have already produced new values at the other end of the wall so you have to be careful no computer that is incapable of producing n operations for n clocks will fail and there is no hope of simulating this operation on another computer because simulation simply does not make sense the clocks are ticking the information is lost we back to information if we don't capture the information at the right time too bad it's gone and this is applicable to all the models of computation the ones we have today and the ones we'll have in the future they are all doomed none of them can claim to be Universal and that brings us to the final little story here it's um um an endearing story between a computer scientist on the right and an engineer on the left the engineers here it is said with affection okay our engineer is very proud of his computer he goes to his girlfriend and says look I just built a universal computer that can do n operations per time unit and Alice says Bob what if I have a problem that requires n plus1 operations what are you going to do then Bob has an exclamation mark on his head and he says okay I'm going to go back to the drawing board and he comes back the next day with a bigger machine and he says now I have a computer that does npl1 operations per time unit what do you say to that Alice and Alice says well Bob what if I have n plus2 operations that I need not just n plus one now he has two exclamation marks but Bob is an enterprising young man he's an engineer he doesn't take no for an answer he goes back and comes back with an even bigger machine and now Alice is really starting to get bored with this game and she says Bob listen what about if I have n plus three and Bob is crushed because he knows he cannot win this game it's an escalating game every time he comes back with a machine she pauses a bigger riddle that he cannot solve and so we will we ever have uh a universal computer well only one only one type of computer will be Universal and one that can do an infinite number of operations per time unit and that would be the universe itself thank you [Applause] [Music]