Turing Complete - Computerphile

there's one thing that we keep coming back to and this idea of turing complete what does it mean and why do we need to worry about it yeah what does it mean to say it's a language it's usually in this context a programming language is or is not during complete well obvious first example is that every programming language you're familiar with um i mean we'll refer to the usual suspects fortran basic pascal cobol c c plus plus java they are all turing complete so what fundamentally does a thing have to be in order to be turing complete and the answer is it needs to be able to do everything that a turing machine can do mercifully we have made several videos on this topic some from me some from my colleague mark jago and we have visited quite a lot of these issues just to recap a turing machine is thought of as an endless infinite piece of tape and it has a read write head that goes over the top of the marks on that tape which can be anything you like but conventionally to keep it very simple you say it's zeros and ones and you can show that just the ability to read and write on an infinite piece of tape patterns of zeros and ones is powerful enough to compute anything that can be computed admittedly your low level turing program with all its zeros and ones maybe 10 trillion times longer than your compiler c program i don't know but in principle it can do exactly the same some people argue that actually although it was touring that made brought this all to our attention in the late 30s with the work he did in some ways some people would say it really ought to be called babbage complete because another uk well he was a computer scientist actually in the way his brain worked charles babbage many of you know he started off by just doing very powerful calculating machines difference engines well going beyond that some of you will know that charles babbage said well that's just like a a calculator that you have in your top pocket but weighs about 10 tons and full of cog wheels but even just using cogwheels he went on and said i want to do something that really can compute in the way that a human can do and the one thing he realized straight away is to make it really powerful enough you must at very minimum have what was called in those days conditional branching if statements you've got to be able to say that i'm going to look at a certain cell on my tape and if it's got a one in it i'm going to do this thing and if you've got a zero in it i'm going to do that thing so it's this sort of two-way choice that an if then else statement can give you and he said it's absolutely vital to be able to do that because very often the computations that humans do depend on the precise nature of the data they are given some data will send you one way some data will send you another so this conditional branching is absolutely vital and as a sort of kind of result or side effect of that it also implicitly means that you've got to have the ability to go to somewhere different in your memory for example you might be saying if this condition is true then i carry on with the sequence of instructions uh that i immediately follow but on the other hand if the else statement is true then i have to go off somewhere else and do something different now all our undergraduates we absolutely do not encourage the raw use of go-to's because it's not good well-structured programming but those who even done assembler will know under the hood you can't avoid it you really do have go to statements which say i'm here at location 88 or whatever now jump off to location 200. so if you like the conditional branching implies a go-to in that you might stay in this part of the tape you might jump off somewhere else we've seen on the turing machine videos it's perfectly possible to get your read write head chattering across the tape until it finds a pattern that it likes the look of the other thing for touring completeness is you must be able to have arbitrary amount of memory at the very basic level you must be able to have a long enough tape in either direction and on modern machines what that means is the totality of the ram that you possess you must be able to get as much memory as the problem needs so that's the fundamental thing then as much memory as you need and conditional branching and at the bedrock that is what you absolutely must have if a turing machine has in principle unlimited memory yeah none of our computers are touring machines then sean i'm so glad you asked that question and i didn't prompt you i didn't prime you in any way but yes um you can say that absolutely none of our so-called infinitely powerful turing machines can be because they've all got finite memory and if you go back to the chomsky hierarchy you will find if you can have arbitrary amounts of memory and if things might go on forever and you never know whether they're going to terminate or not in the general case then you're in chomsky type zero the moment you say ah but it's got to terminate within a finite amount of memory you're down in chomsky type one so you can say yes essentially finiteness of memory enforces that restriction on you anyway down to type one instead of type zero first of all what does a turing machine actually look like what does it do so here we are then this is we ask it a question and it will give us an answer yes or no these

Channel: Computerphile

Views: 310,987

Keywords: computers, computerphile, computer, science, turing complete, computer science, Professor David Brailsford, University of Nottingham, Charles Babbage, Alan Turing, Turing Machine

Id: RPQD7-AOjMI

Length: 6min 26sec (386 seconds)

Published: Tue Jul 05 2016