Computabillity Theory


One of the main objectives of the theory of computation is to determine what can and what cannot be computed. It is important to note that originally this notion of "being computable" was one largely of logical principle. This placed the study of computation almost entirely in the abstract, and relieved "computers" from any relevant details that should be addressed when thought of as actual computers that are physically realized in nature. In the 1930s, pure mathematical considerations led Alan Turing to construct an abstract model of computation using what are called Turing machines. Turing was motivated by the Entscheidungsproblem proposed by David Hilbert in 1928. This problem asked: Given any formal system and a statement from that system, does there exist some algorithmic means which can decide if that statement is either true or false within that system? The Turing machine was intended to have properties which enabled it to perform any algorithmic procedure that a human could do in principle. Thus, in a certain sense, the Turing machine was intended to automate human mathematicians. Using his theory, Alan Turing answered Hilbert's question in the negative. Around the same time, Alonzo Church independently arrived at this same conclusion using the formal system known as the Lambda calculus. Although this latter theory will not be described here, it was eventually shown that the theories of Church and Turing were equivalent.

Classical computation can be thought of as the evaluation of certain kinds of functions, called Boolean functions, between sets of bits. A classical bit \(\omega\) is an element of the set \(\{0,1\}\). This is the abstract definition of a bit and is the one of main concern in this paper. What can physically represent an actual bit in the real world will not be addressed here. Suffice it say that a classical bit is just an entity that is only able to be in one of two physically realizable states. What these two states are is essentially arbitrary and will depend on context.

To make the abstract definition of a classical bit precise, call \(\omega\in\{0,1\}^n\) a bitstring of length \(n\),where \(\{0,1\}^n\) is the Cartesian product of \(\{0,1\}\) with itself \(n\) times. Then in the special case when \(n=1\), \(\omega\in\{0,1\}\) is called a bit. An element of \(\omega\in\{0,1\}^n\), instead of being written as an \(n\)-tuple of the form \(\omega=(b_1,b_2,...,b_n)\) where \(b_i\in\{0,1\}\), will for our purposes be denoted simply by the concatenation of the \(n\) bits as \(b_1b_2...b_n\). For example, if \(\omega\in\{0,1\}^2\), then \(\omega\in\{00,01,10,11\}\). In this way, a Boolean function is a mapping \(f: \{0,1\}^n \rightarrow\{0,1\}^m\) for some natural numbers \(n\) and \(m\). A bitstring \(\omega\in\{0,1\}^n\) is called the input of \(f\), and the image \(f(\omega)\in\{0,1\}^m\) is another bitstring called the output of \(f\).


Some justification ought to be made for this binary paradigm of computing with simply \(0\)s and \(1\)s. Naively, one may think that regarding computations simply as Boolean functions operating on bits encoded as \(0\)s and \(1\)s is a crude and limited framework, because the problems we would expect computers to compute may be richer than what could possibly be expressed with just \(0\)s and \(1\)s. After all,most humans do not think of and solve problems in terms of \(0\)s and \(1\)s alone. For instance, why not allow the computer to have access to more than two symbols. Perhaps this would allow this augmented computer to compute things that a computer working with only two symbols could not. These issues are essentially a matter of how information representing the various things of interest is encoded by the computer. It turns out that for most reasonable circumstances involving problems that ought to be handled by computers the amount and kind of symbols used is an arbitrary choice. That is, although working with a certain set of symbols is more convenient in a particular computational task, a computers ability to actually perform the task is independent of the symbols being used. This even implies that a set of symbols consisting of only one element, say \(\{1\}\), is sufficient for performing computational tasks!

There is one issue, however, regarding the number of different symbols used to encode information. Despite being able to accomplish a task in principle using just \(\{1\}\) as the only permissible symbol, the computer may take exponentially more resources such as time or memory to achieve the task compared to a computer with access to more than one symbol. On the other hand, this exchange in exponentially more resources does not occur when comparing two computers who make use of two sets of symbols of different sizes both greater than one. In such a case, the difference in amount of resources could be at most some polynomial factor (as opposed to exponential). That is, for practical purposes, a computer making use of only two different symbols is just as good as one making use of more. This difference will become relevant in further discussions. For simplicity and conformity, we will therefore make use of the standard binary set of symbols \(\{0,1\}\) throughout.