Computability and Complexity - Introduction
Comparing Algorithms
Computability and Complexity
The final part of the course deals with the issue of
assessing how difficult
specific computational problems are to solve.
Given a description of a particular problem a number of questions arise:
-
Is it possible to design an algorithm which solves the problem?
-
Is it possible to design an efficient algorithm which solves the problem?
-
How can one tell if a given algorithm is the `best possible'?
These questions are imprecisely formulated:
-
What exactly is meant by the term `problem'?
-
What distinguishes algorithms which can be implemented
from those which cannot?
-
What is meant by terms such as:
-
Difficulty
-
Efficient
-
Best
COMPUTABILITY THEORY
and
COMPUTATIONAL COMPLEXITY THEORY
are the fields of Computer Science concerned with the
questions raised earlier.
Computability Theory
is concerned with identifying one particular class of
INTRACTABLE PROBLEMS
(Those for which no `effective' algorithm exists)
One aim of
Computational Complexity Theory
is to identify solvable problems that are intractable in the sense that
No Efficient Algorithm Exists
which solves them.
Both areas require a formal definition of the concepts:
Problem
Algorithm
Complexity Theory also proposes definitions for the ideas of
Problem Difficulty
Algorithm Efficiency
Best Algorithm
Computational Problems
At the lowest level of abstraction any computer program may be viewed as
a means of producing
Specific Output Values
from
Given Input Data
i.e. Programs compute functions whose domain is the set of valid inputs
and whose range is the set of possible outputs.
In practice the input and output are (ultimately) represented in binary
Hence any program may be viewed as (computing) some function
f : {0,1}^* -> {0,1}^*
({0,1}^* is the set of all finite strings
(or words) containing only 0s and 1s.
It is only necessary to consider such functions as have
range {0,1}. These are known as
Decision Problems
Summary
-
All computer programs may be viewed as computing functions
-
Since all computers employ binary notation, such functions
are defined over sets of binary strings.
-
In considering the question `what problems can be solved
by computers' it is sufficient to concentrate on decision problems
Hence the question
What problems can be solved by computers?
is equivalent to
What decision problems can be solved?
Decision Problems
Any binary string can be viewed as the representation
of some natural number. Thus for decision
problems on binary strings we can concentrate on the
set of functions of the form
f : N -> {0,1}
That is `problems' of the form
Input: n a natural number
Output: 1 if n satisfies some property; 0 if n does not satisfy it.
Examples:
-
EVEN: Returns 1 if n is an even number; 0 if n is an
odd number
-
PRIME: Returns 1 if n is a prime number; 0 if n is a
composite number.
-
ADA_PROGRAM: Returns 1 if n written in
binary corresponds to the ASCII representation of
a syntactically correct ADA program; 0 otherwise.
Notice that the last example shows that we are not restricting attention to merely `arithmetic'
decision problems.
What is a `reasonable' algorithm?
In all programming systems
-
Programs have a finite number of instructions.
-
Progams make use of instructions and operations from a
finite set of basic operations
-
Programs should come to a halt for any valid input data.
An effective algorithm is one which meets these criteria.
Suppose we can show that an ADA program cannot be written which solves some problem.
Why should one take this as evidence that
NO PROGRAM (ALGORITHM) AT ALL
exists for the problem?
In other words
How can it be argued that results on computability apply to all types of
computer?
(Past, Present, and Future)
The answer is that such results are proved with
respect to abstract models of computation
that capture all the essential elements of a typical computer.
A `typical computer' has
-
Memory
-
Input and Output Mechanisms
-
A processor handling a finite instruction set.
In an abstract model we can permit an infinite supply of memory. The only
restraint on an algorithm is that it can only
use a finite amount of memory when dealing
with any single input (which, if the algorithm terminates, is all that could be
accessed).
This is not an unrealistic assumption: we do not want to
classify a problem as
unsolvable just because on some real machines there
may not be enough memory available.
The first abstract model of computation was defined by Alan Turing in 1936. This had:
-
An infinite memory of single bit cells.
-
Its `processor' dealt with only two types of `instruction'
-
A stop instruction which would return a result (0 or 1).
-
A test instruction which would read and write to a single bit of memory,
examine an adjacent memory location, and jump to another instruction.
Although the instruction set of the Turing Machine is extremely limited
Turing machine programs can be written to solve any decision problem that
can
be solved on a `normal' computer.
The Church-Turing Hypothesis
-
The class of decision problems that can be solved by any reasonable model of
computation
is exactly the same as the class of decision problems that can be solved
by Turing machine
programs.
Since 1936 several thousand different models of computation have been proposed,
e.g.
-
Post Systems
-
Markov Algorithms
-
lambda-calculus
-
Gö del-Herbrand-Kleene Equational Calculus
-
Horn Clause Logic
-
Unlimited Register Machines
-
ADA programs on unlimited memory machines
Every single one of these satisfies the Church-Turing hypothesis, i.e. anything
that can
be solved by a Turing machine program can be programmed in
any one of the system above and
vice-versa
The importance of the Church-Turing hypothesis is that it allows us, without any
loss of generality, to consider computability results solely with respect to
ADA programs on unlimited memory computers
Suppose P is some decision problem.
The Church-Turing hypothesis asserts
There is no Turing machine program that computes P
IF AND ONLY IF
There is no ADA program which solves P
Because we can (in principle) write a Turing machine program which
can exactly simulate the behaviour of any given ADA program.
Similarly, we can write an ADA program which can exactly simulate the
behaviour of any given Turing machine program.
PED Home Page