don't know if your going to see this but i can't find any source that explains how part A is able to find the description of to print. I am assuming its known beforehand as if it wasn't it would just be another scenerio of needing self reference of machine but how is it that we know .
I didn't quiet get the last example with MIN_TM. How does finding a bigger description than of B prove that MIN_TM is not recognizeable? The recognizer R (for MIN_TM) gets a TM and either says "yes" (there's a smaller TM that recognizes the language) or "no" (there isn't such TM, thus the one we have is indeed the smallest). I guess we use R to find a TM with a bigger description than B, but how's that showing it isn't recognizeable?
I think I know what was my flaw in understanding! When B is initially created, B has no 'fixed' language it can recognize. B's job is to find a TM (we call it C) (regardless of recognized langauge) that has a longer description than B does. Then, by simulating C on the input w, We turned B (which we know has a shorter description) into a recognizer for the same language by C! But C was found by R! This is where the contradiction is. Thanks a lot!
don't know if your going to see this but i can't find any source that explains how part A is able to find the description of to print. I am assuming its known beforehand as if it wasn't it would just be another scenerio of needing self reference of machine but how is it that we know .
Explained gracefully.
Thank you for the video!
Great video! Thank you so much!
Hey , I wanted to ask : Can you explain the recursion theorem in terms of computable functions?
Thanks. Helped me in my exam.
Pretty dawm awsome
I didn't quiet get the last example with MIN_TM.
How does finding a bigger description than of B prove that MIN_TM is not recognizeable?
The recognizer R (for MIN_TM) gets a TM and either says "yes" (there's a smaller TM that recognizes the language) or "no" (there isn't such TM, thus the one we have is indeed the smallest).
I guess we use R to find a TM with a bigger description than B, but how's that showing it isn't recognizeable?
I think I know what was my flaw in understanding!
When B is initially created, B has no 'fixed' language it can recognize.
B's job is to find a TM (we call it C) (regardless of recognized langauge) that has a longer description than B does.
Then, by simulating C on the input w, We turned B (which we know has a shorter description) into a recognizer for the same language by C!
But C was found by R! This is where the contradiction is.
Thanks a lot!