1.4 Theory of computation Flashcards
Define automation
Creating a computer model of a real-life situation and putting it into action
Define representational abstraction
The process of removing unnecessary details so that only information that is required to solve the problem remains
Define abstraction by generalisation / categorisation
The concept of reducing problems by putting similar aspects of a problem into hierarchical catgegories
Define top-down design
Starts with the main system at the top and breaks it down into smaller units
Define functional abstraction
Breaking down a complex problem into a series of reusable functions
Define data abstraction
Hiding how data is represented so that it is easier to build a new kind of data object, for example building a stack from an array
Define problem abstraction
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
Define information hiding
The process of hiding all details of an object that do not contribute to its essential characteristics
Define finite state machine
Any device that stores its current status and whose status can change as the result of an input. Mainly used as a conceptual model for designing and describing systems. There are a finite number of transitions that may take place
What is a state transition diagram?
A visual representation of an FSM using circles and arrows
Define accepting state
The state that identifies whether an output has been accepted
Define state transition table
A tabular representation of an FSM showing inputs, current state, and next state
Define Mealy machine
A type of finite state machine with outputs
What is a Turing machine?
A theoretical model of computation
What is the alphabet of a Turing machine?
The acceptable symbols (characters, numbers) for a given Turing machine
Define read/write head
The theoretical device that writes or reads from the current cell of tape in a Turing machine
Define halting state
The state that stops a Turing machine
Define start state
The initial state of a Turing machine
Define transition function/rule
A method of notating how a Turing machine moves from one state to another and how the data on the tape changes
Define state transition diagram
A visual representation of the transition function of a Turing machine
How does a Turing machine operate?
- Tape divided into an infinite number of cells which are used as memory
- Each cell will contain a symbol, either a character or number, the range of acceptable symbols is the alphabet
- The read/write head can either read what is in the cell, write to the cell, or erase its contents
- The tape can move left or right one cell at a time so every cell is accessible by a read/write head
- The machine can halt at any point if it enters the halting state or if the whole input has been processed
What is needed to represent programs with a Turing machine?
- A start state
- A halting state
- An alphabet
- Movement
- A transition function
Define instruction table
A method of describing a Turing machine in tabular form
Define universal machine
A machine that can simulate a Turing machine by reading a description of the machine along with the input of its own tape
Define a regular language
Any language that can be described using regular expressions
Define a regular expression
Notation that contains strings of characters that can be matched to the content of a set
What symbol represents or in regex?
|
What symbol represents zero or more of a character?
*
What symbol represents one or more of a character?
+
What symbol represents zero or one of a character?
?
What symbol represents a wildcard character?
.
Define a context-free language
An unambiguous way of describing the syntax of a language useful when a language is context
Define Backus-Naur Form (BNF)
A form of notation for describing the syntax used by a programming language
Define terminal in BNF
The final element that requires no further rules
Define syntax diagram
A method of visualising rules written in BNF or any other context-free language
Define set comprehension
The process of creating sets by describing them using notation rather than listing the elements
Define finite set
A set where the elements can be counted using natural numbers up to a particular number, an infinite set is the opposite of this
Define cardinality
The number of elements in a set
Define countable set
A finite set where the elements can be counted using natural numbers
Define countably infinite sets
Sets where the elements can be put into a one-to-one correspondence with the set of natural numbers
Define cartesian product
Combining the elements of two or more sets to create a set of ordered pairs
Define union
Where two sets are joined and all of the elements of both sets are included in the joined set
Define intersection
Describes which elements are common to both sets when two sets are joined
Define difference
Describes which elements differ when two sets are joined together
Define subset
A set where the elements of one are entirely contained within the other; can include two sets that are exactly the same
Define proper subset
Where one set is wholly contained within another and the other set has additional elements
Define space complexity
The concept of how much space an algorithm requires
Define input size
In Big O notation this is the size of whatever data you are asking an algorithm to work with
Define time complexity
The concept of how much time an alogrithm requires
Define constant time
In Big O notation where the time taken to run an algorithm does not vary with the input size
Define linear time
In Big O notation where the time taken to run an algorithm increases in direct proportion with the input size
Define exponential time
In Big O notation where the time taken to run an algorithm increases as an exponential function of the number of inputs
Define logarithmic time
In Big O notation where the time taken to run an algorithm increases or decreases in line with a logarithm
Define polynomial time
In Big O notation where the time taken to run an algorithm is a polynomial function of the input size
What is Big O notation?
Big O notation is a way of describing the time spcae complexity of an algorithm, looking at the maximum time it could take an algorithm to complete
Define tractable problem
A problem that can be solved in an acceptable amount of time
Define intractable problem
A problem that cannot be solved within an acceptable time frame
Define heuristic
With algorithms, it is a method for producing an acceptable but not necessarily best solution to an intractable problem
Define unsolvable problem
A problem that has been proven that it cannot be solved computationally
What is the halting problem?
An example of an unsolvable problem where it is impssible to write a program that can work out whether another problem will halt given a particular input
