8. Uncomputable Functions

Try these first

1. 1.

   Define a computable function.

   Hint

   Think about whether a program can calculate the output for every input.

2. 2.

   What is an uncomputable function?

   Hint

   Consider what might prevent a program from being able to find an answer.

3. 3.

   What defines a computable function?

   • A function computable in polynomial time
   • A function with a corresponding program
   • Any function created in a programming language

   Hint

   Focus on what it means to have a program for every input.

4. 4.

   True or False: Uncomputable functions can be calculated with limitless resources.

   • True
   • False

   Hint

   Think about the limits of computational power.

5. 5.

   Select an uncomputable function and explain why it cannot be computed. Use references to countability.

   Hint

   Focus on the interactions of infinite sets and the limits of computation.

6. 6.

   Devise a non-constructive proof that establishes the existence of an uncomputable function using Cantor's diagonalization.

   Hint

   Utilize Cantor’s argument to clarify the discrepancy in function and program count.