Acceptance for Turing Machines is Undecidable, but Recognizable
Вставка
- Опубліковано 16 жов 2024
- Here we show that the A_TM problem is undecidable and recognizable, which is asking if there is a decider for whether an arbitrary Turing Machine accepts an arbitrary input. The proof is by contradiction and diagonalization.
What is a Turing Machine? It is a state machine that has a set of states, input, tape alphabet, a start state, exactly one accept state, and exactly one reject state. See • Turing Machines - what... for more details.
Easy Theory Website: www.easytheory...
Become a member: / @easytheory
Donation (appears on streams): streamlabs.com...
Paypal: paypal.me/easy...
Patreon: / easytheory
Discord: / discord
#easytheory
Merch:
Language Hierarchy Apparel: teespring.com/...
Pumping Lemma Apparel: teespring.com/...
If you like this content, please consider subscribing to my channel: / @easytheory
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
ryan.e.dougherty@icloud.com
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.
Thanks to my supporters Yuri, vinetor, Ali (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
I learned this two weeks ago and could never grasp what exactly the contradiction was until I watched this video! Thank you so much truly appreciate you.
Thank you so much man you are the best on youtube you made everything complicated easy. Much love from Portugal
Thanks very much!
what an elegant proof. i did not understand the contradiction before but it makes so much sense now. for context, i thought the contradiction was for all inputs to D. i see now that all it took was one input to D (namely D's encoding itself) to show why D cannot exist. thank you for the clear explanation
Finally, I understand it. Thank you for an excellent explanation.
first time i understood the concept behind halting problem proof .. thanks a lot. 😄
Thank you so much for this video man I had trouble understanding this topic in university but you make it seem easy.
but that's just the nature of D right?
it always gives the opposite of its input.
it just proves that a decider that does the opposite cannot exist, doesn't mean A_TM is undecidable.
If you made D that accepts when accepts, and reject when rejects, doesn't that also prove it's a decider?
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.
Much clearly than anyone! Thank you
Thanks dude 👍🏻 I finally understood this part
We have *created* D to output the opposite..hence the contradiction arised. What if we create D such that the output is the same..it then does not create any contradiction. Please help..
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
This ATM proof really helped me understand
Finally I understand the contradiction . thanks man !
So, in this case, the property of TM D (always outputting the opposite of TM H) is one we derive just for the proof? As is the nature of any decider TM to freely do so?
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.
You are a life saver man! Thank you
For anyone still struggling with this here’s how I understand it.
Assume you could know the number of ants in the world with 100% accuracy.
You could definitely do that by getting all the ants and counting them.
If you could get every ant that means you could definitely locate every ant.
But it is impossible to locate every ant
which means it’s impossible to count all the ants
which means it’s impossible to know the entire ant population with 100% accuracy.
The point is to assume the statement is true, find a smaller step that if done would guarantee the statement. Tweak that step in a way which would easily be allowed. Then see if it breaks everything.
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
thank you for this mate.
I finally understand it fully
Great!
How do you just arbitrarily say that turing machine D gives the opposite result? Why is this? There's no explanation as to why that is the case. This needs to be explained better.
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));
Hey there, just a quick question. I see that you proved Atm to be undecidable, but how is it recognizable?
If M accepts w, Step 1 "Run M on w" will finish in a finite amount of time.
THANK YOU SO MUCH FOR THIS .
This argument is improperly defined. lets define D(f) = ~H(f, "f"), take a moment to convince yourself this is equivalent to what was said in the video. If we walk through the execution pipeline, first D is called with argument f. Then H is called with arguments f and "f". Finally f is called with argument "f" and if it accepts we reject and vice versa.
Now lets evaluate the alleged contradiction case: D(D) = ~H(D, "D").
Once again convince yourself of the validity of this notation. Here we can see the issue, an argument mismatch. In the execution pipeline D is called first with argument D, then H is called with arguments D and "D". Which calls D with argument "D" and the result is the opposite of that.
I hope you can convince yourself from there of the fact that D(D) = ~D("D") is not actually a contradiction at all, that is if D(D) accepts, all that means is D("D") rejects.
beauty, was looking for this!
If we run M on w and it runs forever the first time, but will accept the second w in the language, how do we know its Turing Recognizable, if we never get to the second input? This is what im confused about.
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?
Do the opposite is not part of h and is the part that breaks d. They aren't the same if h accepts h then h accepts h if it rejects it rejects the contradiction only exists in d
Also running d on it code isn't the same as running it on its resulting output which can't exist without an initial input
Agreed. Next neighbor may cut you short
really helpful 🙏
Thank you so much❤
Very cool! Thank you.
u r a legend, no cap.
no u r a legend, no cap
Thanks!!!
good shit mang thx so much luv u
thanks
Awesome 😎!!!
Tu es brillant!!
Finally !!! I understand :)'