Thanks very much!

What’s wrong with defining a TM that does that?

What's wrong with that? If there is an H, we can use it to make D, and D can cause contradictory behavior, so D can't exist, and thus neither does H. Standard proof by contradiction.

Great!

no u r a legend, no cap

I got the same confusion

If M accepts w, Step 1 "Run M on w" will finish in a finite amount of time.

The second w? What do you mean?

I'm not sure what you mean; the point is that the recognized emulates running M on w, and accepts if the emulation does. If M accepts w after some number of steps, so does the recognizer. So what do you mean related to the second w?

I don’t quite understand what you mean; if you can make a decider for ATM, what prevents you from making D with it? If D can’t exist, then there can’t be an H that you can make D from. And what does the last part mean?

@@KnakuanaRka Well i am 2 years late to this conversation but hopefully i will get an answer because i am stuck at the same point. What @superdahoho means to say is D can not exist because it outputs the opposite. D not existing has nothing to do with it using H. So how can we say H cannot exist when H is not the reason for D not existing?

@@barsbarancicek4138 The point of the argument is that if H (the decider for ATM) exists, then we can construct D, which results in contradictory behavior. Since we can’t have that, D cannot exist, which means H cannot exist either.

@@KnakuanaRka it doesn't make any sense!!! I'm with @superdahoho. I can't understand this proof bc the problem is with D.

@@kailanefelix2890 The basic process is a proof by contradiction. If a decider for ATM exists, we can use it to make D, so D exists. Applying D to itself causes contradictory behavior (if it accepts, then it rejects, and vice versa); we can’t have that, so D can’t exist, meaning the ATM decider doesn’t exist. It’s a similar form of contradiction to the proof of an infinite number of primes. If there is a finite list of primes (a, b, c…. z), then you could multiply all these together to get P, and add 1 to get P+1. Then we can get P+1’s prime factors (p, q…); these exhibit contradictory behavior, as they are both in the list of primes (as they are prime) and not in the list (P is a multiple of every entry in the list, so P+1 is not, and its factors cannot be in the list). Thus P+1 cannot exist, so the finite list of primes doesn’t either; the list of primes must be infinite to prevent this contradiction from happening.

If you run a decider (we assumed M) on an input, it will either accept OR reject, nothing else. And so when D runs M it gets a result back from it, either "accept" or "reject". You can then invert this result. The easiest way would be to use binary. Let's assume if M accepts, it outputs a 1, if it rejects, it outputs a 0. What we do is that after M has ran, we can have D look at the output and if it's a 1, D itself outputs a 0, and if it's 0, D itself outputs a 1. Does this make sense?

@@jmm5765but isnt that kind of "forcing" a contradiction? How would it be different from using a decidable language i.e. the Acceptance DFA and outputting the opposite result of that/claiming it's a contradiction?

@@7ow1nn1ng Well not quite, your scenario would be just inverting the input, which creates a machine (B) that inverts the input of another one (A). Each machine would still be consistent in its results, they would just contradict each other, which is fine. What happens here though is slightly different, by creating this machine D that inverts the result of M, you cause D to contradict *itself*, and that's where the logical contradiction arises. Does that help/make sense?

@@jmm5765 I'm having the same questions as @7ow1nn1ng, that doesn't make any sense for me. How does D contradict itself? And how do D contradictions implies M impossibility of existence?

@@kailanefelix2890 Basically, the cause of the contradiction is this: The D machine runs H on where M is a Turing machine (determining if the inputting the machine’s code into itself is accepted or not), and then returns the opposite (accept if H rejects, and vice versa). So what happens when you run H on ? This would basically determine whether or not D accepts D. However, internally, this would cause D to run H (the same thing), and then do the opposite. So if H accepts in the emulation, it rejects in the final output, and vice versa. This is a contradiction; you can’t assign a consistent value to the output because the internal emulation would require the same calculation to give the opposite response. It’s similar to Epimenides’ paradox of “This statement is false”; assigning a true/false value to it would imply the opposite, so you can’t evaluate it. So if this can’t happen due to contradictory behavior, what went wrong? If D existed, we could easily cause this by running D, so D can’t exist. And if we had an oracle H, the steps to make D from it are pretty simple; in order for D to not exist to avoid the contradiction, the oracle must not exist, either. The oracle is the only weak point or assumption in creating the contradiction, as if we had an oracle, we could easily do the rest, so by proof by contradiction, it’s where we went wrong. I also find it convenient to express the whole thing in terms of programming pseudocode with more clear names, like this: Oracle (TM, inp): #Return true if TM accepts on inp, false if it rejects or never halts Defier(TM): return NOT(Oracle(TM,TM)); #Does this give true or false? Print(Oracle(Defier, Defier));