This is an old revision of the document!
- Is the following statement valid when x is a real number and f is a function
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(
- Is the following statement valid (for arbitrary properties
P and Q), and why:
"If for all x, both P(x) and Q(x), then both
1) for all x, P(x), and
2) for all x, Q(x)."
- Answer: Valid.
- Is the following statement valid (for arbitrary properties
P and Q), and why:
"If for all x, P(x) or Q(x) hold, then at least
one of the following two is true
1) for all x, P(x), or
2) for all x, Q(x)."
- Answer: Invalid.
- Let x,y,z be integer variables that satisfy both of these
two conditions:
x + y = 3z x - 2y = z
What is the strongest property that you can state about the integer x that does not mention the variables y or z?
- Answer: x is divisible by 7.
* Consider a simple programming 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. - 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 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
algorithm for the following problem:
The input of the algorithm is a description of a
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?