Does the programmer's ability to formulate halting solutions to arbitrarily posed problems signify a non-computational capability in the programmer? In other words, is the programmer doing something that no computer, nor any other object driven by the laws of physics, can ever do?
First of all, if the solutions to these arbitrary problems are halting solutions in a Turing complete environment, it is trivial to computationally generate halting programs if the generator is cognizant of Turing machines. In which case, the question still remains whether it is trivial enough to generate a halting solution out of these trivial halting programs.
Granting that the computational generator can trivially generate halting programs, there are a still a number of programs it cannot determine whether they halt or not. So, the generator has to deal with two sets of programs: P1) those it already knows halt and P2) those it does not know halt.
1. If P1 is sufficient to generate a halting solution (HS), and P1 is trivial to generate, then it is trivial to solve most if not all programming problems we encounter in the real world. This is highly unlikely.
2. If P1 is non-trivial to generate, then it is another set of HS2 programs to find, and is thus a variant of the same initial issue of generating a HS for an arbitrary problem. In this case, HS2 must already have been found in order to use it to find HS. What this means is that all the solvable posed problems have already been solved by the programmers before they are even posed. Pretty neat, but also seems highly unlikely.
Perhaps a non-trivial P1 set can be built up by a previous trivial set, if uses enough trivial steps in between. However, this is merely a variant of #1.
3. If the generator also requires P2, to any degree, then it runs into the halting problem, and won't work. So this option is out.
Therefore, if the programmer's ability to generate halting solutions to arbitrary problems is computational in nature, then either 1 or 2 must be true. Since it seems very unlikely either is true, then it is also very unlikely programming is a solely computational activity.
Eric,
ReplyDeleteVery interesting. However, do we really have the ability to formulate halting solutions to arbitrarily posed problems? It is not a rhetorical question, I simply don't know. I suspect that the conventional Turing machine may just not be adequate to represent the way the human brain computes solutions. To support this suspicion, I can say that there are some complexity theorists who believe the current theory is not expressive enough to resolve if P =/= NP (the two remaining groups being those who believe that the inequality holds and a minority who believe that P = NP but we just currently cannot prove it). Another example is Chaitin's models of life where he used the Turing machine extended by the halting oracle. Interesting stuff.