| HPS 0628 | Paradox | |
Back to doc list
1a. Computer program 1 computes the squares of numbers by multiplying them directly. What function on the natural numbers can represent its operation?
1b. Computer program 2 computes the square by adding the numbers many times, that is by taking different steps, but gets the same result. Can its operation be represented by the same function? Explain.
2. A function on the natural numbers maps every number to 1. That is f(1)=1, f(2)=2, f(3)=3, ... Is this function computable? If so, what is the behavior of a computer program that it represents?
3. Here is an attempt to solve the halting problem. For a given program with a given input, just simulate step by step what the program does. If it halts report that. If it goes into an infinite loop of repeated states, report that. Why does this solution fail?