8.4. Non-constructive Proofs

Try these first

1. 1.

   Define a computable function.

   Hint

   Think about whether you can write a program for it.

2. 2.

   What does it mean if a function is uncomputable?

   Hint

   Consider the implications of a program not existing for that function.

3. 3.

   What defines a computable function?

   • A function with no program
   • A function computable by a program
   • A function that always produces an output

   Hint

   Consider if you can find a program for it.

4. 4.

   True or False: All functions are computable.

   • True
   • False

   Hint

   Think of examples like the Halting Problem.

5. 5.

   Using Cantor's argument, prove that the set of all functions from {1,2,3,...} to {0,1} is uncountable.

   Hint

   Reflect on how listing elements could lead to missing at least one function.

6. 6.

   Discuss the implications of the Halting Problem within programming and computation limits.

   Hint

   Consider programming tasks where it's impossible to predict behavior.