1.4 Theory of computation

Question 1

Define automation

Answer 1

Creating a computer model of a real-life situation and putting it into action

Question 2

Define representational abstraction

Answer 2

The process of removing unnecessary details so that only information that is required to solve the problem remains

Question 3

Define abstraction by generalisation / categorisation

Answer 3

The concept of reducing problems by putting similar aspects of a problem into hierarchical catgegories

Question 4

Define top-down design

Answer 4

Starts with the main system at the top and breaks it down into smaller units

Question 5

Define functional abstraction

Answer 5

Breaking down a complex problem into a series of reusable functions

Question 6

Define data abstraction

Answer 6

Hiding how data is represented so that it is easier to build a new kind of data object, for example building a stack from an array

Question 7

Define problem abstraction

Answer 7

Removing unnecessary details in a problem until the underlying problem is identified to see if this is the same as a problem that has already been solved

Question 8

Define information hiding

Answer 8

The process of hiding all details of an object that do not contribute to its essential characteristics

Question 9

Define finite state machine

Answer 9

Any device that stores its current status and whose status can change as the result of an input. Mainly used as a conceptual model for designing and describing systems. There are a finite number of transitions that may take place

Question 10

What is a state transition diagram?

Answer 10

A visual representation of an FSM using circles and arrows

Question 11

Define accepting state

Answer 11

The state that identifies whether an output has been accepted

Question 12

Define state transition table

Answer 12

A tabular representation of an FSM showing inputs, current state, and next state

Question 13

Define Mealy machine

Answer 13

A type of finite state machine with outputs

Question 14

What is a Turing machine?

Answer 14

A theoretical model of computation

Question 15

What is the alphabet of a Turing machine?

Answer 15

The acceptable symbols (characters, numbers) for a given Turing machine

Question 16

Define read/write head

Answer 16

The theoretical device that writes or reads from the current cell of tape in a Turing machine

Question 17

Define halting state

Answer 17

The state that stops a Turing machine

Question 18

Define start state

Answer 18

The initial state of a Turing machine

Question 19

Define transition function/rule

Answer 19

A method of notating how a Turing machine moves from one state to another and how the data on the tape changes

Question 20

Define state transition diagram

Answer 20

A visual representation of the transition function of a Turing machine

Question 21

How does a Turing machine operate?

Answer 21

• Tape divided into an infinite number of cells which are used as memory
• Each cell will contain a symbol, either a character or number, the range of acceptable symbols is the alphabet
• The read/write head can either read what is in the cell, write to the cell, or erase its contents
• The tape can move left or right one cell at a time so every cell is accessible by a read/write head
• The machine can halt at any point if it enters the halting state or if the whole input has been processed

Question 22

What is needed to represent programs with a Turing machine?

Answer 22

• A start state
• A halting state
• An alphabet
• Movement
• A transition function

Question 23

Define instruction table

Answer 23

A method of describing a Turing machine in tabular form

Question 24

Define universal machine

Answer 24

A machine that can simulate a Turing machine by reading a description of the machine along with the input of its own tape

Question 25

Define a regular language

Answer 25

Any language that can be described using regular expressions

Question 26

Define a regular expression

Answer 26

Notation that contains strings of characters that can be matched to the content of a set

Question 27

What symbol represents or in regex?

Answer 27

|

Question 28

What symbol represents zero or more of a character?

Answer 28

*

Question 29

What symbol represents one or more of a character?

Answer 29

+

Question 30

What symbol represents zero or one of a character?

Answer 30

?

Question 31

What symbol represents a wildcard character?

Answer 31

.

Question 32

Define a context-free language

Answer 32

An unambiguous way of describing the syntax of a language useful when a language is context

Question 33

Define Backus-Naur Form (BNF)

Answer 33

A form of notation for describing the syntax used by a programming language

Question 34

Define terminal in BNF

Answer 34

The final element that requires no further rules

Question 35

Define syntax diagram

Answer 35

A method of visualising rules written in BNF or any other context-free language

Question 36

Define set comprehension

Answer 36

The process of creating sets by describing them using notation rather than listing the elements

Question 37

Define finite set

Answer 37

A set where the elements can be counted using natural numbers up to a particular number, an infinite set is the opposite of this

Question 38

Define cardinality

Answer 38

The number of elements in a set

Question 39

Define countable set

Answer 39

A finite set where the elements can be counted using natural numbers

Question 40

Define countably infinite sets

Answer 40

Sets where the elements can be put into a one-to-one correspondence with the set of natural numbers

Question 41

Define cartesian product

Answer 41

Combining the elements of two or more sets to create a set of ordered pairs

Question 42

Define union

Answer 42

Where two sets are joined and all of the elements of both sets are included in the joined set

Question 43

Define intersection

Answer 43

Describes which elements are common to both sets when two sets are joined

Question 44

Define difference

Answer 44

Describes which elements differ when two sets are joined together

Question 45

Define subset

Answer 45

A set where the elements of one are entirely contained within the other; can include two sets that are exactly the same

Question 46

Define proper subset

Answer 46

Where one set is wholly contained within another and the other set has additional elements

Question 47

Define space complexity

Answer 47

The concept of how much space an algorithm requires

Question 48

Define input size

Answer 48

In Big O notation this is the size of whatever data you are asking an algorithm to work with

Question 49

Define time complexity

Answer 49

The concept of how much time an alogrithm requires

Question 50

Define constant time

Answer 50

In Big O notation where the time taken to run an algorithm does not vary with the input size

Question 51

Define linear time

Answer 51

In Big O notation where the time taken to run an algorithm increases in direct proportion with the input size

Question 52

Define exponential time

Answer 52

In Big O notation where the time taken to run an algorithm increases as an exponential function of the number of inputs

Question 53

Define logarithmic time

Answer 53

In Big O notation where the time taken to run an algorithm increases or decreases in line with a logarithm

Question 54

Define polynomial time

Answer 54

In Big O notation where the time taken to run an algorithm is a polynomial function of the input size

Question 55

What is Big O notation?

Answer 55

Big O notation is a way of describing the time spcae complexity of an algorithm, looking at the maximum time it could take an algorithm to complete

Question 56

Define tractable problem

Answer 56

A problem that can be solved in an acceptable amount of time

Question 57

Define intractable problem

Answer 57

A problem that cannot be solved within an acceptable time frame

Question 58

Define heuristic

Answer 58

With algorithms, it is a method for producing an acceptable but not necessarily best solution to an intractable problem

Question 59

Define unsolvable problem

Answer 59

A problem that has been proven that it cannot be solved computationally

Question 60

What is the halting problem?

Answer 60

An example of an unsolvable problem where it is impssible to write a program that can work out whether another problem will halt given a particular input