AQA A Level Computer Science (7517)

4.4: Theory of Computation: revision quiz and key terms

Free practice for 4.4: Theory of Computation in AQA A Level Computer Science (7517). It has 24 parts, listed below. Try the questions, then check the key terms.

Try 5 free questions

No sign-in needed. Tap an answer to check it.

Question 1 · Multiple choice

What does 'assignment' refer to as a standard construct?

Question 2 · True or false?

A non-computable problem cannot be solved by any algorithm at all.

Question 3 · Multiple choice

Which of these whole strings is matched by the regular expression a(b|c)*?

Question 4 · True or false?

A finite state machine whose output is determined by its transitions, rather than its states, is called a Moore machine.

Question 5 · Multiple choice

What is the time complexity of solving the Travelling Salesman Problem by checking every possible route?

In RADevo, this topic has fill-in-the-blank, matching, multiple-choice and true or false activities, and every question you get wrong comes back in Revise today until you've learnt it.

Key terms for 4.4: Theory of Computation

Algorithm: A sequence of steps that can be followed to complete a task and that always terminates.
Finite state machine: A model of computation with a fixed number of states and transitions between them triggered by inputs.
Halting problem: The unsolvable problem of deciding, for any program and input, whether the program will eventually stop.
Information hiding: Hiding the details of an object that do not contribute to its essential characteristics.
Intractable problem: A problem that can be solved in theory but has no polynomial-time solution.
Limits of computation: Restrictions on what can be practically or theoretically computed.
Regular expression: A notation for describing a set of strings using a pattern.
Turing machine: A theoretical model of computation with a finite set of states, a read/write head and an infinite tape.

What 4.4: Theory of Computation covers

In RADevo this topic has a full topic test and a focused quiz for each part:

4.4.1.1 Problem-Solving
4.4.1.2 Following and Writing Algorithms
4.4.1.3 Abstraction
4.4.1.4 Information Hiding
4.4.1.5 Procedural Abstraction
4.4.1.6 Functional Abstraction
4.4.1.7 Data Abstraction
4.4.1.8 Problem Abstraction/Reduction
4.4.1.9 Decomposition
4.4.1.10 Composition
4.4.1.11 Automation
4.4.2.1 Finite State Machines with and without Output
4.4.2.2 Maths for Regular Expressions
4.4.2.3 Regular Expressions
4.4.2.4 Regular Language
4.4.3.1 Backus-Naur Form (BNF)/Syntax Diagrams
4.4.4.1 Comparing Algorithms
4.4.4.2 Maths for Understanding Big-O Notation
4.4.4.3 Order of Complexity
4.4.4.4 Limits of Computation
4.4.4.5 Classification of Algorithmic Problems
4.4.4.6 Computable and Non-Computable Problems
4.4.4.7 Halting Problem
4.4.5.1 Turing Machine

Teaching AQA A Level Computer Science (7517)?

Set this topic as homework in two clicks, see who has done it and which questions your class got wrong, and start every lesson with a Do Now built from their mistakes.

Start a free 2-week trial

Revising for this?

If your school uses RADevo, sign in to do the full quizzes and keep your progress. If it doesn't, show this page to your Computing teacher.