The Touring Machine: A Fundamental Concept in Computer Science

A touring 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. 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 touring program with all its zeros and ones may be 10 trillion times longer than your computer program I don't know, but in principle, it can do exactly the same.

In fact, some people argue that actually although it was Turing that made bringing this all to our attention in the late 1930s 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 babage said well that's just like a calculator that you have in your top pocket but weighs about 10 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.

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

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 a sequence of instructions uh 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-tos 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, really, you have got to have go-to statements which say I'm here at location 88 or whatever now jump off to location 200.

For a touring machine to be complete, it must be able to have an 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 that 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.

The Question of Completeness

Sean, I'm so glad you ask that question, and I didn't prompt you in any way but yes um you can say that absolutely none of our socalled infinitely powerful computing machines can be because they've all got finite memory and if you go back to the Chomsky hierarchy, you will find.

"WEBVTTKind: captionsLanguage: enthere's one thing that we keep coming back to and this idea of touring 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 cing complete well obvious first example is that every programming language you're familiar with um I mean we'll refer to The Usual Suspects forr basic Pascal cobal C C++ Java they are all touring complete so what fundamentally does a thing have to be in order to be touring complete and the answer is it needs to be able to do everything that a touring machine can do mercifully we have made several videos on this topic some from me some from my colleague Mark Joo and we have visited quite a lot of these issues just a recap a touring machine is thought of as an endless infinite piece of tape and it has a readr 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 is powerful enough to compute anything that can be computed admittedly your low-level touring program with all its zeros and ones may be 10 trillion times longer than your compy 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 babage 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 babage 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 Cog Wheels he went on and said I want to do something that really can compute in the way that a 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 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 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 a sequence of instructions uh that immediately follow but on the other hand if the lse 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-tos 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 uh in that you might stay in this part of the tape you might jump off somewhere else we've seen on the touring machine videos It's Perfectly possible to get your read R 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 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 touring machine has in principle unlimited memory yeah none of our computers are touring machines then Sean I'm so glad you ask that question and I didn't prompt you I didn't pre you in any way but yes um you can say that absolutely none of our socalled infinitely powerful cheing 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 in Chomsky type one so he 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 touring 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 nothere's one thing that we keep coming back to and this idea of touring 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 cing complete well obvious first example is that every programming language you're familiar with um I mean we'll refer to The Usual Suspects forr basic Pascal cobal C C++ Java they are all touring complete so what fundamentally does a thing have to be in order to be touring complete and the answer is it needs to be able to do everything that a touring machine can do mercifully we have made several videos on this topic some from me some from my colleague Mark Joo and we have visited quite a lot of these issues just a recap a touring machine is thought of as an endless infinite piece of tape and it has a readr 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 is powerful enough to compute anything that can be computed admittedly your low-level touring program with all its zeros and ones may be 10 trillion times longer than your compy 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 babage 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 babage 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 Cog Wheels he went on and said I want to do something that really can compute in the way that a 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 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 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 a sequence of instructions uh that immediately follow but on the other hand if the lse 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-tos 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 uh in that you might stay in this part of the tape you might jump off somewhere else we've seen on the touring machine videos It's Perfectly possible to get your read R 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 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 touring machine has in principle unlimited memory yeah none of our computers are touring machines then Sean I'm so glad you ask that question and I didn't prompt you I didn't pre you in any way but yes um you can say that absolutely none of our socalled infinitely powerful cheing 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 in Chomsky type one so he 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 touring 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\n"