Uncommon Descent Serving The Intelligent Design Community

# The “Halting Problem” and an Interesting Analogy to Origins

Share
Flipboard
Print
Email

Wikipedia has a good article on the “Halting Problem.”  It begins:

In computability theory, the halting problem can be stated as follows: ‘Given a description of an arbitrary computer program, decide whether the program finishes running or continues to run forever.’ This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

In response to this UD post a friend who works with computers wrote me and said:

Central to [Turing’s] proof is the scenario where the algorithm is given itself as one of the inputs. The connection I [made] was that no natural law can be used to explain its own origin. We can derive new natural laws from existing ones, but we can trace that process backward only so far. Where it circles back to my comp sci classes is that we used the halting problem’s status as an undecidable problem as a bench mark in using reductio ad absurdum to prove other problems likewise cannot be solved. Where I was struck by your UD post is in the idea that we can’t use natural laws to derive the origin of natural laws. The natural world’s laws are irreducibly complex. Just like we can’t use an algorithm designed to solve the halting problem to determine if it will solve the halting problem, we can’t use natural laws to discern the origin of those same natural laws.