CE204
Data Structures and Algorithms
Part 9
08/03/2020 CE204 Part 9
1
Computability 1
Theoretical computer scientists have for many years been interested in the subject of computability, addressing the question of exactly what can be done by a computer. Informally a function can be said to be computable if we can write an algorithm or program to evaluate the function, but to give a precise definition we need to state exactly what is meant by an algorithm or program. The ambiguity in the use of the term program arises because there are many programming languages and it is not immediately obvious whether the class of functions that can be implemented in Java is the same as the class that can be implemented in a significantly different language.
08/03/2020 CE204 Part 9
2
Computability 2
The issue of computability has been studied since at least 1900, well before the advent of modern digital computers or high-level programming languages. In 1936 two scientists, Turing and Church, came up with independent formal definitions of what is meant by the term computable, using totally different approaches.
It was subsequently proved that the class of computable functions provided by these two definitions was the same (i.e. any function that is Turing-computable is also Church- computable and vice versa).
08/03/2020 CE204 Part 9
3
Computability 3
All functions that are computable using the Church-Turing definitions can be implemented in any programming language with a reasonable set of features.
The Church and Turing definitions regarded a function as being something which accepts input from a stream and produces output on a stream without accessing any external resources.
Limiting the meaning of a function in this way (so that we cannot allow GUIs or file access), no-one has managed to implement any function that is not computable by the Church- Turing definition, so all available evidence suggests that it is a reasonable definition.
08/03/2020 CE204 Part 9
4
Computability 4
A question which arises is “are there any non-computable functions?”. There are certainly well-defined problems for which no algorithmic solution is known, but this might be simply because the problems are very difficult and no-one has yet managed to develop an algorithm to solve them. If there are any non-computable functions it follows that can they never be implemented (unless the definition of computable is wrong).
It is in fact the case that there are some functions which can be proven to be non-computable – the best-known example is the halting problem.
08/03/2020 CE204 Part 9
5
Program Termination 1
Consider the following program.
public static void main(String args[])
{ int i = 0;
try
{ i = Integer.parseInt(args[0]);
}
catch (Exception e) { }
while (i!=0)
if (i%2==1) i–;
else i++;
System.out.println(“Done”); }
08/03/2020 CE204 Part 9
6
Program Termination 2
In what circumstances will the program on the previous slide terminate?
It is not difficult to see that it must either output the message Done or continue looping forever. If its command-line argument is “0” or “1” or any string that does not represent a valid number it will output the message and terminate but if the argument is a string holding any integer other than 0 or 1 it will not terminate. (For example if the argument is “8” the value of the variable i will repeatedly alternate between 8 and 9 and never become zero.)
08/03/2020 CE204 Part 9
7
Program Termination 3
When dealing with programs containing recursion it can be more difficult to determine whether they will terminate. We can be confident that the recursive methods we have written for trees will terminate since the argument to every recursive call refers to a smaller tree than that referred to by the argument to the calling method so we must eventually reach a leaf or an empty tree and we therefore cannot continue recursing indefinitely.
08/03/2020 CE204 Part 9
8
Ackermann’s Function 1
The following method calculates Ackermann’s function.
int ack(int n, int y)
{ if (n==0) return y+1;
else if (y==0) return ack(n-1, 1);
else return ack(n-1, ack(n, y-1));
}
The function is defined only for non-negative arguments; to ensure this happens it should be called from a method that checks that the arguments are valid, since we do not want to put this check into every recursive call.
08/03/2020 CE204 Part 9
9
Ackermann’s Function 2
We observe that the recursion is much more complex that in our tree traversals. Can we be sure that it will always terminate?
We can see that in every recursive call at least one of the arguments will be smaller than the corresponding argument in the caller but the other could be larger. Hence we cannot immediately observe that the recursive calls get simpler as recursion gets deeper. For example if we make a call to ack(2,2) one of the recursive calls will turn out to be to ack(1,5). It turns out that ack(2,2) will indeed terminate after making about 25 calls and return the value 7.
08/03/2020 CE204 Part 9
10
Ackermann’s Function 3
By observing that no recursive call is made with a larger first argument than that of the caller and also that when the first argument is the same the second is smaller, it is possible to prove that the recursion will terminate. We can define an ordering on pairs of numbers so that (a,b)<(c,d) if and only if a