Differences

This shows you the differences between two versions of the page.

--- sav07_quiz_answers [2007/03/18 16:10]
vkuncak created
+++ sav07_quiz_answers [2007/03/18 16:18]
vkuncak
@@ Line 1: / Line 1: @@
-  * Is the following statement valid when x is a real number and f is a function
+  * Is the following statement valid when x is a real number and f is a function from reals to reals, and why:
-    from reals to reals, and why:
     "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(
-  * Is the following statement valid (for arbitrary properties
+  * Is the following statement valid (for arbitrary properties P and Q), and why:
-    P and Q), and why:
      "If for all x, both P(x) and Q(x), then both
@@ Line 13: / Line 11: @@
 ) for all x, Q(x)."
-   * **Answer**: Valid.
+  * **Answer**: Valid.
-  * Is the following statement valid (for arbitrary properties
+  * Is the following statement valid (for arbitrary properties P and Q), and why:
-    P and Q), and why:
     "If for all x, P(x) or Q(x) hold, then at least
@@ Line 36: / Line 33: @@
   * **Answer**: x is divisible by 7.
-* Consider a simple programming language ...
+  * Consider a simple programming language ...
-  - Say in 3-5 sentences how you would build an
+  * Say in 3-5 sentences how you would build an
     interpreter for this language:
-   **Answer**: Parser the program into abstract syntax tree.
+  * **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.
-   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
+  * What is the class of functions from integers to integers that can be described in this programming language?
-    that can be described in this programming language?
-   **Answer**: All computable functions on integers can be computed.
+  * **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.
-   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.
-* Suggest (in 3-10 sentences) how you would design an
+  * Suggest (in 3-10 sentences) how you would design an
-  algorithm for the following problem:
+    algorithm for the following problem...
-    The input of the algorithm is a description of a
+  * **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.
-    function that accepts two integers and produces an
-    integer as a result.  An example of such function,
-    is the function f:
-       x = input();
-       y = input();
-       result = 0;
-       while (y > 0) {
-         result = result + x;
-         y = y - 1;
-       }
-       output(y);
-    Your algorithm should accept any other such function
-    that can be written in our simple programming language.
-    The output of your the algorithm should be "true" if 0
-    is the only value that the function can return, and
-    "false" otherwise.
-  What would your algorithm return on the above example?
-============== End of quiz  ==============================