misha@ai.mit.edu (Mike Bolotski) (11/13/90)
In article <23904:Nov905:22:5290@kramden.acf.nyu.edu>, brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: |> In article <MISHA.90Nov7191750@just-right.ai.mit.edu> I write: |> > In article <7659:Nov620:58:5990@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: |> > > pointers (arrays) are pre-indexed appropriately. Could one of you CS |> > > types please illustrate to Jim that finding optimal addition chains in a |> > > general computation is equivalent to solving the halting problem? |> > Bzzt. But thanks for playing, Dan. |> > Optimal addition is NP. |> |> Bzzt. But thanks for playing, Mike. |> |> Finding optimal addition chains in a general computation is most |> certainly equivalent to the halting problem. Since no CS types have |> stepped forward, I'll illustrate. Consulting that a standard reference text in the field, "Compilers: Principles, Techniques and Tools", by Aho, Sethi, and Ullman reveals the following on page 517. "Finding an optimal assignment of registers to variables is difficult, even with single-register values. Mathematically, the problem is NP-complete." Now this is register assignment, not evaluation order, but Dan's "outline of proof" switched the problem to allocation of address register. But not to despair: "The order in which computations are performed can affect the efficiency of the target code. [..] Picking a best order is another difficult, NP-complete problem." (p 518). |> Outline of proof: Take a program. Add an array[2], x. Read x[0] and x[1] |> from the outside. Use x[0]. In a subroutine, use x[1] repeatedly and |> then exit. Replace every exit with a call to the subroutine. |> |> Now if the program does not exit, it is best to keep &x[1] around. If |> the program exits, it is best to keep only &x[0] around. Q.E.D. The above is not a proof. It is not even close to a proof. In fact, I suspect you have the common misconception that the halting problem consists of determining whether a particular program will ever halt or not. I suggest you consult a standard theory of computation text, such as Hopcroft and Ullman for a definition, and examine what a proof by reduction to a Ktm looks like. [ Timer description deleted due to irrelevance ]. |> Q.E.D. Right. |> Indeed. (As a matter of fact, it's quite feasible to solve the halting |> problem in practice---the algorithm just depends on the program.) If this statement was made with full knowledge of what the halting problem is, it would have been a wonderful .sig quote. Excerpted from another article by Dan, replying to Jim Giles: |> I simply don't understand where you and Mike are getting this ridiculous |> assertions from. What problems are you fantasizing you've solved here? |> Where are your purported proofs? The louder you yell your mistakes, Dan, the more embarassing they become. Especially since you are venturing out of the safe realm of opinion and dealing with facts that can be proven mathematically. -- Mike Bolotski Artificial Intelligence Laboratory, MIT misha@ai.mit.edu Cambridge, MA Okay, just this once: "It's quite feasible to solve the halting problem in practice." -- Dan Bernstein
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/14/90)
There does not exist an algorithm that will convert an (optimal) array program into its optimal pointer form. That summarizes what I've said so far in this thread. What does it mean for real languages? It means that the programmer *must* be allowed to look at an array x from the vantage point of x[a], rather than x[0]. This array shifting doesn't have to look like C's pointer arithmetic, even if it is implemented that way in machine language, and even if it's doing no more than providing pointer arithmetic with a different syntax. It just has to be there. Once you have array shifting, finding the optimal pointer form is rather easy, as Jim has been saying. I don't know of any efficiency advantages of pointers in that case. In article <11839@life.ai.mit.edu> misha@ai.mit.edu writes: > "Finding an optimal assignment of registers to variables is difficult, > even with single-register values. Mathematically, the problem is > NP-complete." I am not talking about finding an optimal assignment of registers to variables, so even if I were to blindly believe this statement, I'd stick to my position. > "The order in which computations are performed can affect the > efficiency of the target code. [..] Picking a best order is > another difficult, NP-complete problem." (p 518). See above. Don't fall into the trap of misinterpreting AHU's statement. Only a very limited class of optimizations may be performed by computer. The general problem of finding the best way to compute something isn't just NP: it's undecidable. An example of a decidable problem: Find the fastest way to compute x^n, for a single exponent n. This is the simple addition chain problem. An example of a problem not yet proven either decidable or undecidable: Find the optimal way to compute x^n, for a given range of exponents n, under a certain computational model, where ``optimal'' means optimal in a weighted average of run time and program space. It's highly likely that a computer can't solve this, but you never know. If you see the difference between these two problems, you'll appreciate what AHU are saying. > |> Outline of proof: [ ... ] > The above is not a proof. It is not even close to a proof. How observant you are. I called it an ``outline'' for a reason. In the article before this, I went through an informal proof. > In fact, > I suspect you have the common misconception that the halting problem > consists of determining whether a particular program will ever halt > or not. In fact, I suspect you have not been on the net long enough to know any better. Or were you not reading comp.theory in January 1989? See my next article. > [ Timer description deleted due to irrelevance ]. > |> Q.E.D. > Right. I'm disgusted by your lack of appreciation for the value of constructive criticism in modern science. If you see something I've missed, point to it! (Or index it! :-) ) I just don't see how you plan to figure out whether you should keep a pointer to x[0] and use that to get x[1], or whether the opposite order is better. > |> Indeed. (As a matter of fact, it's quite feasible to solve the halting > |> problem in practice---the algorithm just depends on the program.) > If this statement was made with full knowledge of what the halting > problem is, it would have been a wonderful .sig quote. Feel free to put it in your .sig---after you understand what I say in my next article. > |> I simply don't understand where you and Mike are getting this ridiculous > |> assertions from. What problems are you fantasizing you've solved here? > |> Where are your purported proofs? > The louder you yell your mistakes, Dan, the more embarassing they become. But you haven't pointed out a single mistake! *You* just implied that it is not feasible to solve the halting problem in practice. As anyone who reads my next article will realize, you are wrong. There. I've now pointed out an error (or at least implied error) of yours. Can you make the effort to follow the same format if you really do see a mistake in what I post? Or are my suspicions correct, and you haven't, in fact, seen any error? > Especially since you are venturing out of the safe realm of opinion and > dealing with facts that can be proven mathematically. No shit. That's one of the things that you learn to do when you're trained as a mathematician. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/14/90)
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.) The second, from January 1989, was my first posting of the solution, on comp.theory. I remember having just finished reading an article in good old Dr. Dobbs about the halting problem. It gave the usual presentation of the theory, but went out on a limb and said that the halting problem wasn't solvable in practice. As happens so often in computer `science,' the limb wasn't connected to the tree's trunk. After seeing a similarly unjustified statement in a discussion in comp.lang.c and comp.theory, I was sufficiently annoyed to write the article. Several months ago someone from England seemed interested in implementing the method. I don't know what's come of it. Oh, well. ---Dan >From: brnstnd@stealth.acf.nyu.edu Newsgroups: comp.software-eng Subject: Re: Have *YOU* ever written a program which COULDN'T be proven correct? Message-ID: <3803:04:53:29@stealth.acf.nyu.edu> Date: 14 Feb 90 04:53:30 GMT Distribution: usa In article <793@arc.UUCP> steve@arc.UUCP (Steve Savitzky) writes: > I think you missed my point, which is that whether or not the halting > problem can be solved *in theory* for real programs on real computers, > it cannot be solved *in practice*. 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. ---Dan >From: bernsten@phoenix.UUCP (Dan Bernstein) Newsgroups: comp.theory Subject: Finite Halting Problem Considered Solvable Message-ID: <8901162049.AA11027@jade.berkeley.edu> Date: 16 Jan 89 16:32:35 GMT Sender: daemon@ucbvax.BERKELEY.EDU Reply-To: TheoryNet List <THEORYNT%NDSUVM1.bitnet@jade.berkeley.edu>, Dan Bernstein <phoenix!bernsten@PRINCETON.EDU> Distribution: inet Organization: The Internet Lines: 52 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. Now consider modern, real computers. The space needed for this is practical. But the time is a trickier consideration. How do we compare the states of two computers? The solution is that in unit time a computer modifies a bounded-size portion of its state as expressed in bits. So we merely watch what registers, memory bytes, etc. are changed, incrementing a difference count when something is made different on the two machines and decrementing it when something is made the same. As a matter of fact, this (at least for memory) is already done by good caches. It would be a simple modification to those caches designed for multiprocessors to have them keep track of (1) registers and flags as well as memory and (2) a difference count. Of course, this eminently practical hardware solution is only appropriate if the entire machine is involved in a single computation that we don't want to have accidentally looping. But I'd say that the problem is practically solvable in software for many situations. For example, MACSYMA and similar programs could have a feature that a user-defined function be run three times slower and have it detect infinite loops of variables blah, blah, and blah in the function. I would expect that this be restricted to non-recursively written functions, and restricted to functions that don't use non-mathematical stuff like reading from a disk file---but it's still quite doable and would be a real, live, practical solution to the halting problem. More ambitiously, I can see how a C compiler could compile a function to detect infinite loops. The function would probably run somewhat slower than just three times, as most optimizations would go down the drain and dealing with the difference count would be a major speed factor relative to the speed of single expressions. And yes, it would take double the memory---which could be a problem if the function had an array taking an amount of space comparable to the space available on the machine. And I would expect the restriction that the function and everything it calls must use only built-in C, no system calls or anything else possibly external; and also that the function and everything it calls must only use variables local to themselves. But after all these caveats this still remains a valuable tool that I would have loved to have for testing many programs: the practical solution to the halting problem. ---Dan Bernstein, bernsten@phoenix.princeton.edu
christer@cs.umu.se (Christer Ericson) (11/14/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 >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 |
gudeman@cs.arizona.edu (David Gudeman) (11/14/90)
In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu> Dan Bernstein writes:
]Here are two articles about the practical solution to the halting
]problem...
This isn't a solution to the halting problem, it's a solution to the
problem of determining whether a program ever enters the same state
twice --which is neither a sufficient nor necessary condition for a
program to be non-terminating. That, unless you include the entire
universe of things that might effect the program in the state (input
futures and such). In that case it is a sufficient but still not
necessary condition for non-termination.
You could probably get a better approximate solution by a static
analysis of the program, and it would not effect run-time parameters.
--
David Gudeman
Department of Computer Science
The University of Arizona gudeman@cs.arizona.edu
Tucson, AZ 85721 noao!arizona!gudemanbrnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/15/90)
In article <27477@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: > In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu> Dan Bernstein writes: > ]Here are two articles about the practical solution to the halting > ]problem... > This isn't a solution to the halting problem, it's a solution to the > problem of determining whether a program ever enters the same state > twice--which is neither a sufficient nor necessary condition for a > program to be non-terminating. More abstract silliness. Perhaps you forgot that the computational model is finite. The halting problem *is* the cycle problem. In practice, non-terminating programs enter a rather simple infinite loop. But this is irrelevant to the theoretical correctness of the method. I advise that you read the articles, which allude to these non-problems. > You could probably get a better approximate solution by a static > analysis of the program, No, you cannot, just as you cannot optimize arrays into pointers by a static analysis. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/15/90)
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: [ on the practical solution to the halting problem ] > You think this is new? No, I don't. I think computer science (as opposed to real-world computer programming) has regressed more than it has progressed in the last twenty years. In particular, modern computer scientists believe that the best known sorting methods are asymptotically suboptimal. They believe the dogma about the halting problem so firmly that they refuse to think through to a practical solution. So when I remind people of what was widely known in the sixties, I get attacked for my ``mathematical mistakes.'' > 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. > 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. ---Dan
gessel@carthage.cs.swarthmore.edu (Daniel Mark Gessel) (11/15/90)
In article <13350:Nov1419:44:2790@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: In article <27477@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: > In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu> Dan Bernstein writes: > ]Here are two articles about the practical solution to the halting > ]problem... > This isn't a solution to the halting problem, it's a solution to the > problem of determining whether a program ever enters the same state > twice--which is neither a sufficient nor necessary condition for a > program to be non-terminating. More abstract silliness. Perhaps you forgot that the computational model is finite. The halting problem *is* the cycle problem. In practice, non-terminating programs enter a rather simple infinite loop. But this is irrelevant to the theoretical correctness of the method. I advise that you read the articles, which allude to these non-problems. > You could probably get a better approximate solution by a static > analysis of the program, No, you cannot, just as you cannot optimize arrays into pointers by a static analysis. ---Dan The Halting Problem is _not_ the cycle problem. The Computational Model is a Turing Machine, not a computer with finite memory. The problem of determining whether or not a program goes into an infinite loop is The Halting Problem, given that the language it is written in can do dynamic allocation under the assumption that dynamic allocation will not fail. If you assume that dynamic allocation will fail at some point, you may be able to do some worthwhile analysis, and may be able to determine if a program halts. I don't actually know. The Halting Problem is by definition abstract silliness. Whether or not a computer program will stop depends exactly on your definition of a computer program. The mathematical definition of an algorithm is equivalent to a turing machine, as far as anyone knows, and if you can prove differently, you will become quite famous. For this definition of an algorithm, the halting problem is unsolvable by a turing machine. Dan -- Daniel Mark Gessel Independent Software Consultant Internet: gessel@cs.swarthmore.edu I do not represent the opinions of Swarthmore College.
gudeman@cs.arizona.edu (David Gudeman) (11/15/90)
In article <13350:Nov1419:44:2790@kramden.acf.nyu.edu> Dan Bernstein writes: ]In article <27477@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: ]> This isn't a solution to the halting problem, it's a solution to the ]> problem of determining whether a program ever enters the same state ]> twice... ] ]More abstract silliness. Perhaps you forgot that the computational model ]is finite. The halting problem *is* the cycle problem. ] ]In practice, non-terminating programs enter a rather simple infinite ]loop. I was objecting on practical grounds, not theoretical ones. Since, as you point out, a real computer is finite, the halting problem is theoreticaly solvable for them, but it is not clear that you have presented a _practical_ solution. It is not the case that all forms of non-termination involve "rather simple infinite loops", nor is it clear that this is the case in practice either. (Such forms of non-termination, by the way, are usually easy to find by static analysis.) In _practice_, a computer program has a huge number of states, and there is no reason to suppose that an infinite loop will cover only a small set of states. Even if the loop is doing something as simple as incrementing a few variables, say n, then the number of states in a cycle is on the order of MaxInteger^n. How long, on average, do you think it will take to detect loops in such a set of states? Your method can take arbitrarily long to detect an infinite loop, and in _practice_ if it takes too long it may as well never terminate. So the _practical_ effect of your method is that it will sometimes terminate with an answer ("infinite loop" or "no infinite loop") and will sometimes never terminate. Any theoretician can tell you that such a test is possible, so I don't see any justification behind your negative comments about computer science. It seems to me that practice follows theory quite closely here. This is not to suggest that it is worthless to do anything about infinite loops. There are approximate solutions known, but most people are careful to observe that the solutions are approximate, and only detect some subset of non-terminating programs. Saying that you have a "practical solution to the halting problem" is deliberately antagonistic, as well as incorrect. Your solution is either a practical partial way to detect _some_ non-terminating programs, in which case it is not a "solution" in the technical sense of the word, or it is a true solution to the problem of using finite state machines to detect non-termination on other finite state machines. But in this case it is not "practical", since there are many problems for which it will not terminate in a reasonable time. ]> You could probably get a better approximate solution by a static ]> analysis of the program, ] ]No, you cannot, just as you cannot optimize arrays into pointers by a ]static analysis. Are you suggesting that there is some connection here? And would you care to give some references to support this statement? (Not the connection, the assertion that you cannot get a better approximation by static analysis.) I'm curious as to how you are defining "better" in such a way that you can state this as a fact rather than as an opinion. -- David Gudeman Department of Computer Science The University of Arizona gudeman@cs.arizona.edu Tucson, AZ 85721 noao!arizona!gudeman
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (11/15/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 technique referred to is commonly known as "Tortoise and Hare". It's a very handy technique for programs that wander around graphs and other finite data structures. Most of the non-terminating loops my programs go into involve constructing ever larger data structures, so tend to be detected by the storage allocator... Eiffel is one of the few languages around which provides for termination tests: when you write a loop you can provide an expression whose value must decrease on each iteration, while remaining non-negative. If it goes negative or fails to decrease, the informal proof of termination you presumably had in mind when you wrote the loop is flawed. An old idea and a simple one. It's _very_ nice to see it actually provided as a debugging tool that's easy to use. -- The problem about real life is that moving one's knight to QB3 may always be replied to with a lob across the net. --Alasdair Macintyre.
oz@yunexus.yorku.ca (Ozan Yigit) (11/15/90)
In article <3975:Nov1323:25:4390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes on the halting problem: > 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. This sounds exactly like an old lisp algorithm for determining whether or ot a list is in fact circular. For example, the scheme code that determines list-length while checking circularity looks like this: (define (list-length lst) (elen lst lst 0)) (define (elen slow fast n) (cond [(null? fast) n] [(null? (cdr fast)) (1+ n)] [(and (eq? fast slow) (not (= n 0))) "cycle in list"] (else (elen (cdr slow) (cddr fast) (+ n 2))))) ;;; (set! foo '(a b c d e f g h i j)) ;;; (list-length foo) ;;; (set-cdr! (list-tail foo 9) foo) ;;; (list-length foo) So, what is the big fuss about? oz --- Where the stream runneth smoothest, | Internet: oz@nexus.yorku.ca the water is deepest. - John Lyly | UUCP: utzoo/utai!yunexus!oz
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/16/90)
If you have a program with a set of variables that enter a loop at time t, and continue to loop in a cycle of length l, then the method outlined will run the program in twice the memory at one-third speed minus housekeeping, and detect the loop between t and t + l, i.e., during its first cycle. That's all the practical solution to the halting problem does; interpret it as you wish. It's practical because the slowdown and memory waste are practical during debugging, and because t and l are relatively small in most practical cases. It's a solution to the halting problem because in the worst case it'll still detect the loop eventually, though I don't think these theoretical statements matter for the real world. In article <GESSEL.90Nov14165831@carthage.cs.swarthmore.edu> gessel@carthage.cs.swarthmore.edu (Daniel Mark Gessel) writes: > > ]Here are two articles about the practical solution to the halting > > ]problem... > The Halting Problem is _not_ the cycle problem. The Computational Model is > a Turing Machine, not a computer with finite memory. See, this is what I mean about computer scientists. The computational model I work with is realistic---it's just my mental picture of what can be coded on lots of real machines. As I said before, it's finite. It has very, very little to do with a Turing machine. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/16/90)
In article <27498@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: > In article <13350:Nov1419:44:2790@kramden.acf.nyu.edu> Dan Bernstein writes: > ]In practice, non-terminating programs enter a rather simple infinite > ]loop. [ disagreement ] Well, I can't remember ever debugging a non-terminating program that *didn't* have a rather simple infinite loop, and I remember debugging lots of programs where the loop was simple. Does your experience differ? I'd be interested in seeing your example. > Any theoretician can tell you that > such a test is possible, so I don't see any justification behind your > negative comments about computer science. 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*. > or it is a true solution to the problem of using finite state machines > to detect non-termination on other finite state machines. Yes, that is correct. > But in this > case it is not "practical", since there are many problems for which it > will not terminate in a reasonable time. Here we disagree about what problems come up in practice, and I'd be interested in seeing your examples of those problems. > ]> You could probably get a better approximate solution by a static > ]> analysis of the program, > ]No, you cannot, just as you cannot optimize arrays into pointers by a > ]static analysis. > Are you suggesting that there is some connection here? 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, that finding the optimal pointer version of array code is decidable (NP, in fact---check out Jim's articles over the past week), and also that the moon is made of green cheese. Well, maybe not that last one. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/16/90)
In article <4279@goanna.cs.rmit.oz.au> ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes: > 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 technique referred to is commonly known as "Tortoise and Hare". > It's a very handy technique for programs that wander around graphs > and other finite data structures. Maybe computer science actually hasn't been regressing in Australia. Thanks for confirming that someone else in the world knows what everyone knew when the words ``computer science'' sounded funny... People who aren't familiar with loop detection should look in Knuth, exercises 3.1-6 and -7 (I think; I don't have the book handy). [ Eiffel termination tests ] > when you write a loop you can provide an expression whose value must decrease > on each iteration, while remaining non-negative. You can apply Q's invariants in similar ways. People who aren't familiar with these techniques should look in Knuth, chapter 1, the first section on Euclid's algorithm. ---Dan
misha@just-right.ai.mit.edu (Mike Bolotski) (11/16/90)
In article <5785:Nov1519:19:5390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >If you have a program with a set of variables that enter a loop at time >t, and continue to loop in a cycle of length l, then the method outlined >will run the program in twice the memory at one-third speed minus >housekeeping, and detect the loop between t and t + l, i.e., during its >first cycle. That's fine, Dan. What if the cycle length is several millenia? It's not hard to write a simple program that uses say, 256-bit integers which accomplishes that. Your "solution" is hardly practical. And here's a quick test for your solution: int foo(x) int256 x; { while (x != 1) if (even(x)) x = x / 2; else x = x * 3 + 1; return 1; } >the worst case it'll still detect the loop eventually, though I don't >think these theoretical statements matter for the real world. The real world being defined as your experience alone, is it? >See, this is what I mean about computer scientists. The computational >model I work with is realistic---it's just my mental picture of what can >be coded on lots of real machines. As I said before, it's finite. It has No need to apologize for your limitations, Dan. Mike Bolotski Artificial Intelligence Laboratory, MIT misha@ai.mit.edu Cambridge, MA
misha@just-right.ai.mit.edu (Mike Bolotski) (11/16/90)
In article <6045:Nov1519:34:2290@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >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, that finding the optimal >pointer version of array code is decidable (NP, in fact---check out >Jim's articles over the past week), and also that the moon is made of >green cheese. Well, maybe not that last one. Just keep putting your foot in your mouth, Dan. And I like the ever-so-subtle transition from optimal addition sequence to pointer version of array code. And just how seriously do you expect your opinions to be taken if you haven't read the basic references about compiler construction or theory of computation? Mike Bolotski Artificial Intelligence Laboratory, MIT misha@ai.mit.edu Cambridge, MA
new@ee.udel.edu (Darren New) (11/16/90)
In article <5785:Nov1519:19:5390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >See, this is what I mean about computer scientists. The computational >model I work with is realistic---it's just my mental picture of what can >be coded on lots of real machines. As I said before, it's finite. It has >very, very little to do with a Turing machine. But the program you write to do the testing you describe requires some memory. Hence, because of your finite machine, there are some problems which the program under test cannot solve which it would have been able to solve had you given it that extra memory. If it cannot solve the problem (i.e., if it gives a different answer) then it might go into a loop. For example, let's try this pseudoprogram: const x = any integer; begin for i := 0 to x do begin y = malloc(1); if (y == NULL) begin while (1) ; end end end. For any given size machine, there will be a value for X where the program will not halt when you test it but will halt if you run it alone. An "almost right" solution to the halting problem may be useful, but I wouldn't call it "a practical solution to the halting problem". -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, Formal Description Techniques (esp. Estelle), Coffee, Amigas ----- =+=+=+ Let GROPE be an N-tuple where ... +=+=+=
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/16/90)
In article <11897@life.ai.mit.edu> misha@just-right.ai.mit.edu (Mike Bolotski) writes: > In article <5785:Nov1519:19:5390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >If you have a program with a set of variables that enter a loop at time > >t, and continue to loop in a cycle of length l, then the method outlined > >will run the program in twice the memory at one-third speed minus > >housekeeping, and detect the loop between t and t + l, i.e., during its > >first cycle. > That's fine, Dan. What if the cycle length is several millenia? Then it will be detected in at most several times three millenia. But I've never seen this happen *in practice*. Have you ever debugged a program to find an infinite loop that would take such a long time, or are you just arguing for the sake of argument? A few examples of the former wouldn't diminish the practical value of the solution, but I'd be interested in seeing them anyway. > >the worst case it'll still detect the loop eventually, though I don't > >think these theoretical statements matter for the real world. > The real world being defined as your experience alone, is it? Again, I invite comments from anyone whose experience differs. I haven't seen any such comments yet. > >See, this is what I mean about computer scientists. The computational > >model I work with is realistic---it's just my mental picture of what can > >be coded on lots of real machines. As I said before, it's finite. It has > No need to apologize for your limitations, Dan. I insist upon apologizing. I simply cannot bring myself to imagine a computer with an infinite amount of memory. When I imagine a byte being sent to memory, the computer explodes and settles into dust. When I picture a Turing machine, it has a lot of tape stretching off into the distance, but I just can't see each and every bit on the tape all at once. Maybe this is just because in my finite experience I've never seen how an infinite computer would work, or where it would be stored. I'm also a firm believer in propositional set theory, if you're mathematically inclined enough to know what that is. Tarski's last book (with Givant) is my bible on these matters. If you in your infinite wisdom would deign to explain to me how to visualize the infinitely powerful computer of yours, I'd be eternally grateful. No, scrap that, I'd be finitely grateful. ---Dan
gudeman@cs.arizona.edu (David Gudeman) (11/16/90)
In article <6045:Nov1519:34:2290@kramden.acf.nyu.edu> Dan Bernstein writes:
]Well, I can't remember ever debugging a non-terminating program that
]*didn't* have a rather simple infinite loop, and I remember debugging
]lots of programs where the loop was simple. Does your experience differ?
The word "simple" here is ambiguous. If you mean that the loop was
fairly small, I guess most of them are. If you mean that the number
of states traversed in a cycle is small, then yes, my experience
differs. It seems to me that there is almost always at least some
monotonic action going on in a loop (which is the reason for having
the loop), and this action will create very long state cycles.
]I'd be interested in seeing your example.
Here's the simplest form: you accidentally use the wrong exit
condition:
for (i = start; i != -1; i++) ...
If "start" begins as a non-negative number, you've got a long wait
ahead of you.
]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.
Oh, well. If I'd known you had such a huge sample space, I would
never have had the nerve to question you. I guess if I have
enountered one beligerant mathematician I can just assume this is
typical of the field.
And furthermore, you have _not_ solved it. If your proposal were
implemented there would still be programs that would never --for all
practical purposes-- terminate. How has life changed? All you have
done is decreased the likelihood of such an eventuallity, by some
unknown amount that --in the absence of further evidence-- reasonable
people can disagree on.
] 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*.
There are a lot of things that should be done that no one has time
for. There is so much _real_ research involved in designing and
implementing programming languages, that this just hasn't recieved
much attention. It is far from being the most important thing that
has been neglected in the field. Many of us would even go so far as
to say that this is not a matter of research, but of engineering, and
therefore outside the realm of computer science.
]Just undecidability.
Hmm. Are you claiming here that if something is undecideable in
theory that there is necessarily no practical approximation? Weren't
you just bashing an anonymous computer scientist for such an opinion?
] 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
Depends on your model. Assertions about the complexity of sorting
rely by necessity on the underlying model. I can produce a model
where sorting time is a constant. As to whether your model is better
than others, that is a matter of opinion. Personally, I happen to
agree with you on this one, but I wouldn't go about insulting people
because they disagree with me.
] that finding the optimal
]pointer version of array code is decidable
Again, a matter of the model in use. Everyone else in the world was
assuming a model where the weights of the paths was given as part of
the input (or assumed to be uniform). After you finally clued us in
about how your model differed, the argument degenerated to opinions on
models.
--
David Gudeman
Department of Computer Science
The University of Arizona gudeman@cs.arizona.edu
Tucson, AZ 85721 noao!arizona!gudemanbrnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/16/90)
In article <36480@nigel.ee.udel.edu> new@ee.udel.edu (Darren New) writes: > In article <5785:Nov1519:19:5390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: > >See, this is what I mean about computer scientists. The computational > >model I work with is realistic---it's just my mental picture of what can > >be coded on lots of real machines. As I said before, it's finite. It has > >very, very little to do with a Turing machine. > But the program you write to do the testing you describe requires some memory. Did you read the original description? The first setup I described has two computers, side by side, one running twice as fast as the other. Cache chips---which already do almost all the necessary work---handle the housekeeping. There is no memory loss. The programs work as usual. If your machine is multiprocessing, then it's better to have two processes running side by side than to duplicate the hardware. This does imply some memory use---but in such an environment you can't assume a fixed memory size anyway. > For any given size machine, there will be a value for X where the program > will not halt when you test it but will halt if you run it alone. An "almost > right" solution to the halting problem may be useful, Your objections are based upon the supposed change in the computer's configuration. Hence they are moot. ---Dan
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/16/90)
In article <11900@life.ai.mit.edu> misha@just-right.ai.mit.edu (Mike Bolotski) writes: > And I like the > ever-so-subtle transition from optimal addition sequence to > pointer version of array code. See, this is what I mean about computer scientists. Anyone who bothers to think about the problem will understand why, in a general computation, converting array references to pointer references is the same as finding an optimal addition chain. (Hint: In machine language, how are array references implemented?) By the way, why do you insist upon repeatedly misquoting the phrase ``optimal addition chain in a general computation''? Which word don't you understand? > And just how seriously do you expect your opinions to be taken if > you haven't read the basic references about compiler construction > or theory of computation? I have read each of the AHU/ASU/etc books. Once. I find none of them particularly useful as references, as everything they say is presented more to my taste either in Knuth or in original research articles. I certainly find it amusing that you consider the currently fashionable elementary textbooks to be ``basic references.'' ---Dan
new@ee.udel.edu (Darren New) (11/16/90)
In article <27546@megaron.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes: >In article <6045:Nov1519:34:2290@kramden.acf.nyu.edu> Dan Bernstein writes: >]Well, I can't remember ever debugging a non-terminating program that >]*didn't* have a rather simple infinite loop, and I remember debugging >]lots of programs where the loop was simple. Does your experience differ? > >The word "simple" here is ambiguous. If you mean that the loop was >fairly small, I guess most of them are. If you mean that the number >of states traversed in a cycle is small, then yes, my experience >differs. It seems to me that there is almost always at least some >monotonic action going on in a loop (which is the reason for having >the loop), and this action will create very long state cycles. > >]I'd be interested in seeing your example. > Here is a really simple example that has stung me a couple of times. Once, this ran for two days before I noticed it had never finished. $ cat xyz* >xyzzy This will eventually fill up the entire disk, never once entering the same state. -- Darren -- --- Darren New --- Grad Student --- CIS --- Univ. of Delaware --- ----- Network Protocols, Graphics, Programming Languages, Formal Description Techniques (esp. Estelle), Coffee, Amigas ----- =+=+=+ Let GROPE be an N-tuple where ... +=+=+=
misha@gracilis.ai.mit.edu (Mike Bolotski) (11/17/90)
In article <13046:Nov1604:16:4390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes: >See, this is what I mean about computer scientists. Actually, Dan, I happen to be an electrical engineer. > Anyone who bothers >to think about the problem will understand why, in a general >computation, converting array references to pointer references is the >same as finding an optimal addition chain. (Hint: In machine language, >how are array references implemented?) Hint: a general computation does not require arrays at all. >>By the way, why do you insist upon repeatedly misquoting the phrase >``optimal addition chain in a general computation''? Which word don't >you understand? Oh, I understand all of the above words as used in the conventional literature. Seeing as you insist on redefining each of them to suit your current argument of the day, I suppose it would be helpful if you went ahead and actually defined your terminology. >> And just how seriously do you expect your opinions to be taken if >> you haven't read the basic references about compiler construction >> or theory of computation? > >I have read each of the AHU/ASU/etc books. Once. I find none of them >particularly useful as references, as everything they say is presented >more to my taste either in Knuth or in original research articles. I >certainly find it amusing that you consider the currently fashionable >elementary textbooks to be ``basic references.'' Basic, Dan. As in: "you have to be familiar with the content to be taken seriously." Now, either you've read the books and disagree with the authors, or you haven't read the books closely enough to comment. Now, about that quote I provided. Do you agree with the authors or do your basic definitions differ? And I'm getting close to Jim's level of frustration with discussing anything with you. How about steering the discussion away from ad hominem attacks, accusations of lying, etc, etc, and back to technical issues. For starters, you could answer my question about the ASU quote. Mike Bolotski Artificial Intelligence Laboratory, MIT misha@ai.mit.edu Cambridge, MA
dbc@bushido.uucp (Dave Caswell) (11/18/90)
.There does not exist an algorithm that will convert an (optimal) array .program into its optimal pointer form. That summarizes what I've said so .far in this thread. . .What does it mean for real languages? It means that the programmer .*must* be allowed to look at an array x from the vantage point of x[a], .rather than x[0]. This array shifting doesn't have to look like C's Clearly that isn't a proof. The word "*must*" is inappropriate in that context. -- David Caswell dbc%bushido.uucp@umich.edu
smryan@garth.UUCP (Steven Ryan) (11/20/90)
>> 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. I assume this includes checking each reel of tape in the library that the program has accessed, each reel of tape that the program accessed but have been moved off site because the tape library is full, and eventually every reel of tape which was moved off planet because the planet is full. Can you really put an a priori bound on the length of the tape? I suppose we could put bounds based on the number of atoms in the universe, IF you can deduce the number of atoms. (Deduce is not the same thing physics does.) -- ...!uunet!ingr!apd!smryan Steven Ryan ...!{apple|pyramid}!garth!smryan 2400 Geng Road, Palo Alto, CA
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/20/90)
In article <1990Nov18.024745.2424@bushido.uucp> dbc@bushido.uucp (Dave Caswell) writes: > .There does not exist an algorithm that will convert an (optimal) array > .program into its optimal pointer form. That summarizes what I've said so > .far in this thread. > .What does it mean for real languages? It means that the programmer > .*must* be allowed to look at an array x from the vantage point of x[a], > .rather than x[0]. This array shifting doesn't have to look like C's > Clearly that isn't a proof. The word "*must*" is inappropriate in that > context. You're right. What I should have said was ``If the language doesn't let the programmer look at [etc.] ... then it will be restricting his freedom to express certain optimizations.'' To a language designer, that means that the language *must* provide some equivalent feature; but most people don't care to design languages. ---Dan
jrbd@craycos.com (James Davies) (11/21/90)
>> 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. main(argc,argv) { int I_halt(); if (I_halt(argv[0])) { while(1); } else { exit(0); } } Please write I_halt. It should return 1 if its argument program halts, 0 if it doesn't. Feel free to consult books or notes, other programmers, Nobel prize winners, etc.
brnstnd@kramden.acf.nyu.edu (Dan Bernstein) (11/21/90)
Skip if you saw James' error. In article <1990Nov20.213454.10879@craycos.com> jrbd@craycos.com (James Davies) writes: > >>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. > main(argc,argv) { > int I_halt(); > if (I_halt(argv[0])) { > while(1); > } else { > exit(0); > } > } > Please write I_halt. It should return 1 if its argument program > halts, 0 if it doesn't. We are all aware that it is impossible for a fixed algorithm *within* machine M to solve the halting problem for machine M (provided that M is not utterly trivial). But the solution takes advantage of a new machine *outside* M. Your artificially restricted question has nothing to do with the problem at hand. > Feel free to consult books or notes, > other programmers, Nobel prize winners, etc. Your sarcasm would be more appropriate if you had shown that you understood anything written in previous articles in this thread. ---Dan
smryan@garth.UUCP (Steven Ryan) (11/22/90)
You may find this shocking, but some of us don't care if array references
can be made optimal--for the machine. How about array references which are
optimal for the programmer? Neither C nor Fortran do that as well as Algol
60 did, thirty years ago.
There are other considerations than grinding out the fastest possible object
code.
--
...!uunet!ingr!apd!smryan Steven Ryan
...!{apple|pyramid}!garth!smryan 2400 Geng Road, Palo Alto, CA