Computability and Complexity - Introduction

### 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

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:

### Algorithm

Complexity Theory also proposes definitions for the ideas of

### Computational Problems

At the lowest level of abstraction any computer program may be viewed as a means of producing

### 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

### 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

is equivalent to

### 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 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.