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:

These questions are imprecisely formulated:




are the fields of Computer Science concerned with the questions raised earlier.

Computability Theory

is concerned with identifying one particular class of


(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:



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


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


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.


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

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


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

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:

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

Since 1936 several thousand different models of computation have been proposed, e.g. 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


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