Question 1
Learning objective
Computable and non-computable problems: Be aware that some problems cannot be solved algorithmically.
Read the explanation, check the common trap, then practise with flashcards and questions.
At a glance
0
Flashcards
0
Questions
Topic
Classification of algorithms
Subtopic
Computable and non-computable problems
Aqa A Level Computer ScienceTheory of computation
Study support
Understand this objective
Quick explanation
Computable and non-computable problems: Be aware that some problems cannot be solved algorithmically
- This point belongs to Classification of algorithms, especially Computable and non-computable problems.
- You need to be able to computable and non-computable problems: Be aware that some problems cannot be solved algorithmically.
- Use the linked flashcards and practice questions to check recall, then practise applying the idea in an exam-style answer.
Why it matters
This objective helps connect Computable and non-computable problems to exam-style questions, flashcards, and revision notes for Classification of algorithms.
Quick student answer
What is meant by a computable problem?
Direct answer
A problem that can be solved by an algorithm
Key terms
- Computable problem: A problem for which an algorithm exists that can solve it.
- Non-computable problem: A problem that cannot be solved algorithmically in every case.
Common trap
Confusing difficulty with non-computability: Non-computability means that no algorithm can solve the problem in every case. Difficulty or lack of current progress alone does not establish this.
Related questions
Try this as a practice card
Question 1 of 4
Choose an answer, get feedback, then move sideways through the set.
0 of 4 attempted
Flashcard prompts
Flip through the key recall cards
Flashcard 1 of 4
Press Space to flip, arrows to move
Revision tools
Choose how to practise
Flashcards0 linked cards
No objective-specific flashcards are cached for this page. Use the topic hub to revise the surrounding flashcards without triggering a frozen-subject DB fallback.Open topic hub
Practice Questions0 linked questions
No objective-specific practice questions are cached for this page. Use the topic question bank to practise nearby curriculum questions without weakening the egress guard.Open topic questions
Related learning objectives
- Comparing algorithms: Understand that algorithms can be compared by expressing their complexity as a function relative to the size of the problem. Understand that the size of the problem is the key issue. Understand that some algorithms are more efficient: • time-wise than other algorithms • space-wise than other algorithms. Efficiently implementing automated abstractions means designing data models and algorithms to run quickly while taking up the minimal amount of resources such as memory.
Comparing algorithms
- Maths for understanding Big-0 notation: Be familiar with the mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ. 60 Be familiar with the concept of: • a linear function, for example y = 2x • a polynomial function, for example y = 2x 2 • an exponential function, for example y = 2x • a logarithmic function, for example y = log10 x. Be familiar with the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutations of n distinct objects is n factorial (n!). n! is the product of all positive integers less than or equal to n.
Maths for understanding Big-0 notation
- Order of complexity: Be familiar with Big-O notation to express time complexity and be able to apply it to cases where the running time requirements of the algorithm grow in: • constant time • logarithmic time • linear time • polynomial time • exponential time. Be able to derive the time complexity of an algorithm.
Order of complexity
- Limits of computation: Be aware that algorithmic complexity and hardware impose limits on what can be computed.
Limits of computation
- Classification of algorithmic problems: Know that algorithms may be classified as being either: • tractable - problems that have a polynomial (or less) time solution are called tractable problems. • intractable - problems that have no polynomial (or less) time solution are called intractable problems. Heuristic methods are often used when tackling intractable problems.
Classification of algorithmic problems