nothing-c's Solution to the Halting Problem

As a general wiseass, I, nothing-c, Lord High Imperator of N-C Softworks, have taken it upon myself to solve the well-known halting problem for the sake of the computing world (yes, I know what Turing said, but I've got a better idea).

The Main Issues

Since I've provided the Wikipedia link, you should know what the halting problem is and what it entails. Therefore, instead of a real solution, I have decided that a flowchart based on outside heuristics is the best move to make here. However, due to budgetary constraints, I will not be able to provide a flowchart, so a textual representation will take its place. For those of you who can only read StackOverflow, I will provide a basic code logic flow at the end of the page so you can understand the high-level thought-processes on display

The Easy Solution

As a consummate slacker, the most obvious answer to the halting problem is that all programs will halt eventually. The inevitable heat death of the universe demonstrates that, even if the algorithm doesn't want to stop, the hardware running it will turn to molten slag and the algorithm will be forcefully stopped. However, this solution is a copout, so I've prepared another

The Harder Solution

There are 3 broad points that my solution covers
    1) The exit point
    2) The loop structure
    3) The branching structure

THE EXIT POINT

The exit point is the most obvious way of determining if an algorithm will halt. If the exit point is unreachable (i.e, embedded in an if-statement that can never be true), then the algorithm will never halt.

THE LOOP STRUCTURE

The loop structure is also obvious. The main issue here is external influence; that is, user input. If a loop's length can be externally set and/or modified, then it will never halt if it is given an infinite source of information (i.e, cat /dev/random). However, if the loop's length is internal-only, then it becomes an exit point issue, as described above. This section also covers the issues of infinitely-looped GOTOs.

THE BRANCHING STRUCTURE

Like the above, the branching structure is primarily based on user input. If a branch can be executed based on the user input, then, provided the correct user input (i.e, one that is infinite or will always fulfill the condition required for branching) the algorithm will never halt. Otherwise, the algorithm will only continue infinitely if engineered that way. The exit point issue also applies here, if the branch occurs until an exit point, and that exit point is unreachable, then the algorithm will continue forever.

So, as you can see, the solution to the halting problem is actually quite simple, with the easiest way to avoid having to plan against it is not accepting user input. Haskell programmers, the smarty-pantses they are, have cleverly embedded this into their language, so kudos to them.

Home