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.

Interesting. I think I see the analogy but I am not sure it is a proper fit. Consider that the halting problem only concerns a specific type of computing machinery, the Turing machine, aka an algorithmic machine. In such a machine, the program only has one input and one output. In addition, every step/instruction has a single predecessor and successor. In a non-algorithmic computer, by contrast, the program can receive inputs and send outputs at any time during execution and any instruction can have multiple predecessors and successors. Programmers never think about the halting problem because a modern computer with its use of interrupts, multiple threads and event-driven architecture, are not really Turing machines.

I guess that I don’t yet see how nature is analogous to a Turing machine or how natural laws are analogous instructions in an algorithm. But then again, maybe I don’t understand the analogy.

I think this analogy is flawed basically because we can legitimately use probabilistic reasoning which is not, strictly speaking, algorithmic.

BTW, Mapou, I don’t agree with you where you say that modern computers are not Turing machines. A Turing machine is a universal model of a computation. Whatever your computation, it can be represented as a Turing machine.

I think the analogy is appropriate. The inability to fully derive the entire set of “meta” laws that define all natural laws is indicated by Godel’s Incompeteness Theorem, which was the Turing’s starting point in working on the Halting Problem.

Simply put, Godel tell us that for any consistent system, there will always be foundational axioms that are required for the system to be complete that are not provable from within the system itself. The Halting Problem is another way of examining this issue.

In the natural world, it means that we are most likely to never have access to the full set of laws that undergird all of reality, because of the contingent nature of the universe itself as a “system”. Does this prove the existence of God? No. Does it mean that there will never be a consistent definition of all physical laws that rule out God’s existence? Yes, I believe it does. And I believe this is by design. By. Design.

Eugene S @3:

Well, I have to disagree. Parallel computers are not Turing machines. My biggest problem with Turing machines is that they are completely oblivious to time. A TM running at 1 Hz is no different than one running a 1 Gz. But, of course, there is a difference. There is no way to determine whether two operations are sequential or concurrent. Any program that can be interrupted externally and modified while running is not a Turing machine by definition.

For a different take on this topic, read Jeff Raskin – Computers Are Not Turing Machines.

“non-algorithmic computer” seems like an oxymoron to me. Admittedly, I am not an expert on computers.

FYI – two areas where the halting problem is directly related to Intelligent Design.

1) The halting problem and Irreducible Complexity

2) How the halting problem demonstrates non-material causation in problem-solving

Mapou,

Any algorithm i.e. a formal procedure which maps an input to an output and which is halting, is representable by a Turing Machine. The fact that this machine may or may not have an oracle is irrelevant. Parallel computations or not, is also irrelevant.

Actually, maybe I am wrong in thinking that the analogy is flawed. I rather meant that we can always come up with bounds on intractable functions, devise heuristics, which is also scientific. Less rigorous, more empirical but scientific nonetheless.

Years ago, G.Chaitin wrote an article in Scientific American called “On the limits of Reason” where he argued in a way similar to this OP.