The problem isn't really looping vs stopping; it's searching vs. finding. Searching might be expressed iteratively (as a loop) or recursively. But what the program is really doing is looking for an element that satisfies some criterion. In many cases, it's not known in advance whether one exists. The only way to find one is to search sequentially through the space of possibilities, which may be infinite. If there is no element that satisfies the criterion, the search never ends, and the program never stops.
*-- Russ Abbott* *_____________________________________________* *** Professor, Computer Science* * California State University, Los Angeles* * My paper on how the Fed can fix the economy: ssrn.com/abstract=1977688* * Google voice: 747-*999-5105 Google+: plus.google.com/114865618166480775623/ * vita: *sites.google.com/site/russabbott/ CS Wiki <http://cs.calstatela.edu/wiki/> and the courses I teach *_____________________________________________* On Wed, Apr 17, 2013 at 9:30 PM, Joseph Spinden <j...@qri.us> wrote: > You can state it pretty simply: There is no algorithm that can decide > whether an arbitrary computer program will ever stop (Halt), or will loop > endlessly.. > > Definitely a problem for software testing.. > > Joe > > > > On 4/17/13 10:15 PM, Owen Densmore wrote: > > Nick: its simple. I married her. Just after explaining Godel to the > philosophy department, and to her Ex who promptly left philosophy and > became a cardio doctor. True. > > In terms of the Halting problem, is Wikipedia too formal? The first two > paragraphs: > > In computability theory, the halting problem can be stated as follows: > "Given a description of an arbitrary computer program, decide whether the > program finishes running or continues to run forever". This is equivalent > to the problem of deciding, given a program and an input, whether the > program will eventually halt when run with that input, or will run forever. > > Alan Turing proved in 1936 that a general algorithm to solve the > halting problem for all possible program-input pairs cannot exist. A key > part of the proof was a mathematical definition of a computer and program, > what became known as a Turing machine; the halting problem is undecidable > over Turing machines. It is one of the first examples of a decision problem. > > > Did you find that foreign? Dede doesn't. > > But then she lived in Silly Valley for 20+ years .. its in the air > there. She thinks math is sexy .. well, hmm, that I am and she puts up > with the math. > > Don't forget I invited you to viewing and discussing Michael Sendel's > Justice and you never antied up. I think its time you read up on > computation theory or discrete math, your choice. You'd love it. > > We've all jumped into your seminars and read your stuff. Your turn. > > -- Owen > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > > > > -- > > "Sunlight is the best disinfectant." > > -- Supreme Court Justice Louis D. Brandeis, 1913. > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
