Timeline for Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$?
Current License: CC BY-SA 3.0
2 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
Jan 1, 2016 at 4:02 | comment | added | Pavel | Well, yea, that's the thing, won't we get a contradiction regardless of what word we put in? I don't understand why the input string has to be the description of D. In your analogy, why not make f to take in x and y? Why not define D to take as input <M,w> and reject w, if H (taking <M,w> as well) accepts it, and vice versa? | |
Dec 31, 2015 at 21:58 | history | answered | David Richerby | CC BY-SA 3.0 |