AQA A Level · Computer Science 7517

A model of computation: Practice Questions

5 multiple-choice questions marked as you go, and 5 written questions with worked solutions. All on A model of computation.

10 questions27 marksFree, no account

Question 1

1 mark

A Turing machine transition function is represented as:
\(\delta(q_1, 0) = (q_2, 1, R)\)
Which of the following best describes the action of the machine when it is in state \(q_1\) and reads a '0' on the tape?

Question 2

1 mark

A Turing machine transition function is defined as: \(\delta(q_a, 1) = (q_b, 0, L)\). If the tape currently reads ...B 1 1 0 B... and the head is over the second '1' (from the left) in state \(q_a\), what will be the tape content and head position after this single transition?

Question 3

1 mark

A Turing machine is designed to increment a unary number (represented by a string of 1s). The head starts at the leftmost '1'. Which set of rules would effectively move the head to the right end of the string and append a '1' before halting?

Question 4

1 mark

Which of the following is a fundamental component of a Turing machine as defined in the AQA specification?

Question 5

1 mark

Which of the following represents the equivalence between a transition function and a state transition diagram for a Turing machine?

Question 6

4 marks

A Universal Turing Machine (UTM) is a fundamental model in computation. Explain how the UTM embodies the stored program concept.

Write your answer out first, then check it against the worked solution.

Question 7

6 marks

A Turing machine transition function is given as \(\delta: Q \times \Sigma \rightarrow Q \times \Sigma \times \{L, R, S\}\). Explain the significance of the \(Q\) and \(\Sigma\) components in this formal model.

Write your answer out first, then check it against the worked solution.

Question 8

2 marks

A Turing machine is defined to have a finite set of states. According to the specification, if a machine enters a state from which there are no outgoing transitions for the current tape symbol, what specific name is given to this type of state?

Write your answer out first, then check it against the worked solution.

Question 9

4 marks

A Turing machine is defined by the following transition rules, where 'B' represents a blank space and the tape initially contains the string "11" followed by blanks. The machine starts in state \(S_0\) at the first '1'.

Rule 1: \((S_0, 1) → (S_0, 1, R)\)
Rule 2: \((S_0, B) → (S_1, 0, L)\)
Rule 3: \((S_1, 1) → (S_1, 1, L)\)
Rule 4: \((S_1, B) → (H_a, B, R)\)

Describe the final contents of the tape and the final position of the read-write head when the machine reaches the halting state \(H_a\).

Write your answer out first, then check it against the worked solution.

Question 10

6 marks

In the context of A model of computation, the Halting Problem is a significant theoretical limit.

(a) Define what the Halting Problem is.
(b) Explain why the Halting Problem is described as undecidable.
(c) Describe the significance of the Halting Problem for the limits of what a computer can compute.

Write your answer out first, then check it against the worked solution.

* The content provided by thinka is generated by AI and may not always be accurate or up-to-date. Please use it as a supplementary resource and verify with official materials.

You've seen the model answer. Now get yours marked.

This page can show you how a good answer looks. It cannot tell you what your answer was missing. thinka marks your written work against the real mark scheme in about 15 seconds.

Get My Answers Marked Back to the notes

Want more questions like these? Get a fresh set on this topic, marked as you go.