christer@cs.umu.se (Christer Ericson) (11/15/90)
In article <13530:Nov1419:56:3790@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >In article <1990Nov14.150535.25991@cs.umu.se> christer@cs.umu.se (Christer Ericson) writes: >> In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > [ stuff deleted ] > >> 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*. > >Right. It's also solvable in practice. > >> Practically, given the size of available >> memory on todays machines, for most problems I'd say it's not. > >Are you trying to contribute to this discussion? In the article you're >responding to I gave quite precise estimates of the amount of work >necessary: twice as much memory for the variables you want to detect >cycling, and three times slower not counting housekeeping whenever those >variables are used. Now you express some vague opinion that this is not >practical, when obviously factors of two and three are the norm during >debugging. I'd like to see you try your method on a program like (defun foo (n) (if (= n 0) t (foo (1+ n)))) and calling the function with n=1. On a system with bigints and lots of memory, this isn't practical. If the function was more complex so it wasn't feasible to solve the halting problem by hand, and if it did get into a loop (when it ran out of memory, and the bigints overflow or whatever) the running time of the program could very well be more than, say, a year and three years to solve the halting problem *isn't* what I'd call practical. Now, for your average program, with a more normal running time it sure is practical, no question about it! >> Also, the metod >> you described is nothing new, it's a commonly used metod to find cycles in >> iterative procedures > >In fact, I didn't even bother to review the details of how to detect >loops in general, because any reader who doesn't understand can look up >the exercises in Knuth. > >> Solving the halting problem for a Turing machine > >We are talking about practical problems, not Turing machines. You do have a tendency to remove sentences from their context, don't you? Besides, what's all the fuzz about? I'm agreeing with you (more or less), ain't I? >---Dan | Christer Ericson Internet: christer@cs.umu.se [130.239.1.101] | | Department of Computer Science, University of Umea, S-90187 UMEA, Sweden |
mjs@hpfcso.HP.COM (Marc Sabatella) (11/17/90)
>Not long ago in this thread I remarked that the halting problem is >solvable in practice. The response I got---from a computer scientist--- >was religious disbelief. It doesn't take much thought to apply theory to >practice and put some reasonable bounds on the resources necessary to >discover a loop---but computer scientists *don't do it*. No, computer scientist object to your using the term "halting problem" to described a reduced subset of the problem which was already known to be solvable, using the phrase "in practice" to justify the corruption of the problem. Some analogies: Fermat's Last Theorem has been proven "in practice", where "in practice" is simply defined, conveniently, to mean for all "n" representable by an 8 bit two's complement integer. Well, OK, this is probably true, but it hasn't proved the theorem itself, it has just stated a rather obvious fact that happens to be subsumed by the theorem. The four color theorem has been proven "in practice", where "in practice" is conveniently defined to mean "on all maps consisting solely of 2-inch square grids". Big deal. Same comment. In fact, your "solution in practice" of the halting problem as well as my examples really boils down to There are a finite number of integers "in practice", where "in practice" is conveniently defined to mean "integers between -0xffffffff and +0xffffffff. Don't use the term "in practice" to corrupt the problem statement. >Just undecidability. Of course, if you were to believe some of the >people who argued with me in this group, you'd believe that sorting is >not linear in the number of bytes being sorted Again, no, no one disputes that, it is just that "number of bytes being sorted" works out to a factor of #keys * log (#keys) whenever there is no duplication of keys. What you mean by your claims is true (well, I don't know about optimal adding chains one way or the other); we take issue with your wording. -------------- Marc Sabatella (marc@hpmonk.fc.hp.com) Disclaimers: 2 + 2 = 3, for suitably small values of 2 Bill and Dave may not always agree with me
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/20/90)
In article <8960025@hpfcso.HP.COM> mjs@hpfcso.HP.COM (Marc Sabatella) writes: [ several analogies ] Two differences: 1. The practical problems people want to solve go well beyond the special cases dealt with in each of your analogies. 2. You are not solving the theoretical problem stated, so you have no right to call it a solution. The limits you introduced are entirely artificial. On the theoretical side, the method I outlined *is* a solution to the halting problem, because all machines are finite. On the practical side, it detects a huge number (in my experience, practically every case) of nonterminating programs in a reasonable time. Your analogies are neither theoretically correct nor practically correct. > >Just undecidability. Of course, if you were to believe some of the > >people who argued with me in this group, you'd believe that sorting is > >not linear in the number of bytes being sorted > Again, no, no one disputes that, it is just that "number of bytes being > sorted" works out to a factor of #keys * log (#keys) whenever there is no > duplication of keys. But it's silly to say ``sorting is k log k when the keys are distinct'' when you can make the much more precise statement ``sorting is linear per byte in all cases.'' After all, when there are duplicate keys, the former bound can be much worse than the latter. ---Dan