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”.

Add a Comment

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