🚀 go-pugleaf

In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>Here are two articles about the practical solution to the halting
>problem. The first, from February this year, is short and should give
>people an idea of the resources implied by ``practical solution.''
>(Practical enough that it could reasonably be an option in Saber-C.)
>
> [lots of stuff deleted]
>
>The halting problem is to determine whether a given program loops forever.
>This is an uncomputable function of a program, as we all know.
>
>But if a program is restricted to a finite number of states then the
>problem is computable. The practical solution is that we run the program
>on two machines with that number of states, one machine exactly twice as
>fast as the other; if the program loops in time t to t+u, then we will
>see the machines in exactly the same state at time 3t to 3t+3u.
>
> [even more deleted stuff]

You think this is new? If a program, or rather a computer, is restricted to
a finite number of states (which all modern computers are) then it's nothing
more than a finite automaton and therefore the halting problem for these
machines is solvable *in theory*. Practically, given the size of available
memory on todays machines, for most problems I'd say it's not. Also, the metod
you described is nothing new, it's a commonly used metod to find cycles in
iterative procedures (hey, A. K. Dewdney has described it in his column in
Scientific American, so everyone - give or take a few - should be familiar
with it :-).  Solving the halting problem for a Turing machine (or any other
machine with unlimited memory) is something entirely different.


| Christer Ericson            Internet: christer@cs.umu.se [130.239.1.101] |
| Department of Computer Science, University of Umea, S-90187 UMEA, Sweden |