Beefy Boxes and Bandwidth Generously Provided by pair Networks Bob
laziness, impatience, and hubris
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??


> > Programmers will be necessary until someone solves the halting
> > problem. The automatic programming problem (writing a program that
> > writes programs for you) has been proven NP-complete.
>
> I'm not sure what you mean here, and most of the obvious
> interpretations are false. If you mean that it's impossible to
> write a program that writes programs, that's wrong, because I have
> a program here that I use every day that takes an input
> specification and writes a machine language program to implement
> that specification; it's called gcc. Programs write other programs
> all the time.

gcc doesn't 'write programs' per se, it just translates programs you've written in one formal language (C) to another formal language (machine code).

Automatic programming boils down to the deep theoretical question of whether all programming can be reduced to a finite set of generative postulates, the way, say, algebra can. If that were true, programmers would be unnecessary. A few supercomputers with theorem-proving software could sift their way through all the permutations, spitting out every possible well-formed program along the way.


> I doubt if there's any meaningful sense in which "the automatic
> programming problem" (whatever that is) can be shown to be
> NP-complete. If you mean that it's equivalent to the halting problem,
> you might also want to note that the halting problem is not
> NP-complete, and revise accordingly.

I misspoke.. the automatic programming problem is AI-complete, not NP-complete. The halting problem is, indeed, impossible to solve with a Turning machine, which I believe Von Neumann classified as a 'type-0' computer.

However, a Von Neumann 'type-1' computer (if I've got the numbers right), can solve the halting problem. A type-1 Von Neumann machine has an infinite tape full of ones and zeros, where the address of each cell corresponds to a unique C program, and the value of each cell is a boolean that says whether the program halts or not. In other words, it's a giant lookup table.

Right now, we don't know if that binary sequence can be found by any means other than brute-force examination of every possible program. However, if programming can be reduced to a finite set of generative postulates, it may be possible to calculate the value of any given bit in finite time. It might even be possible to calculate that value with a Turing machine.. in which case, we could sidestep the current proof for the halting problem's unsolvability without actually contradicting it.

Either way, my original assertion still stands. A solution to the halting problem would generate a solution to automatic programming, and vice versa.


> But you're mistaken; the result of the test is guaranteed to be true.
> Certain float values can be compared exactly, and 1 is among those
> values.

Point taken, though one could probably call that a compiler issue.. IIRC, the ANSI-C spec defines all floating-point representations in terms of a minimal error variable elim.

Please insert the code necessary to calculate the square root of 2.

mike
.


In reply to Re: Re: (OT) Where is programming headed? by mstone
in thread (OT) Where is programming headed? by Ovid

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others drinking their drinks and smoking their pipes about the Monastery: (10)
    As of 2014-04-20 17:48 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      April first is:







      Results (485 votes), past polls