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
