otto@canon.co.uk (G. Paul Otto) (11/27/90)
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 .... >A year ago I posted a short note to comp.theory titled Finite Halting >Problem Considered Solvable. The gist of it is that you can solve the >halting problem for a program using just twice the memory and thrice >the time. > >In practice, with language support, you designate certain variables >to be tested for looping. Those variables are stored twice, and the >program runs at a third of the speed. If those variables together enter >a loop, the loop will be detected during its first period. For some >programs this could be very useful. .... >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. Interesting idea, and it shows how many non-terminations could be detected in a practical way. But not all ... For example, what if the state space is (say) 256 bytes? For example, if I write a loop of the style: do { n = random() } while (n != some_magic_number); where "random" is the function of that name on BSD Unix, then the period could be up to 2^(8*256). (Random can have up to 256 bytes of state, depending upon how you initalise it.). Even on the latest supercomputer of your choice, this would take a while to explore! (And of course, since we have to wait 3 times that long ...) But: let me be more positive. In practice, there is little difference between a non-terminating program and one which will take centuries to terminate. Since it is relatively easy (if one uses exponential algorithms, or tries to solve hard problems in straightforward ways) to write programs which could take too long to be practical, it is often highly desirable to work out how long (in order of magnitude) a program will take to run. The process of calculating that usually enables one to easily calculate a (practical) upper bound for the runtime. So, if the program doesn't terminate, you don't have to wait for 3* the period of whatever loop it has gotten into. [ Note that the period of the loop could be MUCH greater than the originally planned run-time. ] In summary: machines can be programmed to catch many of the simpler errors. Some errors (including some halting problems!) are best caught by using some reasoning. Paul ----------- Paul Otto, Canon Research Centre Europe Ltd., 17-20 Frederick Sanger Rd, Surrey Research Park, Guildford, Surrey, GU2 5YD, UK. NRS: otto@uk.co.canon Internet: otto@canon.co.uk UUCP: otto@canon.uucp PATH: ..!mcsun!ukc!uos-ee!canon!otto Tel: +44 (0) 483 574325 Fax: +44 (0) 483 574360