Pathologically Eclectic Rubbish Lister  
PerlMonks 
Comment on 
( #3333=superdoc: print w/ replies, xml )  Need Help?? 
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 theoremproving software could sift their way through all the permutations, spitting out every possible wellformed program along the way.
I misspoke.. the automatic programming problem is AIcomplete, not NPcomplete. The halting problem is, indeed, impossible to solve with a Turning machine, which I believe Von Neumann classified as a 'type0' computer. However, a Von Neumann 'type1' computer (if I've got the numbers right), can solve the halting problem. A type1 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 bruteforce 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.
Point taken, though one could probably call that a compiler issue.. IIRC, the ANSIC spec defines all floatingpoint 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

