note
mstone
<p>
<br>> > Programmers will be necessary until someone solves the halting
<br>> > problem. The automatic programming problem (writing a program that
<br>> > writes programs for you) has been proven NP-complete.
<br>>
<br>> I'm not sure what you mean here, and most of the obvious
<br>> interpretations are false. If you mean that it's impossible to
<br>> write a program that writes programs, that's wrong, because I have
<br>> a program here that I use every day that takes an input
<br>> specification and writes a machine language program to implement
<br>> that specification; it's called gcc. Programs write other programs
<br>> all the time.
</p>
<p>
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).
</p>
<p>
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.
</p>
<p>
<br>> I doubt if there's any meaningful sense in which "the automatic
<br>> programming problem" (whatever that is) can be shown to be
<br>> NP-complete. If you mean that it's equivalent to the halting problem,
<br>> you might also want to note that the halting problem is not
<br>> NP-complete, and revise accordingly.
</p>
<p>
I misspoke.. the automatic programming problem is <b>AI</b>-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.
</p>
<p>
However, a Von Neumann 'type-1' computer (if I've got the numbers
right), <i>can</i> 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.
</p>
<p>
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 <i>can</i> 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.
</p>
<p>
Either way, my original assertion still stands. A solution to the halting problem would
generate a solution to automatic programming, and vice versa.
</p>
<p>
<br>> But you're mistaken; the result of the test is guaranteed to be true.
<br>> Certain float values can be compared exactly, and 1 is among those
<br>> values.
</p>
<p>
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 <code>elim</code>.
</p>
<p>
Please insert the code necessary to calculate the square root of 2.
</p>
<p>
mike
<br>.
</p>
131789
132063