CS245 Study Guide - Halting Problem
Document Summary
Visit my faster pc for a free scan. The halting problem is one of the most profound discoveries in computer science. It gives us an idea about the limits of what can be computed and what cannot. In this article, i"ll explain this cunning problem using standard computer terminology, rather than the very formal mathematical objects which are usually used. Formalities like the turing machine are necessary to dress the halting. Problem up in and put it in a rigorous math textbook, but the deeper intuition is the real-world computer, since that"s what we have experienced and actually used in real life. In order to simplify things so we don"t get bogged down by unnecessary details, here are the two idealizing assumptions we"ll use: computers never run out of memory. This has actually become closer to reality in recent decades than it was when turing & co. originally assumed in nite tape.
