« first day (4597 days earlier)      last day (53 days later) » 

4:44 AM
1
Q: Diagonalisation in the proof of undecidability of the acceptance problem for Turing Machines

Simon LyonsIt's well-known that the language $A_{TM} = \{\langle M,w\rangle: \text{M is a turing machine that accepts w} \}$ is undecidable. There's a standard proof that's presented in Sipser's "Introduction to the theory of Computation" (and in a number of other online sources I've checked). It's often cl...


« first day (4597 days earlier)      last day (53 days later) »