Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Next revision Both sides next revision | ||
|
sav07_quiz_answers [2007/03/18 16:21] vkuncak |
sav07_quiz_answers [2007/03/18 17:54] vkuncak |
||
|---|---|---|---|
| Line 3: | Line 3: | ||
| "If (f(x))^2 = 4, then f(x)=2" | "If (f(x))^2 = 4, then f(x)=2" | ||
| - | * **Answer**: Not valid. Let x be an arbitrary element. Take as t interpretation a function f and such that f( | + | * **Answer**: Not valid. Let x be an arbitrary element. Take as t interpretation a function f and such that f(x)=-2. |
| * Is the following statement valid (for arbitrary properties P and Q), and why: | * Is the following statement valid (for arbitrary properties P and Q), and why: | ||
| Line 35: | Line 35: | ||
| * Say in 3-5 sentences how you would build an interpreter for this language: | * Say in 3-5 sentences how you would build an interpreter for this language: | ||
| - | * **Answer**: Parser the program into abstract syntax tree. Represent program state as a mapping from variable names to their value. Traverse the abstract syntax tree and change the values of variables according to the meaning of statements. | + | * **Answer**: Parse the program into abstract syntax tree. Represent program state as a mapping from variable names to their value. Traverse the abstract syntax tree and change the values of variables according to the meaning of statements. |
| * What is the class of functions from integers to integers that can be described in this programming language? | * What is the class of functions from integers to integers that can be described in this programming language? | ||
| - | * **Answer**: All computable functions on integers can be computed. To prove this formally, we could write a simulator for a [[wk>Turing machine]], which is often used as a formal model for computable functions. We can represent the tape as an unbounded integer, whose bits represent Turing machine tapes. We can write code with loops that extracts the n-th bit of the number. | + | * **Answer**: All computable functions on integers can be described. To prove this formally, we could write a simulator for a [[wk>Turing machine]], which is often used as a formal model for computable functions. We can represent the tape as an unbounded integer, whose bits represent Turing machine tapes. We can write code with loops that extracts the n-th bit of the number to access the given cells in a Turing machine, and write transition functions of a Turing machine as constructs in our language. |
| * 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. | + | * **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. |