Computability theory (computer science)

For the branch of mathematical logic called computability theory, see recursion theory.

In computer science, computability theory is the branch of the theory of computation that studies which problems are computationally solvable using different models of computation.

Computability theory differs from the related discipline of computational complexity theory, which deals with the question of how efficiently a problem can be solved, rather than whether it is solvable at all.

Introduction

A central question of computer science is to address the limits of computing devices by understanding the problems we can use computers to solve. Modern computing devices often seem to possess infinite capacity for calculation, and it's easy to imagine that, given enough time, we might use computers to solve any problem. However, it is possible to show clear limits to the ability of computers, even given arbitrarily vast computational resources, to solve even seemingly simple problems.

To explore these areas, computer scientists usually address the ability of a computer to answer the question: Given a formal language, and a string, is the string a member of that language? This is a somewhat esoteric way of asking this question, so an example is illuminating. We might define our language as the set of all strings of digits which represent a prime number. To ask whether an input string is a member of this language is equivalent to asking whether the number represented by that input string is prime. Similarly, we define a language as the set of all palindromes, or the set of all strings consisting only of the letter 'a'. In these examples, it is easy to see that constructing a computer to solve one problem is easier in some cases than in others.

But in what real sense is this observation true? Can we define a formal sense in which we can understand how hard a particular problem is to solve on a computer? It is the goal of computability theory to answer just this question.

Formal models of computation

In order to begin to answer the central question of computability theory, it is necessary to define in a formal way what a computer is. There are a number of useful models of computation. Some widely known models are:

Deterministic finite state machine: Also called a deterministic finite automaton (DFA), or simply a finite state machine. A simple model of computation. All real computing devices in existence today can be modeled as a finite state machine. Such a machine has a set of states, and a set of state transitions which are affected by the input stream. Certain states are defined to be accepting states. An input stream is fed into the machine one character at a time, and the state transitions for the current state are compared to the input stream, and if there is a matching transition the machine may enter a new state. If at the end of the input stream the machine is in an accepting state, then the whole input stream is accepted.

Pushdown automaton: Similar to the finite state machine, except that it has available an execution stack, which is allowed to grow to arbitrary size. The state transitions additionally specify whether to add a symbol to the stack, or to remove a symbol from the stack.

Turing machine: Also similar to the finite state machine, except that the input is provided on an execution "tape", which the Turing machine can read from, write to, or move back and forth past its read/write "head". The tape is allowed to grow to arbitrary size. The Turing machine is capable of performing complex calculations which can have arbitrary duration. This model is perhaps the most important model of computation in computer science, as it simulates computation in the absence of predefined resource limits.

Power of computational models

With these computational models in hand, we can determine what their limits are. That is, what classes of languages can they accept?

Power of finite state machines

Computer scientists call any language that can be accepted by a finite state machine a regular language. Because of the restriction that the number of possible states in a finite state machine is finite, we can see that to find a language that is not regular, we must construct a language that would require an infinite number of states.

Such a language is the set of all strings consisting of the letters 'a' and 'b' which contain an equal number of the letter 'a' and 'b'. To see why this language cannot be correctly recognized by a finite state machine, assume first that such a machine $M$ exists. $M$ must have some number of states $n$ . Now consider the string $x$ consisting of $(n+1)$ 'a's followed by $(n+1)$ 'b's.

As $M$ reads in $x$ , there must be some state in the machine that is repeated as it reads in the first series of 'a's, since there are $(n+1)$ 'a's and only $n$ states by the pigeonhole principle. Call this state $S$ , and further let $d$ be the number of 'a's that our machine read in order to get from the first occurrence of $S$ to some subsequent occurrence during the 'a' sequence. We know, then, that at that second occurrence of $S$ , we can add in an additional $d$ (where $d > 0$ ) 'a's and we will be again at state $S$ . This means that we know that a string of $(n+d+1)$ 'a's must end up in the same state as the string of $(n+1)$ 'a's. This implies that if our machine accepts $x$ , it must also accept the string of $(n+d+1)$ 'a's followed by $(n+1)$ 'b's, which is not in the language of strings containing an equal number of 'a's and 'b's.

We know, therefore, that this language cannot be accepted correctly by any finite state machine, and is thus not a regular language. A more general form of this result is called the Pumping lemma for regular languages, which can be used to show that broad classes of languages cannot be recognized by a finite state machine.

Many would object to this result by saying that they can easily write a computer program on their desktop PC to recognize such a language, and we've previously stated that a desktop PC, along with all real computers, are finite state machines. And it is true that it is easy to write such a program, but it would be subject to a limitation: the memory capacity of the computer. Given a long enough string, the memory capacity of the computer would eventually be exhausted by an attempt to maintain a count of the number of input characters, and eventually would overflow. At that point, it must enter a state it has previously been in before. So, while it could recognize a great many such strings, there are strings in this language that it could not recognize. This should help to understand how this result about regular languages applies even to a desktop PC.

Power of push-down automata

Computer scientists define a language that can be accepted by a push-down automaton as a Context-free language, which can be specified as a Context-free grammar. The language consisting of strings with equal numbers of 'a's and 'b's, which we showed was not a regular language, can be decided by a push-down automaton. Also, in general, a push-down automaton can behave just like a finite-state machine, so it can decide any language which is regular. This model of computation is thus strictly more powerful than finite state machines.

However, it turns out there are languages that cannot be decided by push-down automaton either. The result is similar to that for regular expressions, and won't be detailed here. There exists a Pumping lemma for context-free languages. An example of such a language is the set of prime numbers.

Power of Turing machines

Turing machines can decide any context-free language, in addition to languages not decidable by a push-down automata, such as the language consisting of prime numbers. It is therefore a strictly more powerful model of computation.

Because Turing machines have the ability to "back up" in their input tape, it is possible for a Turing machine to run for a long time in a way that is not possible with the other computation models previously described. It is possible to construct a Turing machine that will never finish running (halt) on some inputs. We say that a Turing machine can decide a language if it eventually will halt on all inputs and give an answer. A language that can be so decided is called a recursive language. We can further describe Turing machines that will eventually halt and give an answer for any input in a language, but which may run forever for input strings which are not in the language. Such Turing machines could tell us that a given string is in the language, but we may never be sure based on its behavior that a given string is not in a language, since it may run forever in such a case. A language which is accepted by such a Turing machine is called a recursively enumerable language.

The Turing machine, it turns out, is an exceedingly powerful model of computation. Attempts to amend the definition of a Turing machine to produce a more powerful machine are surprisingly met with failure. For example, adding an extra tape to the Turing machine, giving it a 2-dimensional (or 3 or any-dimensional) infinite surface to work with can all be simulated by a Turing machine with the basic 1-dimensional tape. These models are thus not more powerful. In fact, the Church-Turing thesis conjectures that there is no reasonable model of computation which can decide languages that cannot be decided by a Turing machine. People have proposed models of computation more powerful than a Turing machine. However, these are generally considered to be unrealistic or unreasonable (See below).

Turing machines provide, therefore, an extremely powerful way of understanding broad questions about the very limits of computability. The question to ask then is: do there exist languages which are recursively enumerable, but not recursive? And, furthermore, are there languages which are not even recursively enumerable?

The halting problem

The halting problem is one of the most famous problems in computer science, because it has profound implications on the theory of computability and on how we use computers in everyday practice. The problem can be phrased:

Given a description of a Turing machine and its initial input, determine whether the program, when executed on this input, ever halts (completes). The alternative is that it runs forever without halting.

Here we are asking not a simple question about a prime number or a palindrome, but we are instead turning the tables and asking a Turing machine to answer a question about another Turing machine. It can be shown (See main article: Halting problem) that it is not possible to construct a Turing machine that can answer this question.

That is, the only way to know for sure if a given program will halt on a particular input in all cases is simply to run it and see if it halts. If it does halt, then you know it halts. If it doesn't halt, however, you may never know if it will eventually halt. The language consisting of all Turing machine descriptions paired with all possible input streams on which those Turing machines will eventually halt, is not recursive. The halting problem is therefore called noncomputable or undecidable.

An extension of the halting problem is called Rice's Theorem, which states that all nontrivial properties of the language accepted by a Turing machine are undecidable.

Beyond recursive languages

The halting problem is easy to solve, however, if we allow that the Turing machine that decides it may run forever on input that does not halt. The halting language is therefore recursively enumerable. It is possible to construct languages which are not even recursively enumerable, however.

A simple example of such a language is the complement of the halting language; that is the language consisting of all Turing machines paired with input strings where the Turing machines does not halt on its input. To see that this language is not recursively enumerable, imagine that we construct a Turing machine $M$ which is able to give a definite answer for all such Turing machines, but that it may run forever on any Turing machine that does eventually halt. We can then construct another Turing machine $M'$ that simulates the operation of this machine, along with simulating directly the execution of the machine given in the input as well, by time-sharing the execution of the two programs. Since the direct simulation will eventually halt if the program it is simulating halts, and since by assumption the simulation of $M$ will eventually halt if the input program would never halt, we know that $M'$ will eventually have one of its "threads" halt. $M'$ is thus a decider for the halting problem. We have previously shown, however, that the halting problem is undecidable. We have a contradiction, and we have thus shown that our assumption that $M$ exists is incorrect. The complement of the halting language is therefore not recursively enumerable.

Unreasonable models of computation

The Church-Turing thesis conjectures that there is no reasonable model of computing more powerful than a Turing machine. In this section we will explore some of the "unreasonable" ideas for computational models which violate this conjecture. Computer scientists have imagined many varieties of hypercomputers. Recursion theory is the branch of mathematical logic that deals rigorously with these models of computation.

Infinite execution

Imagine a machine where each step of the computation requires half the time of the previous step. If we normalize to 1 time unit the amount of time required for the first step, the execution would require

1 + {1 \over 2} + {1 \over 4} + \cdots

time to run. This infinite series converges to 2 time units, which means that this Turing machine can run an infinite execution in 2 time units. This machine is capable of deciding the halting problem by directly simulating the execution of the machine in question.

Oracle machines

So-called Oracle machines have access to various "oracles" which provide the solution to specific undecidable problems. For example, the Turing machine may have a "halting oracle" which provided immediately whether a given Turing machine will ever halt on a given input.

Limits of hypercomputation

Even these machines, which seemingly represent the limit of computation that we could imagine, run into their own limitations. While each of them can solve the halting problem for a Turing machine, they cannot solve their own version of the halting problem. That is, an Oracle machine cannot answer the question of whether a given oracle machine will ever halt.

History of computability theory

The lambda calculus, an important precursor to formal computability theory, was developed by Alonzo Church and Stephen Cole Kleene. Alan Turing is most often considered the father of modern computer science, and laid many of the important foundations of computability and complexity theory, including the first description of the Turing machine (in ^*, 1936) as well as many of the important early results.

References

Part Two: Computability Theory, chapters 3–6, pp.123–222.
Chapter 3: Computability, pp.57–70.

Theory of computation

Gourt Home::Gourt :: Computability theory (computer science)