4.4 Theory of Computation

Algorithm

A sequence of instructions that can be followed to complete a task and always terminates

Abstraction

Removing unnecessary details to simplify a problem and focus on important details to make it easier to solve

Representational Abstraction

Representation arrived at by removing unnecessary details

Abstraction by generalisation

Grouping by common characteristics to arrive at some kind of hierarchy or "is a kind of" relationship

Information hiding

hiding details that don't contribute to essential characteristics

Procedural abstraction

ensuring subroutines are as generalised and reusable as possible
- separate UI and processing of data
- abstract real values used

Functional Abstraction

hide complexity of algorithm with subroutine

Data Abstraction

The details of how data are actually represented are hidden.
data objects are made using pre-defined data types

Problem abstraction

Removing unnecessary details in a problem until the underlying problem is one that has already been solved

Automation

design, implement and execute a solution using abstractions
1)design solution
2)implement data structures
3)implement algorithms
4)execute code

tractable

problems that can be solved in polynomial time of less

Halting Problem

there cannot be a program that will determine which computer programs will halt given their inputs without executing the program

Turing Machine

a model of computation with a single program which manipulates symbols on tape. show what is computable
- finite states
- finite alphabet of symbols
-infinite length of tape
-read-write head

Universal Turing Machine (UTM)

can simulate the behaviour of any Turing Machine. an interpreter that reads the description of any Turing machine and faithfully executes operations on data precisely as the original does.
- infinite memory so most powerful computer

Function vs Procedure

Function A subroutine that returns a value.
Procedure A subroutine that does not return a value.