4.4 Theory of computation

Question 1

What is a finite state machine

Answer 1

model which represents states and arrows with conditions showing how to navigate the states

Question 2

notation for finite state machines

Answer 2

arrow pointing at S0 to show start state
double circle indicates a valid stop state

Question 3

What is a set

Answer 3

an abstract data type containing unordered unique values

Question 4

What is notation for a set

Answer 4

F : {1,2,3,4,5}

Question 5

How to express sets in set comprehension e.g set of all positive integers not including zero

Answer 5

e.g F = {x | x ∈ N ^ x ≥ 1}
where F is the name of the set

Question 6

What are empty sets and how are they notated

Answer 6

they contain 0 elements notated by {} or ø

Question 7

how to represent strings in set {01,0011,000111 … } in compact set notation

Answer 7

{0^n 1^n | n ≥ 1}

Question 8

What is a finite set

Answer 8

they contain a finite number of items

Question 9

What is the cardinality of a finite set

Answer 9

refers to the number of elements in the set

Question 10

What is an infinite set

Answer 10

infinite sets contain an infinite number of items

Question 11

What is a countably infinite set

Answer 11

the items in a countably infinite set can be counted off by the natural numbers

Question 12

What is a non-countable set

Answer 12

contain a larger infinity of numbers that can not be paired with natural numbers - this includes the set of real numbers

Question 13

What is the cartesian product of sets

Answer 13

set of pairs from each set such as {(a1,b1),(a2,b2)}

Question 14

What is a subset and its notation

Answer 14

set A is a subset of set B if it only contains items from set B - A ⊆ B

Question 15

What is a proper subset and the notation

Answer 15

set A is a proper subset of set B if it only contains items from set B but not all of them - A ⊂ B

Question 16

What is membership of an element in a set

Answer 16

if an item is in a set then this symbol ∈ denotes it or is the item is not in the set then this symbol ∉ denotes it

Question 17

What is the union of two sets and the symbol

Answer 17

a new set created with the elements in both sets combined - duplicate elements only appear once - symbol is ∪

Question 18

What is the intersection of two sets and the symbol

Answer 18

a new set created from the elements that appear in both sets - symbol is ∩

Question 19

What is the difference of two sets and the symbol and example:
A : {1,2,3,4,5}
B : {2,4,6,8,10}
so what is A\B

Answer 19

a new set created by items that are exclusive to one set - symbol is \ or -
example - A\B = {1,3,5}

Question 20

What is the relationship between regular expressions and FSMs

Answer 20

equivalent ways of defining regular languages

Question 21

How can algorithms be compared

Answer 21

by expressing their complexity as a function relative to the size of the problem - size of the problem is the key issue

Question 22

What are the two ways an algorithm can be complex

Answer 22

time-wise and space-wise

Question 23

What does efficiently implementing automated abstractions mean

Answer 23

designing data models and algorithms to run quickly taking up minimal resources like memory

Question 24

what is automation

Answer 24

requires putting models (abstraction of real world objects) into action to solve problems - achieved by creating algorithms, implementing algorithms in program code, implementing the models in data structures, executing the code

Question 25

what does n! represent

Answer 25

the product of all positive integers less than or equal to n - number of permutations of n distinct objects

Question 26

What is big O notation

Answer 26

it describes the time complexity of an algorithms - it always assumes worst case scenario

Question 27

what is the least to most complex time complexities

Answer 27

constant - O(1), logarithmic - O(log2n), linear - O(n), O(nlogn), polynomial - O(n^2), O(n^3), exponential - O(2^n), factorial - O(n!)

Question 28

what is a tractable problem

Answer 28

a problem that can be solved in a useful period of time - polynomial or less time solution

Question 29

what is an intractable problem

Answer 29

problems that are theoretically solvable but are classified as insoluble due to limits of computations such as speed of today's technology - cannot be solved within a useful period of time

Question 30

what is a heuristic method

Answer 30

for intractable solutions they are approximate solutions to a problem which are not optimal but still more useful than their intractable equivalent

Question 31

what imposes limits to what can be computed

Answer 31

algorithmic complexity and hardware

Question 32

what is the halting problem

Answer 32

unsolvable problem of determining whether any program will eventually stop if given a particular input

Question 33

why is the halting problem significant

Answer 33

it demonstrates that there are some problems that can not be solved by a computer

Question 34

what is a turing machine

Answer 34

a computer with a single fixed program expressed using a finite set of states in a state transition diagram, a finite alphabet of symbols, an infinite tape with marked off squares and a sensing read/write head that can travel along the table one square at a time

Question 35

what is the start state and halting state

Answer 35

start state is the state the Turing machine starts on and halting state is the states that have no outgoing transitions

Question 36

what is the format of a transition function

Answer 36

δ(current state, read) = (new state, write, move)

Question 37

what does □ represent in a tape cell

Answer 37

an empty cell

Question 38

compare finite state machines to turing machines

Answer 38

turing machines are more powerful than finite state machines because they can utilise a greater range of languages than finite state machines and their tape is infinitely long in one direction

Question 39

what three values need to be specified on arrows on a turing machine

Answer 39

current value, new value, direction to move

Question 40

What is a universal turing machine

Answer 40

they are capable of representing any finite state machine - description of finite state machine is to be read off of the same tape as the input data

Question 41

what is the importance of turing machines

Answer 41

turing machines provide a general model of computation and provide a definition of what is computable