Differences

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

--- sav07_quiz_answers [2007/03/18 16:21]
vkuncak
+++ sav07_quiz_answers [2007/03/18 16:23]
vkuncak
@@ Line 35: / Line 35: @@
   * 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?
-  * **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...