4.4 Theory of Computation

Question 1

Algorithm (definition)

Answer 1

A set of step by step instructions to solve a specific problem that always terminates and can be represented by a Turing Machine

Question 2

Representational Abstraction (definition)

Answer 2

Removing unnecessary details

Question 3

Decomposition (definition)

Answer 3

Act of breaking down a problem into a number of more manageable sub problems

Question 4

Finite State Machines can be used to test

Answer 4

if a string belongs to a regular language

Question 5

In Mealy Machines

Answer 5

Outputs are associated with transitions

Question 6

A Finite State Machine is described by (5)

Answer 6

• a set of states
• a start state
• a set of final/accepted states
• transition functions
• input alphabet

Question 7

Each Transition Diagram has (3)

Answer 7

• a start state
• a halting/dead/trap state
• transitions

Question 8

Regular Language (definition)

Answer 8

A language (set of strings) that can be expressed as a regular expression or finite state machine

Question 9

A Regular Language is comprised of two components:

Answer 9

• alphabet: finite set of symbols
• syntax rules: how the symbols must be ordered

Question 10

?

Answer 10

0 or 1 occurrence of previous character

Question 11

*

Answer 11

Min 0 occurrences of previous character

Question 12

+

Answer 12

Min 1 occurrences of previous character

Question 13

|

Answer 13

or

Question 14

Set (definition)

Answer 14

An unordered list of elements in which each element occurs at most once

Question 15

Cardinality =
Empty set:

Answer 15

a measure of the number of elements in a set
{} or ∅

Question 16

Infinite Sets are either

Answer 16

• Countable (e.g. rational)
• Non countable (e.g. real, irrational)

Question 17

Subset (definition)

Answer 17

• allowed to be the same as the original set
• proper subset is not

Question 18

Cartesian Product

Answer 18

• Is found by ‘joining’ two sets together
• X = {2,5,3} Y = {7,9}
• X cross Y = {(2,7), (2,9), (5,7), (5,9), (3,7), (3,9)}

Question 19

Backus Naur diagrams

Answer 19

Syntax / railroad diagrams

Question 20

Types of Complexity

Answer 20

• Time complexity is a function that describes how long an algorithm takes in terms of quantity of input
• Memory complexity is a function the describes how much space an algorithm takes in terms of quantity of input
• Often improving one decreases the other

Question 21

Big O Notation Explanations for:
- Bubble Sort
- Binary Search, Binary Tree Search, Merge Sort

Answer 21

• Bubble Sort:
• • In each pass through the list, n items will be examined
• • There will be at most n passes through the list
• • 2 for loops and so O(n2)
• Binary Search, Binary Tree Search, Merge Sort:
• • Each comparison halves the size of the list that has to be searched through
• • if the size of the list doubles then the number of comparisons needed only increases by 1

Question 22

Intractable (Definition)

Answer 22

The problem is computable but cannot be solved within a polynomial (or less) time

Question 23

Travelling Salesman Problem (Process + 3)

Answer 23

• Select a node to start from
• Choose the nearest neighbour to that node
• Continue choosing the nearest neighbour until all the nodes have been visited
• If not all nodes are visited then choose another starting point and start again
• Problem: find a route that visits all nodes with the shortest distance
• Only way to get the best solution is to try all combinations (brute force)
• Is intractable

Question 24

The Halting Problem (Problem + Importance)

Answer 24

• The Halting Problem determines if a program will halt without running the program given its particular inputs
• Provides proof that there are problems that are unsolvable/non computable

Question 25

The output of a Turing Machine is

Answer 25

not written on a separate tape, but rather overwritten on the same tape

Question 26

Each Turing Machine has (6)

Answer 26

• an infinite tape (+ a head which can move to read/write from the tape)
• a finite alphabet of symbols
• a finite number of states (a transition diagram)
• a halting state/accepting states
• the current state
• a set of transition rules

Question 27

The Universal Turing Machine

Answer 27

“The UTM can simulate any other Turing Machine and executes operations on the data precisely as the simulated Turing Machine does”

Question 28

The UTM is considered to be more powerful than any other computer as

Answer 28

it has an infinite amount of memory

Question 29

Constant Time Complexity (definition)

Answer 29

As the size of inputs increases the amount of time taken remains the same

Question 30

Composition

Answer 30

Combining procedures into compound procedures

Question 31

Automation

Answer 31

Models are put into action to solve problems