Practice Definition Of Computable And Uncomputable Functions (8.1) - Uncomputable Functions

Practice: Definition of Computable and Uncomputable Functions

Lesson 8.1Uncomputable Functions

Practise this section

9 questions

Flashcard drill
3 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
3 questions · about 2 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
Define a computable function in your own words.
Show hintHide hint
Think about the relationship between functions and programs.
Question 2.
What is an example of an uncomputable function?
Show hintHide hint
Consider problems that seem not to have a clear solution.
3Question 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.
Show hintHide hint
Think about the role of programs in defining functions.
4Question 4.
The Halting Problem is an example of which type of function?
- Computable
- Uncomputable
- Both
Show hintHide hint
Recall the definition of uncomputable functions.
Question 5.
Prove the existence of an uncomputable function using cardinality arguments.
Show hintHide hint
Revisit the definitions of countable and uncountable sets and apply them to the sets of functions and programs.
Question 6.
Construct a hypothetical example of an uncomputable function and explain why it cannot be computed.
Show hintHide hint
Think about the implications surrounding determining halting conditions for all programs.

5 more questions in this section. Enroll free to practise them all.