A model of computation Flashcards
Pseudocode
a way of describing instructions that is independent of any programming language. It allows different programmers who may not all understand the same languages, to be able to communicate algorithms to one another.
Abstraction
is the process of omitting unnecessary details from a problem.
Representational Abstraction
A representation of a problem arrived at by removing unnecessary details from the problem
Abstraction by Generalisation/Categorisation
A grouping by common characteristics to arrive at a hierarchal relationship of the ‘is a kind of’ type
Information Hiding
defined as the process of hiding all details of an object that do not contribute to its essential characteristics e.g. seeing what cars can fit into a ferry, colour is irrelevant
Procedural Abstraction
involves breaking down a complex model into a series of reusable procedures e.g. for example, to calculate the area of a rectangle you could Calculate Area = width * height
Functional Abstraction
disregards the particular method of a procedure and results in just a function
Data Abstraction
where specific details of how data is represented is abstracted away, allowing new kinds of data structures to be created from previously defined data structures - this forms the basic types of abstract data types
Decomposition
breaking a problem down into a series of smaller subproblems, these can be solved individually or broken down further and solved until all parts of the original problems have been solved. – top down approach
Composition
also known as bottom-up programming
Automation
is the process of putting abstractions of real world phenomena (which are referred to as models) into action to solve problem
Problem Abstraction(sometimes known as reduction)
where details are removed from a problem until it is represented in a way that is solvable
Finite State Machines (double circle)
Indicates a circle is a valid stop state
Finite State Machines (circle)
Represents a state
Finite State Machines (arrow)
indicates how to move between states, if it loops back it means the state does not change with the input
Finite State Machines (Inputs/outputs)
Often labelled on the arrows, separated by a pipe, left is input and right is output
e.g.
1|a
Regular Expressions
shorthand way of describing sets
List all Metacharacters (5 need to know)
-* is 0 or more repetitions
+ is 1 or more repetitions
? previous character optional
() used to group regular expressions
- | is Alternative/Or
Context Free Languages
is a set of strings and symbols that follow the rules of a context-free grammar
Context free grammars
describe which strings are and are not possible in a language by laying out production rules
A production rule
is as simple as replacing one character for another E.G., dictionary based compression
Backus Naur Form
a way of notating context free languages, it uses statements in which the left hand side is defined by the right
non-terminal
Text which is placed inside of angle brackets represents a <non-terminal> , it can be broken down into further non-terminals, terminals or a combination</non-terminal>
terminal (BNF)
BNF Text without brackets is called a terminal they cannot be broken down any further and must be taken as the written value
Backus Naur Form (example)
<address> ::= <Number><Street>
<Number> ::= 1 | 2 | 3 | 4 | 5
- Number is a non-terminal, which is defined from 5 terminals from 1 to 5. The pipe represents the OR operator
</Number></Street></Number></address>
Backus Naur and Recursion
Backus Naur can use recursion to form more complex definitions, a non terminal can be defined in terms of itself, allowing iteration
Why can regular expressions not represent Backus Naur?
they cannot support recursion
Syntax Diagrams
A visual representation of a regular language, they use rectangles to represent non terminals and ellipses to represent terminals
What do Turing Machines consist of
- A finite state machine
- A set of transition rules
- A (sensing) read/write head
- Start state
- (Set of) accepting/halting states
- A tape that is infinitely long in one direction
- Stat register/current state
- The finite alphabet of symbols that it can use
Turing Machines: Operation
- The tape ^ is divided into cells, each of which can be left blank or constrain a symbol.
- Symbols are written to and removed from cells on the tape by the Turing machine’s read/write head.
- The set of symbols a turing machine uses is called its alphabet and must be finite
- A Turing Machine can be viewed as a computer which runs a single programme, as defined by a FSM
- The FSM will have a start state and may have a number of states from which there are no transitions, referred to as halting states
Turing Machines or FSM?
As a model of computation, Turing machines are more powerful than FSMs because they can utilise a greater range of languages and their tape is infinitely long in one direction
transition functions
The rules a Turing machine follows can be laid out using transition functions
E.G. (Current state, read) = (New state, write, move(left or right))
Universal Turing Machine
Universal Turing Machines are capable of representing any finite state machine.
Universal Turing Machine: Operations
A description of the finite state machine to be used is read off of the same tape as the input data and is then used to process.
Act as interpreters because of the way they read their instructions in a sequence before executing operations on their input data
standard description (UTM)
describes the standard Turing Machine
data (UTM)
is the data that the operations will be executed upon by the UTM exactly as M would have intended
why is a Universal Turing Machine Important?
A UTM is important because anything which a Turing Machine can compute, a real world computer can also compute, providing us with a definition of what is computable, and what cannot be solved by computers
