From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,86fd56abf3579c34 X-Google-Attributes: gid103376,public X-Google-Thread: 10db24,77f71d0bde4c5bb4 X-Google-Attributes: gid10db24,public From: max@gac.edu (Max Hailperin) Subject: Re: What good is halting prob? Date: 1995/04/20 Message-ID: X-Deja-AN: 101370069 references: <3kaksj$iur@isnews.calpoly.edu> organization: Gustavus Adolphus College, St. Peter, MN newsgroups: comp.lang.ada,comp.edu Date: 1995-04-20T00:00:00+00:00 List-Id: In article cpp@netcom.com (Robin Rowe) writes: ..., it's still not clear what about the halting problem is actually useful. How can it be used in design? What problems does it help you solve?... The way it is used in design is as a way to help you distinguish between two situations that on the surface look very similar: 1) You're trying to figure out how to program something, and can't figure out how -- everything you try runs into insurmountable obstacles. You start to wonder whether the problem can be solved at all. It turns out it can, you just need to approach it differently. 2) You're trying to figure out how to program something, and can't figure out how -- everything you try runs into insurmountable obstacles. You start to wonder whether the problem can be solved at all. It turns out it can't, you need to find a way to live without a solution -- maybe by accepting some approximation. When you hit that point of doubting whether the problem you're working on is solvable, it is valuable to take some time off from trying to solve it and instead try to prove it unsolvable. If you succeed in your proof, then you know you are in situation 2 and should work on re-defining the problem instead of trying futilely to solve it. If you fail in your proof, you may well have in the course of the failed proof attempt done enough thinking about the problem in different ways to be able to now approach solving it differently and succeed. The way these proofs are usually constructed is by showing that if you could solve the problem at hand, you could use that to solve the halting problem. Hence, since the halting problem is unsolvable, so is the problem at hand. Here's an example; this is a semi-plausible "real-life-ish" scenario; I'm aware its not perfect in this regard, but its the best I could come up with off the top of my head just now, and I hope that it will help convince you that "really real" scenarios might arise: J. Programmer is working on an package for arbitrary-precision calculations. The user is supposed to be able to select any of the result values and request that it be redisplayed to a higher precision, which the user gets to specify. J. Programmer builds an approximation class (where each instance represents some particular number to some particular precision), and gives it a complete set of overloaded operations, so that you can do things like add two approximations and get an approximation. (The precision of the resulting approximation is suitably derived from the precision of the input approximations.) After this is working, J.'s next step is an "arbitrary precision number" class; each instance represents the abstract precision-independent "essence" of a number, and supports an operation which, when given the precision, will return an approximation of that precision. For example, if pi is an instance of this class, you can ask pi for an approximation of itself good to within 10^-2, and get back the approximation that would display as 3.14, or you can ask it for an approximation of itself good to within 10^-5 and get back the approximation that would display as 3.14159, etc. The way this is achieved varies from subclass to subclass; any given subclass of arbitrary precision number needs some way of doing it, but it can vary. J. Programmer none the less can and does supply the abstract super-class with a full complement of arithmetic operators; for example, you can add any two arbitrary precision numbers and get an arbitrary precision sum. The way J. makes this work is that the sum is of a subclass that has two instance variables, one for the augend and one for the addend. It provides an implementation for the "return an approximation of yourself good to this precision" method, namely, it turns around and asks the addend and augend for suitably more precise approximations of themselves than is desired for the sum, and then adds those approximations to get the approximation to the sum. This general strategy works for operations other than addition as well, and J. Programmer is busily buzzing along, picking off operations one by one and implementing them for the general arbitrary precision number class, until one day the == operator (i.e., equality testing) comes to the top of the to-do list. Nothing works. In fact, J. doesn't see any way it could be possible. But, the last time J. loudly declared a programming problem to be "impossible," C. Scientist from down the hall overheard and said "no, it's not impossible, in fact, it's in Knuth." So, remembering this, J. goes down the hall to see C. C. says "yes, this time I think you're right that its impossible -- I bet we can reduce the halting problem to it." The proof goes like this: if you had some procedure (let's call it P) that you wanted to test to see whether it halts, you could encapsulate it into an instance of a new subclass of arbitrary precision number. The way this subclass implements the "return an approximation of yourself to this precision" method is as follows: when asked to return an approximation good to within 10^-n, it simulates execution of P for n steps, or until P terminates, if it terminates in less than n steps. If P terminated in less than n steps, let's say in k steps, then the approximation returned is 10^-k. Otherwise, it is 0. Now, if you had an == operator, you could just check whether this number was == to 0 [or rather, to 0 converted to an arbitrary precision number]. If they are equal, then P doesn't halt. If they aren't equal, then P does halt. So, you've solved the halting problem! So, since that's impossible, it must be impossible to write a general == too. Armed with this knowledge, J. Programmer now can stop trying to implement == for arbitrary precision numbers, and instead work on finding some way to live without them.