S04- Theory of Computation

Finite set

A set whose elements can be counted off by natural numbers up to a particular number

Infinite set

A set which has no end value

Cardinality

The number of elements in a finite set

Cartesian product

Set of all ordered pairs (a,b) where a is a member of set A and b is a member of set B

Proper subset

If A is a subset of, but not equal to B

Set

An unordered collection of values or symbols in which each value or symbol occurs at most once

Countable

A set which can be counted off against a subset of natural numbers

Countably infinite set

A set where you can count the elements off against the set of natural numbers

Subset

If every member of A is also a member of set B

Regular language

Language that can be expressed with a regular expression

Turing machine

A theoretical concept that can carry out any computer algorithm no matter how complex

Behaviour of a turing machine and why

Behaves like an interpreter, it reads one instruction at a time, executes these instructions, instructions are stored on the tape

Characteristics of a Turing machine

Has a finite set of states in a state transition diagram. A finite alphabet of symbols. An infinite tape with marked-off squared. A sensing read-write head that can travel along the tape, one square at a time.

Halting state

State with no outgoing transitions, causes the program to stop

States that a Turing machine must have

Start state, halting state (causes it to halt for some inputs)

Contorller

A Finite State Machine which tells the machine what to do next. Read, Erase/Write, Move

Transition function

delta(current state, input symbol)=(next state, output symbol, head move)

Universal Turing Machine

Turing Machine that can execute/simulate the behaviour of any other Turing machine, can compute any computable sequence.

How does a Universal Turing Machine work

Faithfully executes operations on the data precisely as the simulated Turing Machine does. Instructions of TM and its inputs are stored on the UTM’s tape

What did the invention of UTM lead to

Idea of the stored program computer

Context-free grammar

Set of recursive rules used to generate patterns; it is used to describe context free languages. They include regular languages but not vice-versa

Disadvantages of regular expressions

Regex can be used to describe simple “languages” and to match patterns in text, but it is time-consuming to define a valid identifier using regex

Why do we need BNF

• An instruction for a computer must not be ambiguous in any way

• A programming language requires strict and precise rules

• BNF can be used by compiler writers to represent the precise syntax of a programming language instructions

Size of a problem

Could be the magnitude of the input (if a number) or the size of input list

Execution time vs problem size

Always a trade-off, can’t have both

Time complexity

How fast an algorithm runs

Space complexity

How much memory its variables need

Time-efficient problem

If its execution ends in max polynomial time

Constant complextiy

O(n), the best time complexity

Logarithmic complexity

O(logn)

Linear complexity

O(n)

Polynomial complexity

O(n²)

Exponential complexity

O(n!), the worst time complexity

Bubble sort time complexity

O(n²)

Merge sort time complexity

O(nlogn)

Computable problem

If there is an algorithm that can solve every instance of it in a finite number of steps

Halting problem

Determining if, for a given input, a program will finish running or continue forever

Tracetable problems

Problems that have a polynomial-time solution (or better)

Intractable problems

Problems that have no polynomial (or less) time solution

Heuristic solutions

Large number of heuristic solutions are used to tackle intractable problems

Computational problem

A problem that can be solved in an algorithm

Representational Abstraction

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

Abstraction by generalisation/categorisation

The concept of reducing problems by putting similar aspects of a problem into hierarchial categories

Information hiding

The process of hiding all details of an object that don’t contribute to its essential characteristics

Procedural abstraction

Concept that all solutions can be broken down into a series of procedures or subroutines; basis of top-down design

Top-down design

Related to modular approach, this starts with the main system at the top and breaks it down into smaller and smaller units

Functional abstraction

Breaking down a complex problem into a series of reusable functions

Data abstraction

Hiding how data is represented so that it is easier to build a new kind of data object

Problem abstraction/reduction

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

Decomposition

Breaking large complex tasks or processes down into smaller, more manageable tasks; abstraction techniques will be used to decompose the system requirements

Composition

Process of creating a working system from the abstraction

What does composition involve?

• Writing all the procedures and linking them together to create compound procedures

• Creating data structures and combining them to form compound structures

Automation

Process of creating computer models of real-life situations and putting them into action