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