AQA A-Level Computer Science 4.4 Theory of computation overview quiz quiz

Making a problem deliberately vaguer and less precise so it is harder to pin down

Breaking a problem down into a set of smaller, more manageable sub-problems

Removing unnecessary detail to focus on the essential features

Running a finished algorithm directly on the physical hardware

The one with output always has more states than the one without any output at all

The one without any output is not even permitted to have a start state, unlike the one with output

There is no real difference between the two; they are just two names for the same machine

The one with output produces output on each transition; the one without only accepts or rejects

(0|1|2|3|4|5|6|7|8|9)+

(0|1|2|3|4|5|6|7|8|9)*

(0-9)?

0123456789

Regular expressions are simply far too slow to match brackets within a reasonable time

A finite state machine has only finitely many states and cannot count without limit

Brackets are not counted as valid characters that a regular expression is able to match

Regular expressions are unable to use the alternation operator to choose between options

It simply has a much larger number of internal states to work with

It runs considerably faster than an ordinary finite state machine

It has an infinite read/write tape giving unlimited memory

It uses regular expressions to describe the inputs that it accepts

Solve absolutely any computational problem instantly, in no time at all

Run only one single fixed program that is permanently built into it

Decide the halting problem for every possible program and input

Simulate any other Turing machine given its description and input

A non-computable problem

A tractable problem that is solvable in polynomial time

An intractable problem that is solvable but only very slowly

A regular language that a finite state machine can recognise

A tractable problem has no solution at all, whereas an intractable problem does in fact have a solution that can be found

A tractable problem has a polynomial-time algorithm; an intractable one has no known polynomial-time algorithm

They are the same thing, just described using two different technical words

A tractable problem is one that is fundamentally non-computable by any machine

They are always guaranteed to return the single optimal solution every single time they are run

They turn the problem into a non-computable one that no algorithm can ever solve

They find a good-enough solution quickly instead of an exact one that would take too long

They reduce the problem down to an equivalent regular language for matching

Using only terminal symbols throughout the whole grammar

Removing the start symbol from the definition of the grammar

Using the star operator, exactly as a regular expression does

A non-terminal that refers to itself (recursion)

NP

P

Neither

Both are about verification only