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

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.

Brainfuck <3

Is there a video on goto?

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.

I love truly enthusiastic teachers, they make everything so much more interesting.

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!

What?? No mention of HTML at all?? Well there is nothing for me to argue about this time.

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

I never understod why a Turing Machine needs an infinity amount of tape/memory, really

Is a quantum computer Turing complete?

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.

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…

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

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.

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

1080p50?!? are we not worth the extra 10 fps?

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?

are there ANY programming languages that are NOT turing complete?

Is the Turing Phone Turing Complete?

Upvote because Fortran was the first language named.

GOTO, or "How to spaghettify your code". 🙂

Kind regards,

Meta Custom Computers

Pretty cool. So basically it's just if statements?

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.

Oh, now I understand all those "My X is Turing complete" jokes.

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

You should also do a video on how to prove if something is turing complete.

your mom is turing complete

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

Turing and even Babbage, and not even a mention of poor underrated Alonzo Church.

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 ofas 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.)what happend to your finger?

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.

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.

Babbage is one of my favorite names. So great.

it's quite annoying that u can't mention brainfuck because of how obscene that language's name is

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?

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…

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

He's a linguistician

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

is English Turing Complete? lol I'm so funny eh?

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.

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.

Ah, goto was monster. Gosub or just calling functions in OOP is much better.

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.

Ohh, look! It's that 'HTML is a programming language' guy!

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

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

lol the continues change between 50 fps and 30 fps (or is it 24?)

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.

First off, while conditional

branchingis sufficientfor turing completeness, it isn't necessary – conditionalexecutionas 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

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

regularlanguages) 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.goto 6:09 -> "type 1 instead of type 0" ->

keypress 1-> goto 0:382: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}?

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

+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!

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?

Are humans Turing Machines? Do we have infinite memory to compute?

Sad to see the lambda calculus go unmentioned even though it was discovered before the Turing machine.

Professor, are you ready to confess that HTML is not a programming language? Confess! Confess!

Please do a video on NTRUEncrypt

I have done french subtitle for the video, but dont know how it work

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.

Tosh.0 – Web Redemption – Professor Brailsford programing language

P = NP

*flies away*Would you do a section on esoteric programming languages?

Loving these videos, keep it up!

Does the smart devices we are using are smart because they are using Turing Complete?

please. add the subtitles

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…

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?

I've seen this explained a few times, but this is the first time I think I've actually understood.

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…

Which language is not Turing complete?

Dissonance: Watching this video after watching the one where he insists HTML is a programming language.

How do products such as this get thumbs down?

Am I Turing complete ?

"The usual suspects: Fortran, Basic, Pascal, Cobol". Professor Brasilford is really showing his age there; it's great.

Nice vid – thankyou

BrainFuck language is turing complete

XDWow!!! 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.

mentions Babbage and forgets Ada Lovelace

Powerpoint is also turing complete

Came here the first time because of school. Now I'm back because of Ethereum!

4:43 Magic occurs & you can hear his pen even when it’s not on the page!

Damn I just learned a lot.

Brainf**k is probably the simplest Turing complete language

no such thing as needx, no worry no matter what. nst as topix or not or so x, argue anyx no mattter what

This is the ideal male body. You may not like it, but this is what peak performance looks like.

Powerpoint is turing complete

Let that sink in

parallel, series ,inverter.

Hello to everyone watching this video now because the lab session was cancelled.

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.

How about church complete.

my microwave is Turing complete.

i can input anything and it will return an answer

wrg

I just love him.

Thanks for making

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.

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)

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.