# A level Computing: Problem Solving Definitions

Flashcards by Zacchaeus Snape, updated more than 1 year ago
 Created by Zacchaeus Snape about 7 years ago
220
3

### Description

Definitions of key terms for the problem solving section of the COMP 3 unit of AQA Computing A Level

## Resource summary

 Question Answer Abstraction representation that is arrived at by removing unnecessary details Principle of universality A universal machine is a machine capable of simulating any other machine Interpreter a program that works its way through a set of instructions, identifying the next instruction then executing it Universal Turing machine A Turing machine that can execute other Turing machines by simulating the behaviour of any Turing machine Power of a Turing machine No physical computing device can be more powerful than a Turing machine. If a turing machine cannot solve a yes/no problem, then the problem is not solvable. Equivalent Turing machine All other types of computing machine are reducible to an equivalent Turing machine Turing machine An FSM that controls one or more tapes where at least one tape is infinitely long Finite state automation An FSM that produces no output while processing the input, but responds yes or no when it has finished processing the input Moore machine An FSM that determines its outputs from the present state only Mealy machine An FSM that determines its outputs from the present state and from the inputs Halting state a state that has no outgoing transition Non-deterministic finite state machine an FSM that may have several possible next states for each pair of state and input symbol Deterministic finite state machine an FSM that has only one next state for each pair of state and input symbols Transition table tabulates the transition mappings transition function maps input symbol and state to the output symbol and state Finite state machine consists of a set or input symbol, and if it produces and output, a set of output symbols, a finite set of states and a transition function that maps a state-symbol pair to a state and possibly generates an output

### Similar

A level Computing Quiz
Biological Definitions
Love through the ages
Social Psychology As level
Biology AQA 3.2.5 Mitosis
Function and Structure of DNA
AQA Biology 8.1 structure of DNA
AS Biology Unit 1
AQA AS Biology Unit 2 DNA and Meiosis
Psychology subject map
AQA Biology 12.1 cellular organisation