No, even perfect specs do not preclude the need for programmers. Not yet. There are three milestones:
The perfect specification.
A working program.
A proof that the program satisfies the specification.
Even when you have the first 2, the third is equivalent to theorem proving, which I believe is at least NP-hard, if not outright undecidable in the general case. When you don’t even have the program… well, we don’t have a sufficiently fast Solomonov Inducer yet. So we’re back to writing the program with human minds.
You insist that there is something a machine cannot do. If you tell me precisely what it is a machine cannot do, then I can always make a machine which will do just that.
-- John von Neumann
By “always,” Neumann means it’s an algorithmic task: turning sufficiently precise requirements into a machine is doable by a machine; it’s what compilers do. Most compilers are not proven correct; but a few are.
I think we do not mean the same thing by “requirement”. I thought about things like “Write a function that sorts an array”, or in more precise terms “let f(A) be such that for any n, f(A)[n]<=f(A)[n+1]” (where “<=” is supposed to be a total order relation, and one or two more nits to pick).
What you (and CronoDAS) probably have in mind is more like a complete algorithm, such as quick-sort, or bubble-sort. Which in a sense, already is a complete program. (C code is hardly called “requirement”.)
I think my point stands. There is no algorithm that proves, in the general case, that any program satisfies the most basic requirement: eventually stop his work, so it can display the damn result.
I don’t know, but my guess is, there is no algorithm that writes programs which satisfies any given unambiguous specification (and guarantees to finish in finite time).
Well, consider your sort example. I can just shuffle the array randomly until your specification is met, or i can do all the possible things to do until your specification is met. It’s the efficient implementations that are a problem. I can easily program a horrifically inefficient AI—a program just iterates through all programs starting from shortest and runs them for specific number of steps, and puts them against a set of challenges solutions to which are substantially larger than the programs being iterated. If AI is at all possible, that will work.
It is possible to make algorithms for important enough subset of the possible specifications, even though it is impossible in general (e.g. you can specify the halting probability, but you can’t compute it).
In von Neumann’s defense, he may have said this before the strong negative results in computability theory. Machines cannot do lots of stuff.
There is the overwhelmingly clear implication in von Neumann’s claim that the ‘something’ in question is ‘something that a human can do that a machine cannot do’. If we are going to abandon that assumption we can skip computability theory and go straight to “Travel faster than light. Ha!”
What there is difficult for you to understand? I can’t make it much simpler than that and it seems to be more or less well formed vernacular.
If you are trying in a backhanded way to make the point “Humans are machines! The set you mention is empty!” then yes, that is rather close to von Neumann’s point.
If you are trying in a backhanded way to make the point “Humans are machines! The set you mention is empty!” then yes, that is rather close to von Neumann’s point.
Indeed, I can’t think of any plausible meanings for machine, do and tell which would make that quotation non-tautological but true.
Sorry. What I meant is that computer programs can’t speak English, or any other natural language. When you get a program that can speak English it will most likely be trivial to make a program that does the translation CronoDAS was talking about.
No, even perfect specs do not preclude the need for programmers. Not yet. There are three milestones:
The perfect specification.
A working program.
A proof that the program satisfies the specification.
Even when you have the first 2, the third is equivalent to theorem proving, which I believe is at least NP-hard, if not outright undecidable in the general case. When you don’t even have the program… well, we don’t have a sufficiently fast Solomonov Inducer yet. So we’re back to writing the program with human minds.
-- John von Neumann
By “always,” Neumann means it’s an algorithmic task: turning sufficiently precise requirements into a machine is doable by a machine; it’s what compilers do. Most compilers are not proven correct; but a few are.
I think we do not mean the same thing by “requirement”. I thought about things like “Write a function that sorts an array”, or in more precise terms “let f(A) be such that for any n, f(A)[n]<=f(A)[n+1]” (where “<=” is supposed to be a total order relation, and one or two more nits to pick).
What you (and CronoDAS) probably have in mind is more like a complete algorithm, such as quick-sort, or bubble-sort. Which in a sense, already is a complete program. (C code is hardly called “requirement”.)
I think my point stands. There is no algorithm that proves, in the general case, that any program satisfies the most basic requirement: eventually stop his work, so it can display the damn result.
I don’t know, but my guess is, there is no algorithm that writes programs which satisfies any given unambiguous specification (and guarantees to finish in finite time).
Well, consider your sort example. I can just shuffle the array randomly until your specification is met, or i can do all the possible things to do until your specification is met. It’s the efficient implementations that are a problem. I can easily program a horrifically inefficient AI—a program just iterates through all programs starting from shortest and runs them for specific number of steps, and puts them against a set of challenges solutions to which are substantially larger than the programs being iterated. If AI is at all possible, that will work.
It is possible to make algorithms for important enough subset of the possible specifications, even though it is impossible in general (e.g. you can specify the halting probability, but you can’t compute it).
In von Neumann’s defense, he may have said this before the strong negative results in computability theory. Machines cannot do lots of stuff.
There is the overwhelmingly clear implication in von Neumann’s claim that the ‘something’ in question is ‘something that a human can do that a machine cannot do’. If we are going to abandon that assumption we can skip computability theory and go straight to “Travel faster than light. Ha!”
Speak English
EDIT: That is an example of what you are looking for.
What there is difficult for you to understand? I can’t make it much simpler than that and it seems to be more or less well formed vernacular.
If you are trying in a backhanded way to make the point “Humans are machines! The set you mention is empty!” then yes, that is rather close to von Neumann’s point.
Indeed, I can’t think of any plausible meanings for machine, do and tell which would make that quotation non-tautological but true.
And if everyone else was able to see that I guess von Neumann would never have needed to make the statement.!
Sorry. What I meant is that computer programs can’t speak English, or any other natural language. When you get a program that can speak English it will most likely be trivial to make a program that does the translation CronoDAS was talking about.
Ahh, I see. I may have been less confused if you replied to the quote directly.
Natural language processing is certainly one task that has not yet been eliminated as a counter-example.