--- Video Title: Decidable, Recognizable, Computable Description: Theory of Computation https://uvatoc.github.io/week10 19.1 Decidable, Recognizable, Computable Nathan Brunelle and David Evans University of Virginia --- I'm going to give you a way, a strategy, a proof strategy for showing additional problems are not computable. As part of that, we're going to catch some bad guys. And then we're going to prove something called Rice's theorem that Professor Evans teased to you at the end of last class. So that's our plan for today. Before we get started, let's talk a little bit about this idea of a description of a Turing machine. So we mentioned that the universal Turing machine, we could give it the description of a machine and an input w to be run on that machine. Let's talk a little bit about this idea of a description of a Turing machine. Who can give me one way that we could describe a Turing machine? What's one manner we could go about describing a Turing Yes, we could do like the states with the transitions and all of that garbage and that sort of thing. That's one way that we could be describing a Turing machine. So this is one potential way for describing a Turing machine. Can anybody give me any other ways of describing a Turing machine? Yes. We could do it with a number. We could have some sort of list of all the possible machines and we could just say, this is machine number 5702 or something like that. So that is another way. Who can give me another way that we can describe Turing machines? So that's actually describing a function, not a Turing machine. So kind of like with Boolean circuits, we could have functions or circuits. The function itself was not a definition of a circuit. And that's an important thing to kind of tease apart, because we can write down functions that we can't make Turing machines for. How did we describe our circuits? Yeah, so we had these straight line programs. So when we were talking about Boolean circuits, we had these straight line programs that we use to describe our circuits. And then we could take those straight line programs, and we converted them into these triples of integers. And then we could convert those triples of integers into binary strings, into bit strings, so that then we could finally convert those into something that made sense for our Boolean circuit, so we could do that eval function. When we look at Turing machines, this one here is probably the most straightforward way to go about describing a Turing machine. Something that we are going to prove, we're going to sort of take this for granted today, we're going to prove it either Wednesday or next week, depending on how fast we go, is that also things like Python. We could have this idea of an idealized Python that we could think of as describing a Turing machine. So when I say idealized Python, we have this issue with Python where you've actually got a fixed word size on your computer that limits how much memory you could possibly have. So idealized Python is kind of how you think about Python when you're programming it, as if numbers have infinite precision, and lists can be unlimited size and so forth. So the way you typically think about Python, you don't worry about memory constraints and so forth. That version of Python that you have in your mind, you can think of that as a description of a Turing machine. It's a more sophisticated description than states, transitions, et cetera. But it is still just describing a Turing machine. So everything that we're going to talk about today that works for states, transitions, et cetera, as being a description of our Turing machine, it's going to equally apply and in a very similar fashion with Python code. With Turing machines, there were three options for what a Turing machine could do for a particular input. It could have been that that Turing machine halted. And when it halted, it was going to either accept that input, that is return 1 for that input, or reject that input, so still halt and reject, so that is return 0 for that input. Or there was sort of this third option where it never returns, that is, it runs forever. There are three behaviors that a Turing machine can have for one input. It halts and then accepts, it halts and then rejects, and then it runs forever. And what I'm going to do is I'm going to give you a couple of definitions, So we are going to say that a function or a language is decidable. So we mentioned last time we could consider a language to be the set of all inputs for which that Turing machine returns one or accepts. So we can say a language or a function is decidable provided it can be computed by some always halting Turing machine. If I had some language and I want to know is it decidable, what I would do is ask this question of is there some always halting Turing machine that accepts exactly all of the strings in that language or returns one for exactly the right things. Alternatively, if we have this run forever answer, if we allow for this, then we are computing things that we call recognizable. Recognizable things are ones where all of the things that we ought to return one for are all of the things that ought to be in our language. We can find a Turing machine which is going to accept and halt for all of those. For all of the things that we want to return one for, all of the things that belong to our language, we are going to halt and accept for all of those. But things that aren't in the language, we can either halt and reject or run forever. So a language is decidable, provided there is an always-halting Turing machine which accepts exactly all of the strings in that language. We say a language is recognizable, provided there is a Turing machine which accepts all of the strings that are in that language. And for strings that are not in the language, it's either going to explicitly reject them and halt, or else it's going to run forever, which we're going to sort of say is like an implicit rejection. It's kind of like if you're on Tinder or whatever your favorite dating app is, if you get ghosted, if the potential significant other does not give you any sort of response, that is an implicit rejection. If that's news to you, then you're welcome. But Turing machines are sort of the same thing. If they never give you an answer, that is an implicit rejection in this case. And in general, when we say computable, what we really mean is decidable. So if we want to say that a function is a computable function, there is an always halting Turing machine that gives the right answer for every input of that function. So computable, we typically say is equivalent to decidability. So you'll often see people interchange these two ideas. I'll probably accidentally interchange these two vocab words. But in general, computable means decidable, which means it can be computed by some always halting Turing machine. Or as I tease at the beginning of class, some always halting Python program or something like that, since those are descriptions of Turing machines.