theory of computation

this is an sequence of steps that can be followed to complete a task.

Abstraction by Generalisation: is simplifying a problem by grouping together common characteristics of a problem to arrive at a hierarchal relationship. Representational Abstraction: Simplifying a problem by only taking into consideration the necessary details required to obtain a solution, leaving representation without any unnecessary details.

Procedural Abstraction: simplifying a problem by breaking it down into a series of procedures or subroutines that are generalised with variable parameters. Procedure: The result of abstracting away the actual values used in any particular computation is a computational pattern.

Simplifying a problem by breaking it down into a series of reusable functions which disregard the particular computational method.

Data abstraction: The storage and representation of data in a computer system along with its logical description and interaction with operators. This allows a construction of new compound data objects from existing ones. Data Objects: Data abstractions that hide details of ho data are actually represented from the user.

The repeated removal of unnecessary details from a problem until a underlying problem representation is reached which is identical to a previously solved problem.

The process of breaking down a problem into a number of sub-problems so that each sub-problem accomplished an identifiable task, which might itself be further subdivided.

Accepting states: an optional state of a FSM that indicates whether or not an input has been accepted by the FSM. FSM: A model of computation for a machine that is always in one of a fixed number of states. Mealy machine: a finite state machine that determines its outputs from the preset state from the inputs. State Transition diagrams: a visual representation of a FSm that uses circles to represent states. State Transition tables: contains current states and inputs and successor state in a table.

Finite set: A set who’s elements can be counted off by natural numbers up to a particular number. Infinite sets: A set that is not finite. cardinality of finite set: the number of elements in the set.

Regular Expression: A way of describing sets and the elements present within it using string s of characters. Regular language: A language that can be represented by a regular expression.

Cartesian product of set: The set of all ordered pairs(a, b) where a and b are from different sets. Countable sets: A set with same cardinality as some subset of

The creation of a set(an unordered collection of values In which each value is unique) by mathematically defining the element that qualify to be in the set.

A notation technique to express syntax of languages in computing.

A computable problem is one that can be solved algorithmically. whilst a non-computable is one that can’t be solved algorithmically.

The unsolvable problem of deterring whether any program will eventually stop if given a particular input.

this a model that consists of a finite state machine, a read/write head and a tape that is infinitely long in one direction. This tape is divided into several cells each of which can either be blank or contain a symbol. These can be changed using the read/write head.

This can be done using a transition function using δ(S0, □) = (S1, 1, R), this means if the machine is in state 1 and reads an empty cell then the machine should write a 1, move to state S1 and move to the right.

These are able to represent any finite state machine, they can be said to act as interpreters as they follow a sequence of instructions before executing the operations.

This states whether a program will stop or run forever, this means that no computer can see solve it.

this can be solved in a reasonable amount of time. so it has a polynomial time solution O(n^k).

this requires unlimited memory to be able to match equal number of a’s and b’s requires counting how many a’s were seen.

data abstraction hides how data is internally stored(using a stack without know how its implemented) whilst procedural abstraction hides how a procedure of function works internally. e.g. sort()