"Another result (the unsolvability of the halting problem) may be
interpreted as implying the impossibility of constructing a program for
determining whether or not an arbitrary given program is free of 'loops'."
Martin Davis, Computability and Unsolvability, 1958
--Joe
On 4/17/13 10:43 PM, Russ Abbott wrote:
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 <http://ssrn.com/abstract=1977688>/
/ Google voice: 747-/999-5105
Google+: plus.google.com/114865618166480775623/
<https://plus.google.com/114865618166480775623/>
/ vita: /sites.google.com/site/russabbott/
<http://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
<mailto: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 unsubscribehttp://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
--
"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
