Turing Machines - How Computer Science Was Created By Accident

hi everyone Jade here today's video is an origin story about the entire field of computer science now when I say computer science I mean literally everything to do with computers laptops desktops smart phones iPods gps's quantum computers literally every physical manifestation of a computer you can think of but I also mean the theoretical side too so the study of algorithms computability and complexity theory all the kinds of things that a theoretical computer scientist would study now the reason I want to tell this story is because it's incredible so not only was computer science accidentally created

but it was created from trying to answer a very abstract question about the foundations of mathematics this story highlights an incredible turn of events a brilliant thinker and the interconnectedness of two fields the story starts with an extraordinary man named David Hilbert he lived at a very exciting time in the history of mathematics see back in the 1900s it had come to light that no one was really sure what they were studying when they were studying mathematics when we study biology we're studying living things that exist in the real world when we study physics we're

studying real-world phenomena which we can verify it by our experiment but math was it the study of real-world objects or abstract entities did it exist in our minds or in some other realm of existence the ancient Greek philosopher Plato thought that mathematical objects shapes numbers and the relationships between them belong to their own ideal world separate from ours he calls it the world of forms but Hilbert wasn't a fan he was a modern day man and the plate in his view was too mystical and airy-fairy for his liking and idealized world of forms please Hilbert

was interested in down-to-earth matters what could and couldn't be proven another prevailing view put forward by the German philosopher Immanuel Kant was that math was a mental construct based on our intuitions but Hilbert had a problem with this too after all intuitions could often lead us astray the fact that the word paradox exists in the English language is evidence of that these differing viewpoints greatly irritated Hilbert it's not uncommon to have multiple viewpoints in other disciplines literature for example is praised for being able to have multiple interpretations of the same thing even physical laws are

revised and changed over time but math oh no this just wouldn't do math was regarded as different from the other disciplines the epitome of certainty the fact that two plus two equals four would never be revised and changed and it just wasn't good enough that different mathematicians had different interpretations about what it meant aside from the prestige of math being called into question these differing opinions had practical problems to those who agreed with Kent's intuition ISM didn't believe that the idea of infinity fit within mathematics those who thought that logic was the foundation of math

ran into logical paradoxes and inconsistencies that limited what they could and couldn't do in comparison with the other schools of thoughts you couldn't have different mathematicians playing by different rules this was just unacceptable and Hilbert was going to do something about it he proposed a crazily ambitious program do axiom 'it is all of mathematics this sentence requires some explaining see Hilbert thought that if we treat math as nothing more than a formal system there could be no more disagreements about what was and wasn't allowed so what is a formal system well it's an alphabet or

a set of meaningless symbols which can be manipulated according to a fixed set of rules chess is a formal system the alphabet are the pieces which are manipulated according to a fixed set of rules it's important to note that the pieces and the rules don't have any meaning outside of the game hillford thought that this was how we should view mathematics something similar had been done by Euclid on a much smaller scale some 2,000 years earlier by putting forward five self-evident axioms and the rules of how to build upon them the whole system of Euclidean

geometry was born equipped with these axioms we don't need to know whether a triangle lives in the world of forms or in our heads to know that it angles always add to 180 degrees so in this way you clearly in geometry can be seen as a formal system Hilbert wanted to do something similar to find the foundational axioms for formal systems for which ball of mass mass could be built upon this would eliminate any disagreements about what was and wasn't allowed this was a monumental task and to start Hilda thought about the three main things

you would want in a foundational system of mathematics consistencies completeness and decidability consistency means that no contradictions can be proven within the system for example you can't prove that two plus two equals four and that two plus two doesn't equal four inconsistencies would render the entire system useless completeness means that a proof was required that all true mathematical statements which existed in the system could be proven within the system and finally decidability this was the idea that there should exist an effective procedure for deciding the truth or falsity of any mathematical statement for example if

given the statement P plus Q equals Z there should be some effective procedure for deciding whether this statement is true within the system this is where our hero of the story comes along Alan Turing you may know him from such films as the imitation game or the biggest award in computer science called the cheering award at the young age of 22 cheering got intensely interested in this last question beside ability did there exist an effective procedure for deciding the truth or falsity of any mathematical statement but cheering sir a slight problem with the question what

exactly was an effective procedure today an effective procedure is considered to be an algorithm some step-by-step set of instructions that you can follow without using any real thought or intuition but this was back in the 30s and the idea of an algorithm was still vague and ill-defined we're used to the concept now because they're fundamental to how computers work but computers didn't exist back then or at least not as we know them today the word computer referred to people usually women who were given a list of instructions and carried out tedious computations by hand this

job required little thought and definitely no mathematical intuition throughout his life cheering was fascinated with the relationship between humans and machines he's famous for coming up with the of the Turing test a test for determining whether a machine is capable of thinking like a human this was no exception as the term effective procedure was too vague to do anything rigorous with he decided to define it himself he based his definition on a human computer he decided that anything a human computer could do by mindlessly following a list of instructions using no genius or insight whatsoever

was an effective procedure he thought about the basic components of what a human computer does when they're computing one they read instructions to they read and write symbols on a piece of paper according to the instructions 3 they occasionally erase symbols and replace them with new symbols and 4 when they're finished with the computation they stop that was about it and here is where the truly revolutionary part comes in that would transform the world for years to come cheering recognize that every step of what a human computer did could be replicated by a very simple

theoretical machine in place of the human could be a scanning head which could read one symbol at a time erase one symbol at a time and write one symbol at a time the piece of paper could be replaced by an infinitely long piece of tape which contained one symbol per square but how does the machine know what to do when a human reads a set of instructions something is going on in their mind which tells them what to do next during thought of these as states of mind and so similarly for his machines devised the

idea of internal states which tell the Machine what to do this idea is best understood using visual diagrams and an example say we want the machine to perform the very simple task of recognizing when there are an even number of zeros and ones in the tape this is easy for a human who has mastered the art of counting but it's not so straightforward for a machine a simple way for our machine to tackle this problem is to pair a 0 with a 1 and then cross off the pair with an X it keeps doing this

until it can't anymore if it crosses up all the symbols in the tape will know there was an even amount if it doesn't well know that there wasn't now how do we program our machine to carry out this task well we build it with an internal state table that looks like this I know this looks complicated but it's not too bad let's read it together take this tape with these symbols we want the machine to tell us whether there is an even number of ones and zeros the machine starts in the start state the stop

state tells the machine if I find a zero I will replace it with an X move to the right and into state B if I find a one I will replace it with an X move to the right and in two states see if I find an X I'll leave it alone and stay in the start state if I don't find any ones or zeros and only encounter blank squares they must have all been paired up so I move to the accept state so at the moment our scanning head is in the start state it

reads a zero replaces it with an X moves one square to the right and interstate B now the machine is justina zero and needs to find a one two pair away so state basis if I see a zero or an X I'll leave them alone and move right one Square and stay in state B if I see a one I replace it with an X and move to state D so our scanning head raises 0 moves one square to the right and stays in state B now it reads a one replaces it with an X

and moves one Square to the left and into state B state D is only entered when a 0 one pair has been crossed out by X's so the Machine needs to reset for the next count it says I keep moving the scanning head to the left ignoring everything if I see a 1 I leave it as a 1 if I see a 0 I leave it as a 0 and if I see an X I leave it as an X I keep moving until I reach a blank square which indicates I've reached the beginning of

the list of symbols I then move one square to the right and go back to the start state to repeat the whole process after another round of this the machine only encounters X's so keeps moving right and remains in the start state when it reaches a blank it moves into the accept state and we know that this list of symbols does have an even number of ones and zeros so that's how one of these machines would work but here truly had another incredible insight see at the moment you would need to build different machines to

do different tasks a machine to calculate square roots would need to be built with a different internal state table than a machine to do addition but sure he realized that any internal state table could be encoded into a list of ones and zeros in this way we could feed the instructions as well as the problem into a new machine and that machine could perform that set of instructions today we know this as a programmable computer we have computers which we can program to do different things after they've been built that idea originated right here insurance

paper he dreamed up a theoretical machine that could perform the same task as any other of his machines and it was pretty freakin incredible even though this theoretical machine is incredibly simple it can in principle do everything that a human computer can do this abstract machine now called a cheering machine was Turing's definition of an effective procedure an effective procedure with anything that could be computed by a cheering machine in a finite amount of time so with that out of the way he could go on to answer Hilbert's question did there exist an effective procedure

for deciding the truth or falsity of any mathematical statement or as framed by cheering did there exist a cheering machine for deciding the truth or falsity of any medical statements the way that cheering answered this is beyond the scope of this video I did make an entire separate video about it called the halting problem which you can check out after this but I will tell you that Hilbert's program ended in complete failure and cheering contributed to it by proving that there was not an effective procedure for deciding whether any mathematical statement was true or false

this alone is an amazing achievement but cheering's little machines took on a life of their own by making a definition of computation that was rigorous people who are able to study the nature of computation and its limitations like never before this bursts the entire field of computer science which is the study of what computers can and can't do the complexity of algorithms and the overall nature of computation furthermore by coming up with an intuitive easy-to-understand model people were able to turn the abstract and vague notion of computation into a physical machine that could replicate the

process cheering machines are the blueprint of the modern-day computer anything from your desktop to your smartphone to the computers on the international space station are based on cheering's model anything that any of these machines can do can in principle be done by a Turing machine it might just take a bit longer now it's worth noting that other models of computation do exist Alonzo Church who would later become cheering's doctoral advisor actually came up with his own model just weeks before cheering called the lambda calculus cheering found out about this just before publishing his own paper

and wrote a quick appendix which showed that church's lambda calculus and his own model were in fact equivalent meaning that anything that can be computed by the lambda calculus can also be computed by a Turing machine and vice versa however because of their concreteness simplicity and precision chairing machines whether model that caught on and captivated the imaginations of the mathematics community even though they were conceived nearly 90 years ago there is currently no working model of computation more powerful than Turing's this is embodied in the church Turing thesis which states that anything that can be

computed can in principle be done so by a Turing machine if the cheering machine can't compute it it's not computable that's not to say that this might not someday change there's a growing field of study called hyper computation which studies theoretical models of computation more powerful than Turing machines the trouble is making them physically realizable another model of computation that's been getting a lot of hype recently are quantum computers which if they work will definitely bring something new to the table but so far cheering simple model which he dreamed up at age 22 kind of

as a by-product to answer a totally different question is still the most widespread model of computation to date this video was an origin story about one of the most fascinating and relevant fields of study but there is so much more to computers and algorithm that's worth exploring if you'd like to get a real handle on the fundamentals of computer science hearing about it in a video probably isn't enough but there is good news you can learn about it the same way I did through interactive courses on brilliant in this computer science fundamentals course you can

learn how to write programs search for solutions using the computational method of brute force and make your own algorithms there are so many cool algorithms out there for solving different problems and you'll get to explore and create the same ones taught in a computer science degree by getting your hands dirty solving problems and making mistakes you'll get a real intuition for the power of algorithms I can say from my own experience that this course is perfect for those wanting to get started in computer science brilliant has a whole bunch of other courses too not just

in computer science but physics and math as well it's worth checking out if you're a curious mind who loves to learn and be challenged which as you clicked on this video I'm guessing you are if you'd like to check it out and support the channel go to brilliant org slash up and Adam it's free to sign up but the first 200 people that go to that link will get 20% off the annual brilliant premium subscription that's the subscription I've been using the link is also available in the description as always a huge thank you to

all of my wonderful patrons on patreon these videos would not be possible without you and your dedication to science inspires me thank you for watching I'll see you in the next episode bye