Turing’s Proof
In: Mathematics
Good explanation with visuals: [https://www.youtube.com/watch?v=92WHN-pAFCs](https://www.youtube.com/watch?v=92WHN-pAFCs)
Summary: imagine that you have a computer that can solve the halting problem by outputting ‘stuck’ or ‘not stuck’. Now, we hook it up to a second computer so that the output of the first is the input of the second. That second computer will get stuck if fed an input of ‘not stuck’, and will not get stuck if fed an input of ‘stuck’. If you feed the schematic of the combined computer into the first part, it can’t output ‘stuck’, because the second computer won’t get stuck, and it can’t output ‘not stuck’, because then the second machine would get stuck.
Latest Answers