Acceptance for Turing Machines is Undecidable, but Recognizable 

Thanks very much!

Great!

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.

Why is it impossible to locate every ant?

@@SunShine-xc6dh Looking at this now I don't think my explanation really applies to reductions since if I recall they actually work the other way around (Known undecidable reduces to possibly undecidable if true both are undecidable otherwise keep testing). But to answer your question It would be because how would you know when you counted the last ant? You would need to search the entire planet with 100% accuracy and even then how do you know ants didn't reproduce in that time, or maybe a spot you checked didn't have an ant and then later an ant you hadn't counted walked there would you infinitely check the entire planet with 100% accuracy at least with our current technology that is impossible. Therefore, the original original statement

no u r a legend, no cap

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.

I got the same confusion

if you create a D s.t. the output is the same then that doesnt prove anything about L's decidability. you just found one specific case (out of an infinitude of cases) that shows it MIGHT be decidable. however, we want to find ONE concrete counterexample s.t. we create a decider whose output causes a contradiction on ONE concrete input. if we can find ONE specific case to contradict the claim (by assumption) that L is decidable, then our claim is wrong and therefore L must be undecidable

Agreed. Next neighbor may cut you short

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?

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?

@@gobwinning 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));