Turing Complete – Computerphile


>>Sean: There’s one thing that we keep coming
back to. It’s this idea of Turing Complete. What does it mean and why do we need to
worry about it?>>DFB: Yeah! what does it mean to say “Is a
language – it’s usually, in this context, a programming language – is, or is not, Turing
Complete?” Well, the obvious first example is that every
programming language you’re familiar with I mean we’ll refer to the usual suspects:
Fortran, Basic, Pascal, Cobol, C, C++, 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 can 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 may be ten trillion times longer than your
compiled C program – I don’t know – but in principle it can do exactly the same. Some people argue that
actually although it was Turing that brought this all to our attention,
in the late thirties, with the work he did, in some way, 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 ten tons and full of cog wheels! But even
just using cog wheels 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 it’s
got a zero in itIi’m going to do that thing. So it’s this sort of two-way choice that
an if-then-else statement can give you. 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, resultant side-
effect of that it also implicitly means that you’ve got 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 that
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 have done assembler will know that 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 Turing Completeness is you must be able
to have arbitrary amounts of memory. At the very basic level you must be able to
have a long enough tape in either direction and our 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.
>>Sean: So, if a Turing Machine has, in principle, unlimited memory – none of our
computers are Turing Machines, then?>>DFB: 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, 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 0. But the moment you say “Ah! but it’s got to
terminate within a finite amount of memory you’re down in Chomsky Type 1. So
you can say “Yes, essentially finiteness of memory forces that restriction on
you anyway – down to Type 1 instead of Type 0”.

100 thoughts on “Turing Complete – Computerphile

  1. To a computer scientist, watching Brailsford is like watching porn: you already know what's going to happen, you know you're not going to learn anything new, but when you see that particular sexy cutie in a thumbnail, you immediately click it because it's going to be SO GOOD.

    I'd be chuffed to sprinkles if you would make him explain homoiconicity.

  2. Does the hypothetical "tape" go backwards to allow for a loop? It doesn't seem like a real tape machine could practically auto-reverse or rewind quite as often as needed without breaking down.

  3. I hate that theoretical, abstract, academic thinking in IT. It basically doesn't move IT further in any way. Lets teach people more about everyday problems they face in real project, like structuring your code, DRY, SOLID, Patterns, UML and other tools they will use in real life. They are awesome and pretty much not understood well in general. Or think theoretically about future, not past!

  4. Nice video. But when Professor Brailsford mentioned Charles Babbage, I hoped he mentioned Lady Ada Lovelace as well, but he didn't 🙁

  5. I've been waiting for this video for a while. But I thought that another condition would be to have a loop or recursion? Also could've mentioned Turing tarpits.

  6. I always choose which computerphile video to watch based on the face in the thumbnail… This guy is one of the faces I will always click on…

  7. I don't think it actually matters that we only have finite hardware. What is described is a property of a programming language. So the question is not "Can we with our resources build it to be an exact TM?". But rather: "Does the language behave like the software of a TM?". So in the example of finite hardware the requirement to the language should in my opinion just be: "Could it handle an infinite hardware and still meet the other TM requirements?"

  8. 5:25 That's look of a teacher who's is relieved to see his student finally learning something after how many Professor Brailsford videos has it been now? Nice work Sean.

  9. If there are a finite number of particles in the universe, wouldn't that mean that a Turing complete machine is impossible?

  10. I understood from an MIT computer science lecture online that a program was considered "Turing Complete" when, for example, a for loop was used, or a degree of recursion used to solve a computational problem. The program can loop an infinite amount of times to meet a condition or compute output continuously, this is in contrast to the output of a program being proportonal to the length of a program. This distinction was my understanding of Turing Completeness. I would argue it has less to do with the language used but the approach and elements used to solving a computational problem. Conditionality and moving between arbitrary areas of memory would both be needed as you explained. Not quite sure i understand the infinite tape reference, is this to illustrate the potential for an infinite amount of output?

  11. Unfortunately he only explains what a Turing machine is without saying what it means to be Turing complete. At the root of the problem when we say something is Turing complete we are saying computationally universal. Meaning it can calculate anything that is calculable. This distances it from the very abstract yet mechanical Turing machine. Like he said we could call it Babbage complete, or Church complete, or Java complete etc. I personally find Lambda Calculus which was defined before the Turing machine more useful for writing programs to than a Turing machine. But both are equal in a computability sense.

  12. Out of curiosity, how is it proved that a turing machine can compute anything that can possibly be computed?

  13. "All programming languages you're familiar with […], they're all Turing-complete." So, picking up where we left off, HTML, right? …… That's what I thought. Well, I rest my case then.

  14. Strictly speaking, of course, every computer we have is a finite-state machine. They go from one state to the next by means of electrical signals (including clock pulses) coming in. Computers are not normally thought of as finite-state machines largely because it would be impractical to try to draw a state diagram. (There are more possible states than there are atoms in the known universe. But it is still a finite number.)

  15. I strongly disagree with the assertion that if a computer does not have an infinite amount of memory then it is not Turing complete. By pushing the limits of time and memory to infinity, what Alan Turing was stating about his machine was that these two variables are unimportant to what defines a universal machine. After all, if a Turing machine runs out of memory, a human operator (or another Turing machine) can come along and swap out the contents of the memory that aren't important to do the next few cycles of the calculation with blank memory so that the machine can keep running. As so long as the human operator or second Turing machine can continue to swap out the contents of the memory, the Turing machine can be said to effectively have an infinite amount of memory. This despite the fact that it only has a finite amount of memory at any discrete point in time.

  16. when he says "can compute anything a computer can do", what exactly does he mean? as in, what all can a computer in its essence actually do? control flow and arithmetic? Or would he be referring to the different categories of opcodes?

    this might have an overarching name that I am just not aware of that is about this, maybe "elements of computing" or something like that… i would love to read through some links if anyone can send me links on any of this. I may be on the right track with the opcodes part.

    and to delve even deeper, why is it that a computer NEEDS to do these "elements of computing" (and why was it determined that these "elements" needed to be the actual elements)? this is probably really at the core of what it actually means for a computer to be a computer.

  17. If the amount of memory available is finite, wouldn't the computer be in Chomsky's type 3 (finite state automata or regular languages) instead of type 1?

  18. How powerful does a regex engine need to be to be Turning complete? Obviously perl's is (you can call function within the regex), but is PCRE, ERE, (and I'm guessing not) BRE…? I'm thinking any engine that has a match counter mechanism might pass the test – not sure if there is any reading on this…

  19. ". . . you can show that just the ability to write on a tape patterns of 0s and 1s is powerful enough to compute anything that can be computed."

    Strictly speaking, this isn't true. The Church-Turing thesis isn't a theorem — it's not even a mathematical conjecture — it's an assertion. It's not the kind of thing that can be expressed formally, so it can't be proven.

    Of course, we have good reason to believe it, since we've found lots of Turing-equivalent systems and no super-Turing systems, but it remains theoretically possible that super-Turing systems do exist.

  20. To me the definition of Turing completeness is that the output state is able to be relied on, given its input(s). Such a state is at least 1 bit of memory

  21. Near the end, there was a mistake stated about how memory is finite. The ability for a LANGUAGE to be Turing Complete is the ability for that language to run a TM tape machine, full stop….there is no infinite memory requirement of the statement. On top of that, the software that runs on a computer is not the piece that is being limited by memory, it is the hardware that is limiting….and just as you can increase the length of the TM tape machine towards infinite, you can add bigger HDD space to infinite as well. This means ALL computers possess the ability for type 0 inclusion, the means of which humans put the machines together is what places it into type 1….the languages itself are not at fault of the limitations.

  22. I don't know where I've heard it but I thought that a part of being turing complete meant that if any one opcode/statement was removed the same result could still be achieved using a conjunction of other opcodes/statements in the same system.
    I could be thinking of something completely different.

  23. I was always taught a TM has an 'unbounded' tape, not an infinite tape, whereby your tape is finite length but you can always add another bit to it whenever needed. The point is that at any individual point in time, an unbounded tape will have finite length.

  24. The language is Turning complete (C doesn't say you can only use this much memory) but the device it runs on puts on other limitations

  25. Endless and infinite mean exactly the same thing. So saying "endless, infinite piece of tape" is quite redundant.

  26. It would be nice if this video discussed the advantages and disadvantages of Turing-complete systems. Right now it's not much more than a recap of Turing machines.

  27. First off, while conditional branching is sufficient for turing completeness, it isn't necessary – conditional execution as well as repetition are the necessary and sufficient conditions. Conditional branching just happens to provide both and be useful in everyday computers.
    But computational classes aren't about modern computer architecture, it's automata and computability. Game of Life is well known to be turing complete, using just a single check repeated over and over – there's nothing analogous to goto or if there.

    Second, you implied that a computer can recognize arbitrary context-sensitive languages, which is simply not true. In fact, there are even finite languages (a strict subset of the regular languages) which no computer in existence can reasonably recognize (say any language {s, t} where |s| = |t| = 10^5000). As run on any existing computer, no language is even strictly stronger than the regular languages.

  28. 2:56 obviously pressing "j" jumps backwards on the tape, pressing "k" toggles it's state, and pressing "l" jumps forwards on the tape. Does that make this video(2:00) {youtube complete}?

  29. I've probably said this before but the animations are extremely helpful in understanding what is being explained!

  30. +Computerphile could you have Professor Brailsford explain if the Ackermann's function would compute with inputs that are complex numbers? Just a question I'm curious about. Thanks for the great videos!

  31. I'm a designer (noob at programming) currently developing AI for my Unreal Engine video game. I'm familiar with what he's saying from a node(visual) perspective. My question is if I set up a series of events branching off each other to use a loop, does that mean that either my AI systen, the game engine or computer running everything is "turing complete"? In other words, is there a destinction between hardware vs code?

  32. Turing-complete doesn't say anything about I/O. Practical languages don't need infinite memory space, but they do need some form of I/O.

  33. I want to just sit next this guy and listen to whatever he ramble about. I dont take up much space, and I smell nice…

  34. so when i complete question N on my tax form, and it says "if no, go to question" N+3, and also has such things as "attach extra pages where required", does this mean my tax form is turing complete?

  35. Regarding the idea of 'theoretically infinite memory', as soon as you add some kind of external I/O storage device, have you not qualified, as the program and data can be stored and split onto as many extra storage media as you require. It might not be convenient, but it would work…

  36. Wow!!! Infinite memory? Why would you need that? If you need infinite memory most likely the outcome is undefined. The process will never end therefore no outcome. I do not think it has meaning in the physical world.

  37. when he says you must have arbitrary amount of memory (4:50) he runs out of paper to write the whole thing in a straight line. funny.

  38. Babbage was a great computer scientist.
    But I think that Turing was the first one, who broke through classical "only mechanical" type of computing machine, and made first (in theory) true cyberphysical computing machine.

  39. ironically, you're using what look like html tags in your graphics as dude mentions all the programming languages that are turing complete — html is not, if you consider it a language (which it really isnt)

  40. Turing completeness alone is not enough to pass the Turing test. In order to reason like a human, an AI machine must be able, not only to perform math, logic and branching on data but, to orchestrate the process, and to observe and remember the process of orchestration, and improve it.

Leave a Reply

Your email address will not be published. Required fields are marked *