8.1. Definition of Computable and Uncomputable Functions

Try these first

1. 1.

   Define a computable function in your own words.

   Hint

   Think about the relationship between functions and programs.

2. 2.

   What is an example of an uncomputable function?

   Hint

   Consider problems that seem not to have a clear solution.

3. 3.

   What defines a computable function?

   • A function with an arbitrary output.
   • A function computable by any computer.
   • A function for which a program exists to compute outputs for all inputs.

   Hint

   Think about the role of programs in defining functions.

4. 4.

   The Halting Problem is an example of which type of function?

   • Computable
   • Uncomputable
   • Both

   Hint

   Recall the definition of uncomputable functions.

5. 5.

   Prove the existence of an uncomputable function using cardinality arguments.

   Hint

   Revisit the definitions of countable and uncountable sets and apply them to the sets of functions and programs.

6. 6.

   Construct a hypothetical example of an uncomputable function and explain why it cannot be computed.

   Hint

   Think about the implications surrounding determining halting conditions for all programs.