--- Video Title: ACCEPTS is Uncomputable (Part 2) Description: Theory of Computation https://uvatoc.github.io/week9 18.5: ACCEPTS is Uncomputable (Part 2) - Proof-by-Contradiction that ACCEPTS is uncomputable David Evans and Nathan Brunelle University of Virginia --- So if we're going to prove something by contradiction, what's our assumption going to be? That we want to get a contradiction to? Yeah, our assumption is if it's computable, that must mean there's some machine that computes it. That's going to be our assumption. And we can give that machine a name. If there's a machine that computes accepts, that means there must be some string that describes it. There's some string that describes it. That wa must exist. That's not a contradiction yet. But what we're going to try to do is define a new machine that now takes one input. Remember that our exception machine takes both a description of a machine and an input x, which can be any string. But we can decide what x is. So we're going to define a new machine that takes one input and simulates our ma, our machine that we have assumed computes accepts. It's going to simulate that on this description of the machine and this input. And then instead of outputting what that outputs, we're going to just flip the output. So if it would accept, we're going to reject. Meaning if it would produce a one as output, we're going to output a zero. If it would produce something other than a one, including running forever, we're going to output a one. This is really just negating the machine and now using the same input. All the machines are described by some string. So there must be some string we'll call wd such that it describes this d machine. We're just defining machines. If we wanted to be really careful, we'd have to define them precisely as Turing machines. But now that we've got a notion of what Turing machines can do, I think you should be convinced that we could make a Turing machine. We know how to simulate. What does it mean to simulate MA running on XX? Can we do that? Have we built a machine that can simulate other Turing machines? That's our machine U. Our universal Turing machine can do that. We've just got to make the input. We're going to make the input to you the description of the machine A and XX as the two inputs. So we know how to do that simulation. We certainly know how to flip the output. So all of this we should be happy with. And that means we can definitely ask the question, what should be the result of running D on its own description? WD is the string that describes D. What are our choices? Kind of like what we did before with self-rejecting. Well, this is a binary question. Right? Either it accepts or it doesn't. There's two options. What this part does. Right? So either simulating MA on WWD that can either accept or it can reject. We should flip the result. Could either of these be valid? Remember, what does this mean? That means does running the machine represented by D accept the input X? So this means the machine represented by WD, which is equal to D. Right? That's how we defined it. Accepts WD. That's what X is here. But what our machine does in that case is reject. So that doesn't make sense. It has to do the opposite of what it actually does. Well, the same thing here. If this rejects, it means D rejects. But because we're flipping the output here, the machine has to accept. So we have a contradiction. Right? Neither of these can be the case. We have a problem. So the contradiction is, on every input, D either accepts or rejects. Because we assumed there was some Turing machine that decides accept. So it always outputs either 0 or 1. And we can use that to construct a machine that would output the result of simulating this machine and flipping its output. So this D machine either accepts or rejects. It's got to do one of those two things. It can't do anything else. But for this particular input, which is a perfectly valid, good input, like it's just some string, it can't do either of those. If D accepts, that would mean this must accept, because this is really describing D. That would mean that much to accept. But the way we define D then, it's got to reject. I have the same thing here, good. And if it rejects, it must accept. But it rejects. Both ways are contradictions. So the only thing we can conclude is that D doesn't exist. Right? There's no output it can give that makes sense. And that might not bother us if D was sort of a normal thing. Because D is something we constructed that does this. And maybe we don't care that D doesn't exist. But if MA exists, then we can definitely construct D. There's no question that we know how to use Turing machines in a way that would allow us to construct D from MA. So that means if D does not exist, then MA must not exist. Because if we had MA, we could construct D. But we know D doesn't exist. And all we said about what MA was, was some machine that computes accepts. So that means MA must not exist. Which means there's no machine that computes accepts. So this is a pretty shocking result. So we should take a video break. Make sure we appreciate its significance. NBC higher than we are if we are pursuing so much along. So we have a great to say, well... By the past 2 Bye.