Basic Concepts 6 – Computability, Decidability and Enumerability

In the first article of this series, we encountered the concept of a function. In the previous article, we have gained a first, intuitive understanding of programs. We can now define a few basic concepts. A rigorous and exact definition would require that we define the concept of a program more exactly, but it is sufficient here if we get a rough understanding.

Datei:Alan Turing az 1930-as években.jpg

We call a function computable if it is possible to write a program that calculates that function. The inputs and outputs might be arbitrary data, but to make mathematical analysis easier, mathematicians often restrict themselves to functions whose inputs and outputs are natural numbers. We have seen in a previous article how the concept of Gödel numbers can be used to map arbitrary data into natural numbers and vice versa, so we do not actually lose anything with such a restriction.

In later articles, we will see examples of functions that are not computable, so we will see that not every function can be calculated by a program.

We call a set (of natural numbers, or of any kind of data) enumerable if it is the set of possible outputs of a computable function whose inputs are the natural numbers. So by putting the sequence of the natural numbers 1, 2, 3, etc. (or more exactly: data objects representing those numbers, e.g. strings of decimal digits) into the program computing that function, we can generate the first, second, third etc. result. The same output might be generated from more than one input, but we could check the elements generated already before for duplicates. As a result, we can generate each element of the set.

Examples of enumerable sets:

Obviously, the set of natural numbers is enumerable. We can write a program that just copies its input into the output. If the inputs are all the natural numbers, the outputs must be all the natural numbers as well.

Other examples are the set of even numbers and the set of odd numbers, the set of prime numbers, etc.

We will get to know sets that are not enumerable in a later article. Such sets will play an important role in our argumentation.

A set is called decidable if we can write a program that can check if its input is a member of that set or not. The program will have two different outputs; we can choose 1 and 2 for this purpose, for example. If the input belongs to the set, the program will yield one of the outputs (that we can interpret as “yes”), if it does not, it will yield the other output (that we will interpret as “no”).

Examples:

We can check if a number is an even number.

If we define a scheme to produce Gödel numbers, we can check if a given number is a Gödel number or not.

For programming languages, we can decide if a given string of characters is a program in that programming language or not.

If a set is decidable and it is a sub-set of an enumerable set, it is generally also enumerable. For example, we can enumerate all natural numbers. For each of them, we can check if it is a Gödel number. By searching this way through the numbers for the next Gödel number, we can enumerate the Gödel numbers which form a sub-set of all natural numbers.

On the other hand, enumerable sets are not always decidable. In some cases, it is possible to generate all the elements of a set, one after the other, but as long as a specific element has not yet been generated, we will not know if it ever will or not.

(The picture is from https://de.wikipedia.org/wiki/Datei:Alan_Turing_az_1930-as_%C3%A9vekben.jpg. It is showing Alan Turing, one of the fathers of computability theory, the branch of mathematics, logic and computer science that deals with the concepts introduced in this article.)

Advertisements

One comment

  1. […] order to turn the intuitive concepts discussed in the previous article into exact concepts, one would have to define exactly what a program is. Different mathematicians […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: