A model of computation | AQA Computer Science 7517

Choose a revision tool

Start revising A model of computation

Quick active recall practice

Quick multiple-choice practice

Mixed practice and exam-style prompts

Syllabus checklist

0 objective pages available

Turing machine1 objectives

Turing machine: Be familiar with the structure and use of Turing machines that perform simple computations. 62 Know that a Turing machine can be viewed as a computer with a single fixed program, expressed using: • a finite set of states in a state transition diagram • a finite alphabet of symbols • an infinite tape with marked-off squares • a sensing read-write head that can travel along the tape, one square at a time. One of the states is called a start state and states that have no outgoing transitions are called halting states. Exam questions will only be asked about Turing machines that have one tape that is infinite in one direction. Understand the equivalence between a transition function and a state transition diagram. Be able to: • represent transition rules using a transition function • represent transition rules using a state transition diagram • hand-trace simple Turing machines. Be able to explain the importance of Turing machines and the Universal Turing machine to the subject of computation. Turing machines provide a (general/formal) model of computation and provide a definition of what is computable.

Transition functionComputable

Trace one transition at a time: For every step, record the current state, head position, symbol read, symbol written, movement and new state.

Confusing the symbol read with the symbol written: Read the rule in order: identify the current state and symbol read, then apply the new state, write the specified symbol and move in the specified direction.

Choose a learning objective

Objectives are grouped by subtopic so students can jump straight to the exact skill they want to revise.