Theory Of Computation

a level computer science paper one topic four

what is an algorithm

a step by step series of instructions used to solve a problem

what are the different types of abstraction

functional, representational, categorical, procedural and data

what is decomposition

breaking down a large problem into smaller more easily solvable ones

what is automation

using models and algorithms to solve problems without manual intervention

what is a countably infinite set

sets that theoretically could be counted in a logical order, without ever reaching the end as they are infinite

what is the cardinality of a finite set

the number of members within the set

what is the cartesian product of a set

the complete combination of all their values

what is the difference between a subset and a proper subset

a proper subset has to have atleast one other data item that is not present in the data set

what are regular expressions

a way of describing a set or type of language

what is meant by regular language

language that can be defined by a regular expression, or accepted by a finite state machine

what are finite state machines

computational models that can be used to represent a regular expression

what is an example of a context free language

backus naur form (BNF)

how is BNF structured

<non terminal> ;; <non terminal> | <terminal>

what can BNF do that regular expressions cant

it can be used to represent recursion

what is recursion

The process of something making a call to itself until a base case is reached

what are the two ways algorithmic efficiency is measured as

time wise efficient, space wise efficient

what are tractable problems

problems that have a time complexity of polynomial or less

what are non-tractable problems

problems that have a time have an exponential time complexity, meaning they cannot be solved within a reasonable amount of time

what is the halting problem

a problem that asks the computer whether a program will halt/ terminate, or execute indefinitely

what does the halting problem prove?

it proves there are some problems a computer cannot solve

what can a turing machine be thought of as

a computer with a single fixed program

what are the components of a turing machine

a read write head, an infinite tape, a current state, a transition function, a finite set of states, a start state and end state

what does a transition function do

takes the current state and tape symbol, and determines the next state and symbol, as well as the direction the read/write head should move along the tape

what are problems solved by a turing machine thought to be

computable

why is a UTM thought to be more powerful than any real computer

due to its infinite memory

what is a UTM

a universal turing machine

what does a UTM do

takes a turing machine and interprets it for step by step execution