Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
Says mstone:
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.
Perhaps I misunderstand your meaning, but it seems to me that Gödel's first incompleteness theorem says exactly that algebra cannot be reduced to a finite set of postulates.
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.
You seem to have a deep misunderstanding of the halting problem. Right now, we believe that no method, including "brute-force examination", can determine if every program halts. If "brute-force examination" were sufficient, one would write a computer program to perform the brute-force examination and come up with the answer. But this is precisely what we know is impossible.

As a very simple example, consider this program:

use Math::BigInt; my $N = Math::BigInt->new(shift @ARGV); while (1) { $N += 1; next unless prime($N); next unless prime($N+2); print "$N\n"; exit; } sub prime { my $n = shift; for (my $i = Math::BigInt->new(2); $i * $i <= $n; $i += 1) { return 0 if $n % $i == 0; } return 1; }
You can't tell me whether this program will halt on all inputs. Not by "brute force examination" or by any other method. Why not? Because you don't know how to figure that out. Neither does anyone else.

I won't address your assertion that a solution to the halting problem will provide a solution to "the automatic programming problem", because you still haven't said what "the automatic programming problem" is, and I'm starting to suspect that you don't have a very clear idea of it yourself.

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.
No, you couldn't. The proof completely rules out this exact possibility. I don't think you could understand the proof and still believe this.

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.
You're the one that brought it up; if you wanted to leave compiler-dependent issues out of the discussion, you should have done that. As for the square root of 2, what of it? Are you now saying that code to compute the square root of 2 will fail "as often as not"? That isn't true either.

The term elim does not appear in the 1999 C language standard, which I consulted before posting my original reply.

--
Mark Dominus
Perl Paraphernalia


In reply to Re: (OT) Where is programming headed? by Dominus
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 imbibing at the Monastery: (4)
    As of 2014-09-30 21:39 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (384 votes), past polls