Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav07_quiz_answers [2007/03/18 16:27] vkuncak |
sav07_quiz_answers [2007/03/18 17:54] vkuncak |
||
|---|---|---|---|
| Line 43: | Line 43: | ||
| * Suggest (in 3-10 sentences) how you would design an algorithm for the following problem... | * Suggest (in 3-10 sentences) how you would design an algorithm for the following problem... | ||
| - | * **Answer**: According to the [[wk>Rice's theorem]], there is no algorithm that solves this solution exactly. We can implement a practically useful "conservative" approximation which has the property that, when it claims that the program always returns zero, then it will indeed return zero, but when it says that the program "need not always return zero", it still might be the case that the program always returns zero but our approximate algorithm was not smart enough to do that. An approximate algorithm might perform interval analysis, which approximates an interval of values to which the variables of the program can belong to. | + | * **Answer**: According to the [[wk>Rice's theorem]], there is no algorithm that solves this solution exactly. We can implement a practically useful "conservative" approximation which has the property that, when it claims that the program always returns zero, then it will indeed return zero, but when it says that the program "need not always return zero", it still might be the case that the program always returns zero but our approximate algorithm was not smart enough to do that. Such approximate algorithm might perform interval analysis, which computes an interval of values to which the variables of the program can belong to. |