8.7. Summary and References

Try these first

1. 1.

   Define computable function.

   Hint

   Think of it as something you can code.

2. 2.

   Give an example of an uncomputable function.

   Hint

   This often relates to whether a program finishes or keeps looping.

3. 3.

   What defines a computable function?

   • A function without an algorithm
   • A function with a corresponding program
   • Any function irrespective of implementation

   Hint

   Think about what it takes to compute!

4. 4.

   Is the Halting Problem computable?

   • True
   • False

   Hint

   Consider the existence of a program that can solve it!

5. 5.

   Can you describe a scenario in computer science where uncomputable functions might pose a significant challenge?

   Hint

   Consider AI limitations in problem-solving.

6. 6.

   Propose a real-world application where knowing about computability could impact development.

   Hint

   Think about algorithms in the context of security and predictability.