Practice Uncomputable Functions (8) - Uncomputable Functions - Discrete Mathematics - Vol 2

Practice: Uncomputable Functions

Lesson 8Uncomputable Functions

Practise this section

9 questions

Flashcard drill
4 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.
Show hintHide hint
Think about whether a program can calculate the output for every input.
Question 2.
What is an uncomputable function?
Show hintHide hint
Consider what might prevent a program from being able to find an answer.
3Question 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
Show hintHide hint
Focus on what it means to have a program for every input.
4Question 4.
True or False: Uncomputable functions can be calculated with limitless resources.
- True
- False
Show hintHide hint
Think about the limits of computational power.
Question 5.
Select an uncomputable function and explain why it cannot be computed. Use references to countability.
Show hintHide hint
Focus on the interactions of infinite sets and the limits of computation.
Question 6.
Devise a non-constructive proof that establishes the existence of an uncomputable function using Cantor's diagonalization.
Show hintHide hint
Utilize Cantor’s argument to clarify the discrepancy in function and program count.

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