Isomorphism between computation and philosophy

[Joe Spinden]

"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
  Google voice: 747-999-5105

  Google+: plus.google.com/114865618166480775623/

  vita:  sites.google.com/site/russabbott/

  CS Wiki and the courses I teach
_____________________________________________ 

On Wed, Apr 17, 2013 at 9:30 PM, Joseph Spinden <[hidden email]> 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

============================================================
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

[Joe Spinden]

I was suggesting the contributors to this chat could "go read the
Wikipedia article" to give them something useful to say to the beautiful
woman about the halting problem. (Not to be taken to imply that none of
the readers if this are beautiful women, only some of the readers..)

Joe



On 4/17/13 11:04 PM, Nicholas Thompson wrote:

> I don't think the beautiful woman would accept "go read the Wikipedia
> article" as am answer.
>
> N
>
> -----Original Message-----
> From: Friam [mailto:[hidden email]] On Behalf Of Joseph Spinden
> Sent: Wednesday, April 17, 2013 8:21 PM
> To: The Friday Morning Applied Complexity Coffee Group
> Subject: Re: [FRIAM] Isomorphism between computation and philosophy
>
> Owen is right that there are N! ways to map a set of N objects 1-1, onto
> another set of N objects. The first object can go to 1 of N objects, the
> next to 1 of N-1, etc. That's pretty standard.
>
> As to the Halting Problem, Why not start with the first few lines of the
> Wikipedia article ? That is simple and easy to understand.
>
> Joe
>
>
>
>
> On 4/17/13 7:32 PM, [hidden email] wrote:
>> Nick asks Owen:
>>    
>>> So, Owen, you meet a beautiful woman at a cocktail party.  She seems
>>> intelligent, not a person to be fobbed off, but has no experience
>>> with either Maths or Computer Science.  She looks deep into your
>>> eyes, and asks "And what, Mr. Densmore, is the halting problem?"  You
>>> find yourself torn between two impulses.  One is to use the language
>>> that would give you credibility in the world of your mentors and
>>> colleagues.  But you realize that that language is going to be of
>>> absolutely no use to her, however ever much it might make you feel
> authoritative to use it.  She expects an answer.
>>> Yet you hesitate.  What language do you use?
>>>
>>> You would start, would you not, with the idea of a "problem."  A
>>> problem is some sort of difficulty that needs to be surmounted.
>>> There is a goal and something that thwarts that goal.  What are these
> elements in the halting
>>> PROBLEM?    And why is HALTING a problem?
>> Nick, Owen may well disagree, but from my point of view you've already
>> staked a dubious claim, by assuming (defensably) that "problem" in the
>> MathEng phrase "Halting Problem" can and should be understood to be
>> the same word as "problem" in your dialect of English.  But this is, I
> think, a false assumption.  Now, at least, whatever the case was when the
> "Halting Problem"
>> got its original name (in MathGerman, I think), the meaning that
>> "Halting Problem" conveys in MathEng is the same (or nearly the same)
>> as that conveyed by "Halting Question".  "Problem" is there for
>> historical reasons, just as, in geometric topology, a certain question
>> of considerable interest and importance (which has been answered for
>> fewer decades than has the "Halting Problem") is still called--even in
> MathEng!--"the Hauptvermutung".  The framing in terms of "a goal" and
> "something that thwarts" is delusive.  There is, rather, "a question"
>> and--if you must be florid--a "quest for an answer".  Note, "*an*
>> answer".  Of course, at an extreme level (I can't decide whether it's
>> the highest or the lowest: I *hate* "level" talk precisely for this
>> kind of reason) there is *the* answer ("no").  But that isn't, in
>> itself, very interesting (any more: of course it was before it was
>> known to be "the" answer).  *How* you get to "no" is interesting, and
>> there are (by now) many different "hows" (for the "Halting Question", the
> Hauptvermutung, Poincare's Conjecture, and so forth and so on), each of
> which is *an* answer (as are many of the "not hows").
>> ============================================================
>> 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

[Marcus G. Daniels]

On 4/18/13 7:57 AM, Joseph Spinden wrote:

"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'."

Well, compilers can't reason about all forms of loops, but note how the compiler realized that the accumulating
"sum" didn't require iteration.   (In the assembly it collapses to a "movl $30,%eax".)  Flat maps and reductions with simple transformation/aggregation functions can be determined to exit. 

$ cat collapse.c
int
main ()
{
   unsigned i;
   unsigned sum = 0;

   for (i = 0; i < 10; i++) sum += 3;
   return sum;
}
$ gcc -S -O3 collapse.c
$ cat collapse.s
    .file    "collapse.c"
    .section    .text.startup,"ax",@progbits
    .p2align 4,,15
    .globl    main
    .type    main, @function
main:
.LFB0:
    .cfi_startproc
    movl    $30, %eax
    ret
    .cfi_endproc
.LFE0:
    .size    main, .-main
    .ident    "GCC: (GNU) 4.7.2 20121109 (Red Hat 4.7.2-8)"
    .section    .note.GNU-stack,"",@progbits

============================================================
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

[glen ropella]

Joseph Spinden wrote at 04/17/2013 07:21 PM:
> Owen is right that there are N! ways to map a set of N objects 1-1, onto
> another set of N objects. The first object can go to 1 of N objects, the
> next to 1 of N-1, etc. That's pretty standard.

Well, saying there are N! maps is different from saying there are N!
ways to map.  While there may only be N! potential maps, there are many
many more ways to demonstrate or realize those maps.

The difference lies in the methods, something that is often left out of
math presentations.  This is one area where I think computation helps
boost the intuitionist or constructivist sense of math, as well as the
incremental/iterative conception of sets.

--
=><= glen e. p. ropella
Or at least come to a show


============================================================
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

[Nick Thompson]

And I am trying to get folks here to confront the problem of putting in
their own words things they think are obvious for other folks for whom these
things are not obvious.

-----Original Message-----
From: Friam [mailto:[hidden email]] On Behalf Of Joseph Spinden
Sent: Thursday, April 18, 2013 8:06 AM
To: The Friday Morning Applied Complexity Coffee Group
Subject: Re: [FRIAM] Isomorphism between computation and philosophy

I was suggesting the contributors to this chat could "go read the Wikipedia
article" to give them something useful to say to the beautiful woman about
the halting problem. (Not to be taken to imply that none of the readers if
this are beautiful women, only some of the readers..)

Joe



On 4/17/13 11:04 PM, Nicholas Thompson wrote:

> I don't think the beautiful woman would accept "go read the Wikipedia
> article" as am answer.
>
> N
>
> -----Original Message-----
> From: Friam [mailto:[hidden email]] On Behalf Of Joseph
> Spinden
> Sent: Wednesday, April 17, 2013 8:21 PM
> To: The Friday Morning Applied Complexity Coffee Group
> Subject: Re: [FRIAM] Isomorphism between computation and philosophy
>
> Owen is right that there are N! ways to map a set of N objects 1-1,
> onto another set of N objects. The first object can go to 1 of N
> objects, the next to 1 of N-1, etc. That's pretty standard.
>
> As to the Halting Problem, Why not start with the first few lines of
> the Wikipedia article ? That is simple and easy to understand.
>
> Joe
>
>
>
>
> On 4/17/13 7:32 PM, [hidden email] wrote:
>> Nick asks Owen:
>>    
>>> So, Owen, you meet a beautiful woman at a cocktail party.  She seems
>>> intelligent, not a person to be fobbed off, but has no experience
>>> with either Maths or Computer Science.  She looks deep into your
>>> eyes, and asks "And what, Mr. Densmore, is the halting problem?"  
>>> You find yourself torn between two impulses.  One is to use the
>>> language that would give you credibility in the world of your
>>> mentors and colleagues.  But you realize that that language is going
>>> to be of absolutely no use to her, however ever much it might make
>>> you feel
> authoritative to use it.  She expects an answer.
>>> Yet you hesitate.  What language do you use?
>>>
>>> You would start, would you not, with the idea of a "problem."  A
>>> problem is some sort of difficulty that needs to be surmounted.
>>> There is a goal and something that thwarts that goal.  What are
>>> these
> elements in the halting
>>> PROBLEM?    And why is HALTING a problem?
>> Nick, Owen may well disagree, but from my point of view you've
>> already staked a dubious claim, by assuming (defensably) that
>> "problem" in the MathEng phrase "Halting Problem" can and should be
>> understood to be the same word as "problem" in your dialect of
>> English.  But this is, I
> think, a false assumption.  Now, at least, whatever the case was when
> the "Halting Problem"
>> got its original name (in MathGerman, I think), the meaning that
>> "Halting Problem" conveys in MathEng is the same (or nearly the same)
>> as that conveyed by "Halting Question".  "Problem" is there for
>> historical reasons, just as, in geometric topology, a certain
>> question of considerable interest and importance (which has been
>> answered for fewer decades than has the "Halting Problem") is still
>> called--even in
> MathEng!--"the Hauptvermutung".  The framing in terms of "a goal" and
> "something that thwarts" is delusive.  There is, rather, "a question"
>> and--if you must be florid--a "quest for an answer".  Note, "*an*
>> answer".  Of course, at an extreme level (I can't decide whether it's
>> the highest or the lowest: I *hate* "level" talk precisely for this
>> kind of reason) there is *the* answer ("no").  But that isn't, in
>> itself, very interesting (any more: of course it was before it was
>> known to be "the" answer).  *How* you get to "no" is interesting, and
>> there are (by now) many different "hows" (for the "Halting Question",
>> the
> Hauptvermutung, Poincare's Conjecture, and so forth and so on), each
> of which is *an* answer (as are many of the "not hows").
>> ============================================================
>> 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

[Owen Densmore]

On Thu, Apr 18, 2013 at 10:08 AM, Nicholas Thompson <[hidden email]> wrote:

And I am trying to get folks here to confront the problem of putting in
their own words things they think are obvious for other folks for whom these
things are not obvious.

This reminds me of Einsteins famous quote: Everything should be made as simple as possible, but not simpler.

And, forgive me Nick, you have the same problem too, right?  At times your discourse tends to be as specialized as any techy's, I think.

   -- 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

[Nick Thompson]

Owen wrote –

 

At times your discourse tends to be as specialized as any techy's, I think.

 

Nick replies --  Well, then call me on it!  There is nothing that drives me wilder – in myself or others ---- than pretentious bafflegab.  The problem becomes more difficult when one is talking to a highly various audience like FRIAM.  But any time you – owen -- don’t understand something that I am saying, demand clarification and  I will do my best to find a common language by which to express myself.  Another fair question you might ask, is, “Ytf should I care?”  This sort of intensive communication may involve going off line, lest I drive the list nuts, because, as you all know, I am relentless about this sort of thing.  And of course, there is always the possibility of discovering that the thing one was trying to say was not clear in the first place.  Those are ugly but educative moments.

 

There is an important distinction between communicating and mouthing off and I am determined to honor it. 

 

Nick

 

From: Friam [mailto:[hidden email]] On Behalf Of Owen Densmore
Sent: Thursday, April 18, 2013 10:49 AM
To: The Friday Morning Applied Complexity Coffee Group
Subject: Re: [FRIAM] Isomorphism between computation and philosophy

 

On Thu, Apr 18, 2013 at 10:08 AM, Nicholas Thompson <[hidden email]> wrote:

And I am trying to get folks here to confront the problem of putting in
their own words things they think are obvious for other folks for whom these
things are not obvious.

 

This reminds me of Einsteins famous quote: Everything should be made as simple as possible, but not simpler.

 

And, forgive me Nick, you have the same problem too, right?  At times your discourse tends to be as specialized as any techy's, I think.

 

   -- 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