A model of computation

Question 1

Pseudocode

Answer 1

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.

Question 2

Abstraction

Answer 2

is the process of omitting unnecessary details from a problem.

Question 3

Representational Abstraction

Answer 3

A representation of a problem arrived at by removing unnecessary details from the problem

Question 4

Abstraction by Generalisation/Categorisation

Answer 4

A grouping by common characteristics to arrive at a hierarchal relationship of the ‘is a kind of’ type

Question 5

Information Hiding

Answer 5

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

Question 6

Procedural Abstraction

Answer 6

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

Question 7

Functional Abstraction

Answer 7

disregards the particular method of a procedure and results in just a function

Question 8

Data Abstraction

Answer 8

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

Question 9

Decomposition

Answer 9

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

Question 10

Composition

Answer 10

also known as bottom-up programming

Question 11

Automation

Answer 11

is the process of putting abstractions of real world phenomena (which are referred to as models) into action to solve problem

Question 12

Problem Abstraction(sometimes known as reduction)

Answer 12

where details are removed from a problem until it is represented in a way that is solvable

Question 13

Finite State Machines (double circle)

Answer 13

Indicates a circle is a valid stop state

Question 14

Finite State Machines (circle)

Answer 14

Represents a state

Question 15

Finite State Machines (arrow)

Answer 15

indicates how to move between states, if it loops back it means the state does not change with the input

Question 16

Finite State Machines (Inputs/outputs)

Answer 16

Often labelled on the arrows, separated by a pipe, left is input and right is output

e.g.
1|a

Question 17

Regular Expressions

Answer 17

shorthand way of describing sets

Question 18

List all Metacharacters (5 need to know)

Answer 18

-* is 0 or more repetitions
+ is 1 or more repetitions
? previous character optional
() used to group regular expressions

• | is Alternative/Or

Question 19

Context Free Languages

Answer 19

is a set of strings and symbols that follow the rules of a context-free grammar

Question 20

Context free grammars

Answer 20

describe which strings are and are not possible in a language by laying out production rules

Question 21

A production rule

Answer 21

is as simple as replacing one character for another E.G., dictionary based compression

Question 22

Backus Naur Form

Answer 22

a way of notating context free languages, it uses statements in which the left hand side is defined by the right

Question 23

non-terminal

Answer 23

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>

Question 24

terminal (BNF)

Answer 24

BNF Text without brackets is called a terminal they cannot be broken down any further and must be taken as the written value

Question 25

Backus Naur Form (example)

Answer 25

<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>

Question 26

Backus Naur and Recursion

Answer 26

Backus Naur can use recursion to form more complex definitions, a non terminal can be defined in terms of itself, allowing iteration

Question 27

Why can regular expressions not represent Backus Naur?

Answer 27

they cannot support recursion

Question 28

Syntax Diagrams

Answer 28

A visual representation of a regular language, they use rectangles to represent non terminals and ellipses to represent terminals

Question 29

What do Turing Machines consist of

Answer 29

• 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

Question 30

Turing Machines: Operation

Answer 30

1. The tape ^ is divided into cells, each of which can be left blank or constrain a symbol.
2. Symbols are written to and removed from cells on the tape by the Turing machine’s read/write head.
3. 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

Question 31

Turing Machines or FSM?

Answer 31

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

Question 32

transition functions

Answer 32

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))

Question 33

Universal Turing Machine

Answer 33

Universal Turing Machines are capable of representing any finite state machine.

Question 34

Universal Turing Machine: Operations

Answer 34

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

Question 35

standard description (UTM)

Answer 35

describes the standard Turing Machine

Question 36

data (UTM)

Answer 36

is the data that the operations will be executed upon by the UTM exactly as M would have intended

Question 37

why is a Universal Turing Machine Important?

Answer 37

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