Oh Hey There

re Halting Problem

particularapparatus:

Also, who cares? “What are the civilian applications?”

It matters because it tells us that there are functions that cannot be computed by any physically realizable model of computation, and as for a “practical” use of the halting problem, if you can reduce a problem to the halting problem, then you can show that that problem is also uncomputable.

Notes:

1. tristn liked this
2. particularapparatus reblogged this from tristn and added:

   Yes, I know :) I ask again… Well, maybe it is a little harsh. I am just cranky about computation this week, don’t mind...

3. tristn reblogged this from particularapparatus and added:

   It matters because it tells us that there...functions that cannot be computed by any...

4. particularapparatus reblogged this from tristn and added:

   who cares? “What are the civilian applications?”

5. poisonville liked this
6. tristn posted this