Video 2-3: Models of computation: Turing Machines

0:02 In the next section, we'll look at Turing machines. After studying the word RAM model for a bit and finding that it is a little too detailed and complex, um let's go back to uh a model that's that's really designed to be as simple as possible. Uh we talked about uh this yesterday already a bit. Um there's many more models of computation that you could study and indeed uh a theoretical computer science course often spends a third or so on studying different formalisms of what computation can be and then proving that they're all equivalent in the sense that they compute uh the same set of functions. So there are these famous undecidable or uncomputable problems like the halting problem uh which are not effectively computable with any of those formalisms. Uh but apart from those all the functions that are computable on any of these models are computable on all of the other models too. And you can the list you can make much bigger. There's uh there's fun things like um the game of life happens to be touring complete.

1:12 um cellular automa as a general concept if you pick an interesting one are are turing complete. Uh so all of these um any any programming language that is interesting will be Turing complete and so is is not just able to express all of these models but the the other direction too. They can all simulate each other. And there's the church Turing thesis that says whatever model you can you come up with as long as it formalizes something that means effectively computable uh it'll be equivalent to those in terms of the functions that they compute. Now this is not provable because it it's not clear uh how to formally grasp all possible ways to define this. So it's just a a kind of working hypothesis, but it hasn't been falsified. And there's an extended version of this that takes running time into account. Many of these models have very strange and different notions of time. We'll look at the one for Turing machines. You've seen the one for for the word RAM. I didn't even bother to list that, but it's it's kind of a um a register machine. Cool. Not on the list.

2:28 Uh but of course word RAM is one of those. Um in a in a cellular automata time is a very different thing because many things happen in parallel. Despite all of that if you look at the models that we have they can simulate each other with polomial overhead. Again this is I left I leave this vague for now. uh the extended church steering thesis is that whatever model you can come up with it'll be able to simulate all the others with polomial overhead and vice versa that's a stronger state statement and indeed it's not clear if this is true for quantum computers so for all the other models I think is uh is clear or proven to a degree um for quantum computers I think this is unclear and also uh what I'm saying here is about theoretical models for quantum computers. None of the existing ones is really exciting if you look at what they actually can solve in terms of practical problems. Well, different story. Um, but they might be the exception to this extended church Turing thesis. What we'll look at is uh the historically oldest and simplest of these of these models.

3:47 Uh, I love this. Um the paper was received in May 36 and read November 36. I suppose this means published um and in between there was a bit of peer review and and and type setting and so on. Uh so this is Alan Turing's paper where he introduced Turing machines and also uh showed that this this holding problem uh that's the German phrase that was used at the time because Kurt Girdle coined the term and so on. Uh but I I really have to cut the history lesson short. Uh what what Alan Turing set out to do was formalize what you can do with pen and paper and as a as a person computing things step by step. If he really thought about the algorithms you learn in primary school for doing uh doing arithmetic that's what he had in mind and he thought what how can I possibly generalize this to the uh the biggest extent that's what uh what he came up with and uh well some some geeks build a a physical version which is not by any means uh the most reasonable way to build an actual computer but it's possible.

5:01 Okay. And of course there also invite circulation. I spent the since la until last summer I spent five years in in Britain. So this is a a picture I took of an actual note uh with Alan Turing on it and he invented some shortorthhand for his Turing machines. That's one what's on the bill otherwise it's a bit hard to decipher. Uh but uh yeah um they're very proud of uh L Turing and for a good reason. Informally, very briefly, what is a Turing machine? Uh it has this conceptually infinite tape like in this picture. You can extend it on both ends as as much as you need. It has a single position that it can look at and it it reads one symbol there and then uh it has a finite control which contains a finite number of different states. This is a piece of memory, working memory if you want. And these states encode the whole memory of the Turing machine outside of the tape. And in each time step, it reads one symbol and it is in a certain state that tells you where you are in this table. And then the right right hand side tells you what to do, which is write a different symbol at this cell in the on the tape. Move your read right head one position or stay and good go to a new state and that's all you can do. Uh there's a special state where you terminate the computation and that's it. So it's very restricted. Uh and it's at first not clear why this would be powerful enough to do all computation imaginable. Uh but it turns out it is and it's the same expressive power as any programming language.

6:50 The goal of this part though is to formally define this make it a bit more um rigorous. So for that a touring machine is really a collection of of all these pieces of information is a finite set of states that's capital Q. It's an input alphabet that's uh the alphabet the symbols that you can write your input onto the tape initially. There's a tape alphabet which is a bit bigger. So it contains the input alphabet but it might have additional symbols that you allow the machine to write on the tape for temporary storage. Uh then there's a transition function and there's two cases. The normal way computers work would really be a deterministic Turing machine where the transition function like in the example here is unambiguous. If you're in a certain position um combination of a current state and a tape symbol that you currently read, there's a single thing you do and that's given by this function delta. It maps from the states that are not the holding state and the current tape symbol to a new state, a new symbol that you write and a movement of the right of the readr head. But we'll also need nondeterministic Turing machines which are really strange beasts. They're not intuitive. They're not physically producable. Um, but they're sensible to define. And you'll see why soon if you don't know already. In this case, we also have a function that maps from a current state and a tape symbol to something. But now that something is a whole set of possible next states, and the computation will have to somehow know which one to pick. The other pieces we need is some initial state so that we know what's the state called where we start. Uh we need a blank symbol. So the tape is initially filled and because it's infinite we don't want to do this uh explicitly. So we just assume it's filled with these blank symbols initially. Um that's part of the tapes alphabet. And we have a special state that means if you ever reach this state then the computation stops.

9:03 What I defined here is is basically just the syntax in in logic speak. I'm just defining in set theoretic notion notation certain things. I've already given you the meaning behind them. Uh but technically that's that's separate and I'm defining the meaning a bit more rigorously will take one or two slides. Uh we've already talked about the steps of computation. If I'm in a current state and I read a current symbol, then this transition function or transition relation uh tells me what the new state is, what symbol I write on the tape, and where I move the head. And here's the semantics spelled out. I essentially verbalized that on the previous slide. Um, sometimes it's useful to distinguish between the syntax, which is what can you write down, but these are just empty symbols with no meaning, and the semantics, which is what's the meaning behind it. And I I tried to separate this here a little bit. Again, the important part to keep in mind, a deterministic Turing machine has a uniquely determined next action, whereas a nondeterministic Turing machine may have several ones. And for now, this is just the definition. It tells you there's several things you c you could possibly do, and it doesn't tell you which one to actually execute.

10:28 Now the memory of the Turing machine is just the state as I said but the uh state of the world includes this infinite tape. So if we want to specify the full computation we'll also have to capture what's on the tape and that's done with the notion of a configuration. Configuration is kind of a a snapshot of the entire world as seen from the from the eyes of a Turing machine. And we write this as one long string which is just a a shortand uh there's a string. So this the star means zero or an arbitrary number of uh occurrences of letters from this alphabet. Uh so gamma star means as many tape symbols as you like followed by one state followed by potentially more tape symbols. So each configuration will have this form alpha Q gamma where Q is a state and then alpha beta together uh that should be gamma I guess or rather the first one should be beta. So these two together are the entire tape content read from left to right and uh they're separated so that you can say where the read write head is. So it's kind of very concise notation. This position of the state tells you the first symbol of beta is where the read write head sits currently. Other than that it's just a a very concise way to capture the whole state of the system. And then we can define what a computation looks like.

12:06 It's a relation between configurations. The computation tells you you're currently in one world. Then you can do one computational step and that transforms the world into a slightly different world. Most of the tape will not be modified. As you see here, these A's remain unchanged. In the first case where you don't move the read write head don't move.

12:37 uh then you just replace this first symbol of B of of beta um with a new symbol C given in the transition function and you go to a new state Q prime instead of Q and the other two cases are similar in you just have to model that the the read right head moves. If you move to the right it means this symbol that you wrote is then on the left of the read right head. So you basically swap those two. The rest is the same. Uh whereas if you move to the left, you have this symbol here that you wrote and then you move once to the left. So you're sitting on this symbol now. So we have to move Q prime one position left. Okay? It's nothing really deep, but I want you to get a little into um into touch with with formal notations just because they make it possible to be super rigorous about things.

13:36 uh there's there's two cases um that are not captured by this general case which is just the boundary cases. If you if you're at the end of the tape content that you specified, we imagine the tape to be infinite but it is filled with these blank symbols. So no need to write infinitely many blank symbols left and right. We don't do that. Instead, we just fill up with new blank symbols as needed when we move further left or further right than than we've previously been. And that's what these two cases capture. If you're at the end of the the encoded tape symbol and you move further to the right, then you just uh add a new tape uh blank symbol. And the same on the left. If you're currently sitting on the leftmost symbol that you've explicitly captured, then you add another blank symbol if you further move left. Okay, this way a configuration is always finite at least if it has been running for finite time. The Turing machine cannot have done more damage to the tape than change a finite number of symbols. But it is conceptually infinite. You can make more space as you need it whenever you reach the boundary. Okay, good. That's configurations and the computation relation.

14:49 uh relation here just means there's pairs of configurations that you put in relation so that you can go from here to here in one step. It's not a function that you go from here always to this one because we have these nondeterministic machines. They mean there's several possible next steps. Uh here's an example from the one before where I just spelled out the configuration. You can just read this up for yourself. Um, and just what what I said before, uh, this entirely captures the state of the world for the Turing machine. There's nothing else that's ever relevant for the computation that wouldn't be in the configuration. Okay, now we know uh how these how these steering machines work. Now we want them to do something useful. So we want the the outside API of a of a Turing machine and that's the function that's computed by it. So we're given some Turing machine again this lovely seven tpple just as a convenient shortand to write this down. Um now this machine M when I give it an input X what that means is I initially write this input on the tape and nothing else. And so I can define what this function is now in a very convenient and short way. The function is all possible strings y that I can reach if I start in the starting state of the machine with x on the tape and nothing else. And I can with a an arbitrarily long sequence of steps. So the star again means the transitive reflexive closure in in fancy speak but really a an arbitrary number of executions or iterations of this relation. I can reach from this the holding state with Y to the right. So implicitly I'm telling you here how we are supposed to use during machines. Put the input on the tape. Put the read write head on the first symbol of the input. let it run and you want it to reach the halting state and be at the beginning of the output. If it does anything else, if it stops and is in the middle of the output, we're not formally allowing this this kind of an illegal behavior. Okay, so we're we're a bit strict maybe, but um it's convenient to define it that way and you can always modify your machine to move back to the beginning if that's what you want.

17:26 This definition works for both deterministic and nondeterministic machines. For deterministic ones, we'll always have a single element in this set because every step is clearly defined. Uh you can only go in one way. Uh it's lesser equal one because if you if you uh screw up the programming of the machine, it might never reach the halting state and then there's maybe no such why so that it reaches a halting state. You've programmed an infinite loop, right? We've all done it before. Um, if that's the case, if we have a deterministic machine, we'll just write it as a function and omit be a bit sloppy with the uh set notation. If we know that there's a single element in the set, we'll just write it like that. For a nondeterministic machine, it could be that there's several computations and they produce different outputs. For now, we'll accept that. Okay. Now we know how a Turing machine can compute a function. Now we need to talk about the cost of that and we can define time and space in this uh world of configurations as well. Time is kind of easy. It's uh this is the important bit. Would have wanted to do that in red maybe. Uh so it just says the time that the machine takes on this input X is essentially how many computational steps it needs to reach the halting state. Now there's a catch. There's an infom around this because it could be a non-deterministic machine that has several computations.

19:03 Then we take the longest running one. Um we also include if this is if you somehow mess up and it doesn't ever reach a halting state or is is even completely broken then maybe uh you need this this catch all case of of going zero but it could be infinity as the running time if you run into an infinite loop.

19:28 uh space is a little more uh subtle maybe there we say it's this the size of the tape content that you ever can produce as an intermediate state you start from the starting state you somehow get to this position where you have alpha beta on the tape and then you keep going until some halting state and here I have to restrict that we don't have uh just a lot of blank symbols in there uh the way we defined the configured the the relation might not be needed because we only move with the read write head. So I think you could drop this either way is as much tape as is as you've used right is intuitive too I guess. Uh, and my point on this slide is I can in one line each rigorously define what time cost and space cost is for the model. That's why I went through all the pain of formalizing things. Um, once you've done that, you can be very clear about what these definitions mean without having to fluff it. There's this catch uh there's this tricky cases for nondeterministic machines. We will soon get rid of those.

20:48 Um, but for now they're included in the definitions because you can present me a a completely uh useless machine and the definitions are supposed to still make sense. Now we're coming back to uh TCS theoretical computer science where you would have spent a lot of time talking about languages formal languages which are just sets of strings and um we'll also use that in complexity theory. So uh I've talked about the function computed by a Turing machine. We can use that formalism to define the language accepted by a Turing machine. Uh formally just say the language is a set of strings. So it has a characteristic function. It's a function that is one if the input is part of the language and is zero otherwise. And so you can just have the machine compute that function. You give it a string and it either outputs one, then it's part of the language, or it outputs zero, then it's not part of the language. Here's the formal definition. Uh again, for nondeterministic machines, they might out output several different values. And so, let me stress this here again. Uh a word is part of the language accepted by a Turing machine. If there is a way to produce the output one, some way to produce the output one, there might be many other computations in a nondeterministic machine that produce other outputs. In particular, some might say no, it's not in the language output zero. As long as there's one computation that produces a one, it's part of the language. That is non-determinism in the way we use it.

22:32 There might be many ways for the machine to branch out. As long as there's one that accepts the word ging in the end, we treat it as part of the language.

22:50 Okay, a side remark on I think there's there's two slides on essentially these are the general definitions and you can produce many Turing machines that are annoying and don't make sense and are kind of broken. Uh so we'll uh we'll have two statements that say we can get rid of some of these awkward cases. Um one one thing I'll just throw in. You can define a Turing machine that has several tapes instead of just one and it can independently move a read write head on each of those K tapes. K is a fixed constant. So maybe five tapes. Okay. and then all the all the definitions have to be modified so that there's five positions at each point in time. Uh you can do this and it's sometimes more convenient uh to work on those machines. If you describe a computation if you have a single tape and you want to say uh count something in one place and do uh work on some other place, you always have to walk back and forth. And uh that's that's um a bit unrealistic uh that you can't access two pieces of information that are far apart. And so the K tapes allowed to do that. But lo and behold in terms of the running time there's not a huge difference if you are on the polomial versus super polomial uh side of things. So if you have a ktape turing machine um that accepts some language in a certain time f of n uh then you can also accept the language with a single tape and you might square the running time. Squaring the running time in in all practical terms is really bad. But uh as a theoretical construction it's fine. It just means we don't have to bother with several tapes for the for the definitions of what a computation is. But we could use several tapes to describe a computation and then invoke this result to uh say there is a way to do it with one tape. It's just going to be more tedious and a bit slower.

24:57 uh I wanted to throw in this this vocabulary here that models are polomially equivalent when they can do something like this when one can simulate the other where the time might blow up but only by a polomial amount. Okay, so far our touring machines might do stupid things like run in infinite loops. And for talking about algorithms and running time, that's inconvenient. We'll we'll want to speak about worst case running time. This makes it extra inconvenient if there's some computations that run forever. Um, and luckily for all of the things that we do in this module, we can exclude all those cases where they run forever. So we'll leave the general case for undecidable languages and all this behind. Um the definition of what what I mean by uh don't run in cycles is is this uh during machine is always terminating or computes a total function. Uh I'll try to use the always terminating. I find it a bit more intuitive.

26:07 Um if there's uh a way to bound the time it takes. So there's some function t. So that whenever I have uh a computation from some uh initial uh input and the initial state and I go through a sequence of computations, there has to be um an upper bound on how many steps I can possibly go. This basically ruling out infinite loops. That's all it does. Um but it also gives you a little more um because then uh we can speak about the running time which is bounded by this function t and that's a function of the size of the input the number of symbols in the input that's what we put into this function. So always terminating has these two sides. Uh there should be an upper bound on how long any computation can run but it also should be possible to reach the halting state. uh this part could be unfinished computations that somehow uh get stuck. This is only really possible for non-deterministic machines. Okay, for for all those uh nice machines always terminating, the time it takes to run uh on a specific input, remember that's the the worst number of steps you could possibly take will be at least one. you never do nothing and it will be at most this function of the input Okay, if you wonder um that's a definition and I can wish for my machines to be like that. Um there's more. You can also make them be like that and that's what this lema uh gives you. It's uh if you're given an arbitrary touring machine that might do all the stupid things I mentioned in particular, it might run in in infinite loops and I give you some function um with some mild side conditions. I'll I'll comment on that in a second. Uh the idea is that you want the machine to do at most t steps t of the input size and then stop for sure. And we the the lema says we can we can basically make it so by counting up to this this time steps and then stopping. Uh the formal way to say this is we're given one during machine as input and we produce a different machine as output which is always terminating and uh it simulates this original machine for exactly that many time steps at most and produces the output that it would have produced on the other machine. But if that machine doesn't finish in that time, it produces a special timeout uh output. And uh you can also bound how long it takes for this machine m prime to do so. Uh again we have this squaring of the time that we want.

29:09 And [Music] um I don't want the to do formal proof of this but the idea of how to build this M prime is that M prime first uh computes this function of the input size. So that's where the mild side condition come into the game. there must be another Turing machine that computes this function t for us and in a reasonable time. Uh so I can certainly compute the length of the input and count that as a binary number. Then I can pass that to this other machine. I can simulate what this other machine would have done to compute t and I can produce t as a una number. So just as many uh little ticks uh on my tape as t of the size of x is long and we can be creative. Let's put a little uh this is a a little watch, a little clock. So that's a symbol that I include in my in my uh alphabet. Why not? So this has to be part of my tape symbol for the machine M prime. Now the idea will be I'll produce as many time symbols as I'm allowed to spend time later on simulating the other machine. So I execute one step of the other machine by reproducing its transition function.

31:13 And then I'll delete one of those clock symbols. And when I run out of clock symbols, I have to output timeout. If the computation of m stops before then I also stop. Uh well there must be a way to compute the function t and uh in general not all functions are computable but if it's some polomial say n to the fifth uh there is a program that produces n to the fifth many ticks on a tape by for example nesting five four loops within each other. Right? for I from one to n for i from one to n i five times there's pardon how do we know there's no left uh well you can you can um it's a bit tedious to do it with the transition functions but it's possible in general you have a special state that says now I'm scanning left you have to say where the clocks go either on the left end of the tape or the right end whatever is more convenient doesn't make much difference uh the time Squaring comes from the fact that after each time step you simulate, you have to walk back to your clock symbols to remove one. And so the way the the distance you have to walk is at most the space usage of your machine M. And the space usage is actually at most the time because it just doesn't have more time to produce garbage. So there's a there's a a whole bunch of things I'm I'm skipping here.

33:01 That's that's the rough idea. Maybe you have a um yeah, let's let's leave it with a rough idea. Um I think the construction itself is is not as important. Um the the consequence for this part here is uh if we're only interested in the existence is there some way to do it on a touring machine with polomial running time then we can restrict our attention to these always terminating ones. Okay. Uh so again um flushing out this construction in full detail would take a bit more time and is fun. There's there's one construction in the book where they specify a complete machine. I think this construction is not in that book. Um once you've done a few of them, you get a feeling for what is easily doable, but it's tedious each time it takes ages to spell out the details.

34:07 Okay, so to sum up, uh, Turing machines are a model where it's relatively easy in a few slides to rigorously define what computation is, what running time is, what space cost is, and all that. Uh, the downside is some ways that you can write down a Turing machine make no sense. So you want to restrict to something more sensible at least these always terminating ones by simply forbidding you as the programmer to produce Turing machines that make very little sense. Uh but we have to make this as a as a second result. Um just to make that point explicit as well uh we talked about the cost to uh add two integers and I said the the ultimate answer is the word RAM model if you care about the the precise precise number of uh the precise time to add two numbers. Um if you stick with Turing machines, you're always going to end up with the logarithmic cost model or um so that's the way of saying the word size is constant and the input might be bigger. Uh because steering machines have a a finite alphabet. The tape symbol is finite whereas word rams effectively have a logarithmically sized well no uh their alphabet size is 2 to the w um well the kind of polomial nonpomial doesn't make a