CS 5315 Homework #9

Date Assigned: Tuesday, February 15, 2005

Due Date: Thursday, February 17, 2005

1. Describe, in detail, the proof that zero-checker does not exist.

2. Prove that a cube-checked does not exist. Reminder: a cube-checker is a program, that, given a program p, checks whether for every input n, p(n) always returns n^3.