Answer Happy

Problem 3: Calculating the Limits of Calculation (25 Points) Computers can do a lot! But they can't do everything. 1) Argue that there are at most countably infinite computer programs. Think about the problem of computing real numbers as the output of a program. A computer might calculate 1/3 for instance, by printing 0.3, then go into an infinite loop repeating 3, forever. More complicated programs could calculate more complex things, like the square root of 2, or for instance. 2) Argue that there are real numbers that cannot be calculated by any computer program. (Hint: Think about pairing every program with its real number output.) 3) Does it matter if you used a different language? Multiple languages? More powerful computers? Why or why not? 4) Conclude that there are fundamental limits to what can be computed by any computer.