'''The Halting Problem is to work out, given an arbitrary program, whether that program terminates. It is known to be completely insoluble.''' ---- *********************** HOLA A TODOS, QUIERO DECIRLES QUE AMO A MAR�A RAM�REZ, ATENTAMENTE ISAAC RAM�REZ. ****************** Nota: no somos hermanos ni familia. To understand why, assume you've got some Tcl command ''willHalt'' which takes a single argument (a script) and returns a boolean which says whether that script terminates. The following are obviously true: [willHalt {}] == 1 [willHalt {while {1} {}}] == 0 Now we build the following procedure: proc nothalt {script} { if {[willHalt $script]} { while {1} {} } } Thus, [[nothalt $script]] will halt exactly when $script does not. proc foobar {} { nothalt foobar } Now, we can say that [[nothalt foobar]] will terminate when [[foobar]] does not terminate, but we know that [[foobar]] is defined as [[nothalt foobar]]. So [[foobar]] only terminates when it does not terminate!?! Which is ''complete'' rot... The only assumption we've made that is not completely grounded in a script that we can trivially build is the existance of the [[willHalt]] test. Consequently, there cannot exist any such test (or at least, not one that is guaranteed to complete with the right answer.) QED. '''DKF''' ''JC: Gorgeous. With some luck, we could end up with enough gems in here to interest Tim O'Reilly one day!'' ---- I'm not sure I agree with the phrase "completely insoluble". Obviously, if you can write a willHalt function, you have it at least ''partially'' solved. You ''can'' prove in special cases whether a program will or will not halt, and you can even do so automatically if you can enumerate all of the program's possible states, and if it does no I/O (or you enumerate all possible I/O as part of your enumeration of the program's states). If a program ever returns to exactly the same state during execution, then it will execute forever (remember: no I/O allowed, unless you count all possible I/O as states in your state machine); conversely, if your program ever hits a terminal state, then you know it terminates. Perhaps it should read "insoluble completely", which is more accurate (although the set of cases where it can be solved is pretty uninteresting). I think it's provable that any machine which is capable of solving the halting problem in a specific case is not capable of analyzing itself. That's pretty much the same result, I guess... [Zygo Blaxell]% ''Actually -- if you have a machine where all algorithms are guaranteed to terminate (no recursion, iteration only over ennumerated sets of items, i/o limited to specific spans of time -- maybe 2^40 seconds), then willHalt is trivial: proc willHalt {} {return 1}. Here, instead of willHalt being bogus, notHalt is using the undefined command [[while]].'' ''And, given that all computers are finite, this way of looking at things isn't completely unreasonable. To "fix" this problem, texts on the halting problem usually are phrased along the lines of "halt before consuming a certain amount of resources" and the assumption is that the line is drawn someplace interesting.'' ''In fact: most of the times I see someone using recursion I also see a better way of approaching the problem (usually involving use of the properties of numbers). Something to ponder... actually, it isn't even necessary to prohibit recursion. Instead just do what real computers do: when the stack gets too deep, throw an error.'' ''Note that if you want to play around with this style of programming in tcl you'll want to define yourself a couple commands before you get rid of stuff like while and for. You'll want a command to make '''n''' copies of something, and you'll want a command to generate the first '''n''' indices of an array. See [Playing APL] for somewhat fleshed out examples of this kind of stuff.''