A level Computing: Problem Solving Definitions

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


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
Show full summary Hide full summary


A level Computing Quiz
Zacchaeus Snape
Biological Definitions
Love through the ages
Social Psychology As level
Gurdev Manchanda
Biology AQA 3.2.5 Mitosis
Function and Structure of DNA
Elena Cade
AQA Biology 8.1 structure of DNA
Charlotte Hewson
AS Biology Unit 1
AQA AS Biology Unit 2 DNA and Meiosis
Psychology subject map
Jake Pickup
AQA Biology 12.1 cellular organisation
Charlotte Hewson