Video 2-3: Turing Machines

0:02 The next section covers Turing machines, the historically oldest and still somewhat popular model for computation that is at the very end of the spectrum of simplicity of the model. Extremely inconvenient to work with and do anything with. Also not realistic in that it's not close to how modern computers work. So things might take longer on this machine than they would on any actual computer that we can build. But it because it's so simple and restricted, it makes proofs easier. And that's the main goal here.

0:34 Okay. Uh the word RAM is a bit too complicated, so let's simplify further. Um it turns out Turing machines are one of a whole zoo of different formulas it form formalisms for describing computation. I don't know um many of you will know certain subsets of these. Um they all have their pros and cons in in terms of describing some things more naturally and some things less naturally. The important thing is that they're essentially all equivalent in the sense that any function you can express in one of these formalisms, there is a way to express it in the other formalisms. And if you define what what execution time means in a sensible way, then you can even um translate this with a certain um polynomial overhead.

1:33 Uh so let me maybe be a bit more precise here. Uh all of these are proven to compute the same set of functions. So there's no algorithm that you can somehow give There's no function for which you can give a a computation any of these models, or any of the other models would not be able to express this. But that makes no assumption or makes no statement about the running time. And for some, maybe running time is even a bit awkward to define.

2:06 There's the thesis, the Church-Turing thesis, that this list is of course never complete. You can always invent a new way to compute, or you can invent your own favorite programming language that may be really strange. You can find esoteric languages um of any kind, and maybe you find joy in these. Uh the thesis here is that whatever you write down will be the same set of computable functions. Now, a stronger version of this, which may be a bit bit more uh flaky to justify, is that you can also simulate with polynomial overhead any of these models. That depends a lot on how you define running time. For the usual ones that we care about, this is true, though. So, we might as well stick with the Turing machines as an homage to uh Alan Turing who invented this, and also because they're somewhat um easy to understand.

3:03 So, Turing machines, they date back to 1936. There's the original paper. Uh and uh you can also build them in actual life, even though they're horrendously slow for anything. They're also in circulation. This is the 50-pound note in England. I don't know if you if you know. Um there's the there's there's Alan Turing on it, but there's also a compact representation of a Turing machine itself, which is unfortunately so compact that you need you need a blog post to understand what it does. It's um some shorthand notation that uh Turing himself invented for some of his proofs.

3:45 What does it do? A Turing machine has a finite control, so it's a finite state machine. It has a finite collection of things it can itself remember.

3:56 And everything else it needs to do is on a tape. This thing here, right? Thought to be essentially infinite or unboundedly long. You can extend in any direction as long as you wish. Think about if if the tape ends, then you glue another one to it and keep the machine running. Uh so, it can go in both directions as as far as you wish. And initially these these uh entries are filled with some blank symbol. And what the Turing machine can do is essentially write different symbols there. But everything in the machine needs to be finite. A fixed set of states that you can be in. So, there's a Here, the states are numbered 0, 1, and then there's a special state that terminates. There's just these two, Q0 and Q1. Then the symbol of allowed letters on the tape is finite. It's this blank symbol and maybe a few others. Here, it's A and B on top of that.

4:58 Uh and that's pretty much it. And in each step, a machine that is currently in some state and reads at a certain position. Uh I didn't mention the read-write head. You're always looking at one cell in this tape. You read a certain symbol. You're in a certain state that tells you what symbol to write instead of the current one. And then what to do with your read-write head. Move it either one position left, one position right, or stay in place. And you can go to a new state. And that is all. And the beauty of the model is that this can express any computation. Even though a bit uh with a bit of overhead.

5:42 Uh anyone has who has not seen something like this before? Who has seen something like this before? Okay. Uh the formal definition, maybe we can go over this a bit quicker. Is essentially giving all of these a formal name and then a set theoretic meaning. Um set theoretic meaning. So, the states are numbered Q. Uh the input alphabet, that's what you're you're fed into the machine. Uh which initially is on the tape. The tape alphabet could allow a few extra symbols. Then this table I had on the slide is given by a transition function or relation. Um in this case here, the table, there was a unique entry, a single entry for each combination of state and tape symbol. In general, you allow there to be ambiguity. Then it's a non-deterministic uh Turing machine where you have potentially several things you could have done. We'll come back to that. Um you start in some initial state and there's some initial symbol on the tape.

6:45 And then there's a special state halt, which if you ever reach that, the whole thing just stops. Um in formal logic, you could say this is the syntax. It tells you what you can write down, but it doesn't tell you what it means. The semantic is missing. And that's the next step. Um The semantic of this means that you can do computational steps using the table as I as I showed you a bit. So, each step in in uh computation takes um a current state and reads one symbol from the tape. This is the picture from before, right? I'm sitting here. And I read this letter A and I'm currently in state Q. Now, uh the update, what the one step that I do is go to a different state Q prime.

7:38 Write this letter B there instead of the A and then move my read-write head left, right, or stay. So, you maybe move one position to the right.

7:52 Uh the notation is just as in the table before. Uh for a deterministic Turing machine where this delta is a is a unique function. So, there's exactly one successor state for each combination of Q and A. Every step of the computation is predetermined. Um otherwise, if it's a relation where you have choice, then you may have several options.

8:22 So, this defines one computational step, but it has a bit of a a problem in terms of uh forgetting the tape. We'd like to have a concise way to say, "This is what the Turing machine does." And that needs to encode the tape contents. Otherwise, we're not getting the whole picture. Uh this this says, "Okay, I'm reading an A, but where does this A come from?" And if I move one position to the right, what what was there? Um I've forgotten, right? Uh so, to properly define what the computation looks like, you need the tape as well. And a a concise way to to uh capture that is via this notion of a configuration for the entire machine now. And you can concisely write this as a little string, namely a state that you currently have, and then you give the tape content split at the position where you're where your read-write head is. So, these configurations always have this form, some prefix alpha, then a state, and then some suffix beta.

9:23 And alpha beta together is the tape content, and the head sits on the first symbol of beta. So, in pictures, right? Um this is alpha, this is beta, then my uh state is here and I'm looking at this first entry of beta. That's just a convention, but it means you can very concisely write down uh what um the current state of the machine is. And then one step of computation takes one such configuration and produces another one. And here's the definition that follows precisely this process from before. I have some tape content left and right of the current head. And then it depends where I move on what the successor configuration is. If I don't move, then my Q stays where it is. It's updated to the news new state. And this first symbol here after the Q, that's the position of the read-write head. So, if I write a new symbol, it goes here.

10:26 Okay? And right and left are the same except that now if you move right, you swap spaces with this first symbol of the tape. And if you move left, then this last symbol of alpha becomes the first of beta.

10:48 >> Uh there's one little caveat that I should point out with the formal definition. Because we allow to read as far far to the left or to the right as the machine desires or needs, we may at some point have to fill in new blank symbols for those definitions here to make sense. If you think about it uh carefully, then you see there's a bit of a problem with swapping say the first the last letter of alpha to the right if alpha were empty. What this means is that you always fill up with as many of these gap symbols as you need for the definition to make sense. But then afterwards, you delete the leading and trailing gap symbols again. That's only important for some of the formal definitions that come that follow. But this is the most convenient way to do it proper. Okay? So, a configuration in principle is any such string and it could have leading and trailing gap symbols, but we ignore those for the definitions.

11:56 Uh here's again an example from before and one specific configuration that describes the state um from the example. I think there's not much going on there other than having a very specific notation so that you can conveniently and concisely represent things. Okay.

12:25 Now, we have machines and they can do computations or they can relate configurations and thereby chain together computational steps. Uh now we want to define the semantic of a machine, which means what does it do? What does it compute from the outside? Um and for that um we have to carefully dissect this little formula here. We start in the starting state. Q0 was the special state that we initially start in. And we put the input of a function that we want to compute into the initial tape. And the read-write head sits on the first position, the first letter of this input X.

13:06 By the way, all of Turing machines always just deal with strings by definition, right? They have characters that they get as input. This one, they get characters written on their tape and they move characters around and they they can produce an output. Um we'll come to that. Uh namely, whatever they leave on the tape when they stop. So, they always deal with strings.

13:33 Which means the function that a Turing machine may compute is also um defined as a mapping from some strings to other strings. So, it's a function that takes a string and outputs another string. And if we have such a function a given machine computes this function if for every input to the function I could give, if I start the Turing machine with initial state and position on the first letter, there's a way to get to the halting state and the precise the the appropriate output.

14:05 Okay. That's what the machine does and you can uh this is in in general written as a set, but if the machine is deterministic, you know that there's always just one step in this. Remember this uh notation here?

14:24 This little Mhm. I don't know if this has a name. Let's say the computation relation as a in the text. So, there's always just one uh successor state, then this set will have a single element or maybe none if the machine doesn't ever stop or doesn't ever accept this input.

14:42 Um so, then we can just write this in the usual notation for functions. Otherwise, it may be for a non-deterministic machine, there may be several things I can reach.

14:57 Still clear? So, given a machine, I can figure out with a given input, what could the machine do? And then if I write uh arrive at some halting state with stuff behind, then that's the output.

15:14 Uh with that we can define the running time and space usage of a Turing machine. And that's really where the model shines because previously we had to, you know, argue if I add two numbers, what happens and all these uh all these details. Here, the running time is simply the number of such computation steps that I've taken. So, in this notation here, we take the relation and take the teeth power of the relation, so sequences of T steps. Um the running time on a specific input now here is a bit weirdly defined to be the supremum over all possible values so that there is an a computation that produces this output. Why do we need that complication? We wouldn't need that um for deterministic machines. Uh there at least the set is not needed. There's only one one computation. But it might not terminate. In general, the Turing machine might run in an infinite loop.

16:13 And so then the supremum would would be uh empty or would not exist. Then we uh put the zero. Uh we will for all of complexity theory ignore non-terminating machines. But they are not um not easy to just define away. But for the running time, we'll um ignore those. And the space usage is just a maximal number of cells that we filled with something other than gap symbols.

16:57 I guess if the machine doesn't terminate, the supremum exists, but is uh just an infinite. Okay, supremum should be with the zero, right? Should be parentheses around this. Otherwise, the union doesn't make sense.

17:18 Yeah, if the machine never reaches the halting state, then this first set is just empty. And then I'm I only get the zero. Uh For a non-deterministic machine, I could have many many I could have an infinite number of non-deterministic computations. And they could be arbitrarily long. There might be no bound on the longest running computation. That's why I might get this infinite and why I need the supremum. Is that clear? Like um I don't know if I made that uh made that point very well. The question is this set, the set of all time step and set of all T number of time steps after which I reach the halting state might just be empty. Then I only get the running time zero, which is a uh it's a convention that we won't won't rely on much. For non-deterministic machines, I could have spawned new computations, and they might all terminate, but they might take longer and longer.

18:27 And here I'm I'm rather pessimistic. All of this is worst case over the possible computation. Okay. Already for the cute Turing machines, the definitions are a bit hairy in the details.

18:56 So, we've now defined Turing machines, we defined running time and space cost, and we defined the function that it computes. We'll actually usually just look at um functions mapping to zero and one. And so, uh the Turing machines will compute the characteristic function of some set. Namely, the set is those inputs where the machine outputs a one. And anything else is rejected or is not accepted.

19:30 Uh for non-deterministic machines, uh I don't know. I mean, more care than we've had on the previous slide is not needed. Um but the we want them to essentially always output something. We don't want them to run o- only in infinite loops.

19:50 So, if I have a um a Turing machine, I can define this this language of inputs that it it accepts as all the strings so that when I start it on that string in the starting state, it eventually outputs one. Terminates in the holding state and has a single one next to it. I guess here uh I'm assuming that these numbers zero and one are part of the alphabet that I'm allowed to use. >> [snorts] >> Uh for note that we're non-deterministic machine, by the definition of computed function, it's enough that there is some way to reach a one.

20:39 So, I guess um yeah, that's that's why it's written here as the output one is one possible output of your machine on this input. Okay? So, non-deterministic machine, given the same input, might run into different computational options, and might even output different things. As long as any one of these computations eventually says, "Yes, I like this input." This input is part of the language of the machine.

21:20 I think we may may see some examples. Um This is a side remark. I'm not going to even talk much about. You can sometimes um the model gets a bit more natural in terms of the running times if you don't allow fix a single tape but allow a finite number of tapes. It doesn't get in general more expressive or it doesn't change the classes P and NP. You can take that's the specific statement here. If I start with um a Turing machine that is allowed to use K tapes. So it has K read write heads that it can move independently. That gives it a bit more power. So it may be a bit faster but as um if I'm if I'm happy with a quadratic speed as slow down then I can simulate this machine on a single tape. So we don't need to deal with those as long as we ignore um squaring the running time.

22:23 Okay. Um for complexity theory we're really just interested in Turing machines that never run into infinite loops. And you can uh um you can always enforce that. That's the next one. Uh Let me first say what does that mean? Um Turing machine is is total or computes a total function is always terminating. Well uh for every input there is always some um upper bound on how long it takes. If you make the input longer and longer it might take longer and longer for the machine to finish as we expect from computation in general but it will eventually finish.

23:12 That was the comment I was making a second ago. This for this area or complexity theory is not a big restriction because you can always make a Turing machine terminating by essentially letting it run and when it takes too long saying time out and treat that as a failure. So a bit more formally you need you need an upper bound for the number of steps that is computable which is an insanely weak requirement. Um people may know about Ackermann function and the so there's very little running time functions that you would come up with that are not computable but formally it's a requirement because we're building a machine M prime that takes the length of the input evaluates how many time steps I should give the other machine and once I know that I can simulate this other machine by simulating its tape checking which state it was in, checking which symbol it reads and then looking up in in the finite small table of transitions what step it should take then executing that step somehow on the side making notes of what I've done and decrement the counter until the time out happens.

24:27 That's what I meant with we'll not do this in full detail. This is the kind of level of programming for Turing machines that you can do with without going insane. You could maybe imagine how this could be spelled out for a specific machine M you can somehow make a way to simulate it step by step and have some part of the tape reserved for your metadata and the other part of the actual tape of the machine. And then if it needs more space to the left maybe you just copy all your stuff once further. If you if you allow a certain slow down as here again I essentially for every time step I'm allowing myself to take as much time as the machine has taken. So, like very very slow. It's not at all uh ambitious. Then you can simulate this machine with this extra timer where if it takes too long, you will just output time out.

25:23 So, if you want, we can just say for now all Turing machines we can assume that they always halt and it's not a big restriction.

25:45 So, a quick summary. Um we won't use Turing machines as a model for actual computers. They're a model for making proofs about impossibility statements. And for that they're at least more convenient than other options. Uh usually if we're only interested in the distinction between polynomial time and worse um the model details don't matter at all. And so, uh for example, this um the question about how much time does it take to add up two numbers doesn't play much into this. It's still I think very useful and important to have one specific model in mind in case some questions do need the details of the model to be resolved.