= 27d567bc2d48d9f40e9ccc20ea370b15)
loup-vaillant comments on Causal diagrams and software engineering - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (29)
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).