Computability

Introduction

This part of the project 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'?

More precise formulations of these questions should specify the following :

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

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.

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.

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.

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
Godel-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 some specific computer language.
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 C (or any other computer language) program which solves P

The Halting Theory The Theory of Computation Summary of the Chapter in the book by John L. Casti: Five Golden Rules

In 1935, Alan Turing devised a theoretical gadget [which is also a model for a primitive computer] that he believed could settle the famous Hilbert Decision Problem. The Hilbert Decision Problem queries whether there exists an effective procedure for determining in advance if a certain conclusion follows logically from a given set of assumptions. This interesting problem was only hampered in Turing’s mind by the notion of an "effective procedure," or computation, which after thousands of years of use still had no clear cut definition. So Turing designed an imagined machine which utilizes an algorithm to carry out a computation.

This Turing Machine (TM) as it is called is composed of an infinitely long tape of ruled off squar4s that can each contain one of a finite set of symbols [in the simplest case: 1 and 0], and a scanning head that can write read and erase symbols of these squares. The algorithm for this machine is in all intents and purposes the program: the set of instructions that tells the machine what to do.

So how does this machine work?

First the data [the tape with a string of 1’s and 0’s] is fed into the Machine and then the Machine reacts to the data as the program calls. An example of a set of instructions by which such a machine is governed is as follows: 1. Go right one square. 2. Go to step 1 if the current square contains a 1. 3. Print 1 on the current square. 4. Go left one square. 5. Go to step 4 if the current square contains a 1. 6. Print 1 on the current square. 7. Stop. This program changes the zeroes at the end of a string of 1’s into 1’s. This program can either be imbedded permanently into the machine, so this machine can only perform these instructions or the instructions themselves can be fed into the machine on a tape so that the machine can perform any set of steps. This machine that can perform any set of steps is called a Universal Turning Machine (UTM)..

What can this machine compute?

An integer n can be computed is there is a TM that can produce it. So a number is computable if there is such a TM that will stop after printing n number of 1’s on an input tape of zeroes. Other real numbers can also be computed simply by printing a string of 1’s that represents each digit of the real number. Even irrational numbers are computable in this sense but the program will run on forever. But Turing says that these computable numbers constitute a small part of the set of all numbers and for the most part the great percentage of numbers are not computable.

So what is this Halting Problem?

The Halting Problem asks if there is a program that accepts a program P and input data I that after a finite number of steps halts, at which point the final configuration of the tape tells whether the program P will stop after a finite number of steps of processing data I. The Halting Theorem a la Turing states that no such program exists. And furthermore any thing that is computable can be computed by a suitable TM. A formal system is a system which is composed of abstract symbols. These symbols have no intrinsic meaning (such as words have a meaning in a sentence) other than the meaning the framework within which they are created gives to them (the sentence is either true or false, i.e. provable or unprovable). This framework of symbols is called a formal system. In this formal system a string of symbols may or may not constitute a theorem. A string is a theorem if and only if the string can be deduced from the set of axioms which defines the formal system. The formal system is equivalent to a TM.

What are the implications?

A formal system of arithmetic, per Hilbert, is finitely describable, consistent, complete [i.e., every mathematical truth translates to a theorem and every theorem translates to a mathematical truth], and sufficiently powerful enough to represent all statements that can be made about the natural numbers.

Hilbert believed that the system was formalizable, that is to say, that there is a finite procedure for deciding the truth or falsity of a statement. Goedel said that arithmetic is not formalizable. He also noted that formalized systems are ones that for which we have created a mathematical framework within which to speak about whatever it is we wanted to formalize. The formal system is a mathematical object itself. Goedel goes on to say that there may be a formal system powerful enough to represent arithmetic but that there exists truths that are not provable within that system. So this is the same as the Halting theorem in that there are statement sin arithmetic that cannot be proven or disproven just as there is no TM that will determine whether a program with input data will ever halt. So there is no Turing Machine that can print out the true statements of arithmetic. Truth is bigger than truth. This led Turing to embark on the quest to determine if a machine can or ever be able to think. His view was that if the machine appeared to think then it does think.

Like the Skinnerian behaviorists only external behaviors count not the "black box" that "determines" what those behaviors are. I appear to think therefore I think. But others view of thinking takes into account that the human mind can transcend rational [algorithmic] thought an know unprovable things. So humans have this one up on all machine which are limited by the theorem of Halting and the theorem of formal systems. Also the mind asserts its own consistency whereby a machine cannot. But consider the statement: A person cannot consistently assert this sentence. Assertion of truth cannot take place even though it is true. So there are statements that neither a machine nor a person can assert. But Goedel leaves open the possibility that a machine that can prove any theorem is possible but cannot be constructed. A machine too complex to design could nevertheless exist. An Example of Turing Machines

An Example of Turing Machines

(The Analytical Engine by Rick Decker and Stuart Hirshfield has a very good example of how the Turing Machine works. Here is a shortened version of it.)

The Turing Machine's control device embodies the program. It uses a set of rules, it's notion of "states", and the content of the tape to determine how to process the input symbols. The state that the machine regards itself as being in when the computation begins is called the "initial state". Each rule is stated in the form: "In state n, if the head is reading symbol x, write symbol y, move left or right one cell on the tape, and change the state to m."

Here are a set of rules for a Turing Machine (TM) with five states,
the initial state being 1.

Present State	Present Symbol	Write	Move	New State
1	0	0	Right	2
2	0	0	Right	3
2	1	1	Right	2
3	0	Blank	Left	5
3	1	0	Left	4
4	0	1	Right	2

You could simplify the table by writing each row in statements like (1, 0, 0, R, 2),
(2, 0, 0, R, 3), (2, 1, 1, R, 2), (3, 0, b, L, 5), (3, 1, 0, L, 4), and (4, 0, 1, R, 2).
This series of statements actually accomplishes integer addition. Say the input represents two numbers in unary notation that you want to add. To represent a pair of integers (x, k) in unary notation, you would start with a 0, followed by x 1's separated by another 0 followed by k 1's, you then end with a 0. So if you had the pair (2, 3) you would have a unary notation of 01101110. Now, using 01101110 for input and the rules for the TM from the table above you would get an output of 0111110. Here are the steps:

Number (In Unary)	Machine State	Movement
01101110	1	Write a Zero, Go to state two
01101110	2	Scan past 1's
01101110	2	End of first string, go to next
01101110	3	Change 1 to 0, go back.
01110110	4	Copy the 1, return to second string.
01110110	2	End of first string, go to next.
01110110	3	Change 1 to 0, go back.
01110010	4	Copy the 1, return to second string.
01111010	2	End of first string, go to next.
01111010	3	Change 1 to 0, go back.
01111010	4	Copy the 1, return to second string.
01111100	3	No second string. Erase last 0.
0111110	5	Halt--no further move possible.

There was no rule for symbol 0 in state 5 so the TM halts. This works correctly, because 2 and 3 equals 5. In unary notation five would be represented as 0111110 which is the answer gotten from the step through. Of course this is a very simple TM. When programmed correctly a TM Model can add, subtract, multiply, divide compute logs and powers, compare two data elements for equality or size, and perform other remarkably complex functions.

Click here for an Applet that simulates Turing Machine.

Return To Index