Computability: Lecture 1

MAT246: Concepts in Abstract Math

July 31st 2024

Computability and Logic

Our goal for the last two weeks is to build a foundation for proving a famous result referred to as Godel’s Incompleteness Theorem.  This theorem roughly states that

Theorem 1. No system of axioms is capable of proving all truths about the arithmetic of natural numbers.

An important detail missed in the formulation above is that the system of axioms in question must have an algorithm capable of generating a complete list of potential theorem about the arithmetic of natural numbers.  We now set out to explore this idea of ”algorithm” and ”generating lists” .

Computable functions

We will begin our study of computability in an informal manner, meaning that we will not yet formally define what precisely an algorithm is, we will rather rely on our 21st century familiarity with computers and hopefully some basic understanding of the idea of a programming language.

Definition 1. An algorithm is a program that can be written in your program- ming language of choice.

Algorithms are somewhat similar to functions, they often have some form of input and some form. of output, a crucial difference is however that an algorithm isn’t always expected to produce a result - a computer program might loop infinitely and we are generally unable to distinguish whether or not it has looped or is just taking longer than expected to print out the result. To accommodate for this we will from now on have to deal with partially defined functions to reflect the fact that an algorithm might not produce a result on some input. It is standard practice in this area of math to use to word ”function” to mean partially defined function and to use ”total function” to mean a function defined everywhere.

Definition 2. A function is called computable if it can be realized by means of some algorithm.

We will primarily be concerned with function from the natural numbers into the natural numbers.  The reason we can afford to do this is that most ”data types” are countable. For example, computers don’t directly deal with natural numbers, but operate with finite binary strings.

Lemma 2. The set of finite binary strings is countable.

Proof.  For each fixed length there are only finitely many binary strings, taking the union overall all possible string lengths we see that the set of all finite binary strings is a countable union of finite sets.

We will also sometimes want to deal with n-tuples of natural numbers, but we also know that the sets Nn  are countable.  We know that the set of real numbers R is not countable, so it is unclear how to fit computations with real numbers into this framework, but take a look at problem 3 from tutorial 1.

The set of finite binary strings or n-tuples of natural numbers are not only countable, but also enumerable by an algorithm.   Recall that when we were constructing a bijection between N and N2  we didn’t do so explicitly, but rather defined a recursive procedure mapping N2  into N.  This leads to the following definition.

Definition 3. A set is called  recursively  enumerable  if there is  an algorithm that prints out its elements.

The set N2  is recursively enumerable:  start by printing  (0 , 0), then print (0, 1), then print (1, 0), then (0, 2); if the last pair printed was (x,y), then if y ≠ 0, print (x + 1, y − 1), otherwise print (0, x + 1) - this algorithm is exactly how we constructed the bijection between N2  and N moving along the diagonals of the N2  grid.

The set of finite binary strings is recursively enumerable: start by printing 0, then print 1, then 10; if the last string printed was a1 a2 ... an , then if all ai  = 1,

print 1 、(0)00000–, otherwise starting from the last digit find a 0 digit and change

n-times

it to 1 - this algorithm generates the set of finite binary strings by using binary arithmetic, the procedure described here is simply adding 1 to the previously printed number written in binary.

To practice understanding recursively enumerable sets lets give some equiv- alent definitions.

Lemma 3. •  A set is recursively enumerable if and only if it is the domain of definition of a computable function.

•  A set is recursively enumerable if and only if it is the set of values of a computable function.

Proof.  Given a recursively enumerable set X  define a computable function as follows: for a given input n we fire up the algorithm which prints the elements of X, when and if the element n is printed we stop and say that f(n) = 0. This defines a computable function which is equal to 0 on all elements of X and is undefined on all elements not belonging to X .  We could also define a computable function like this:  for a given input n we fire up the algorithm which prints the elements of X, when and if the n-th element is printed we stop and say that f(n) is equal to that element.  This defines a computable function whose set of values is precisely the set X, this function will be total if X is infinite and have a finite domain of definition if X is finite.

The key idea to prove the converse is that every algorithm follows a series of steps and we can perform these steps one at a time, this effectively allows us to run an increasingly large number of computations simultaneously.  Given a computable function f, we perform. the following algorithm: run one step of the computation off(0), then run one step of the computation of f(1), go back and do one more step of f(0), one step of f(1), one step of f(2), having done one more step of f(n), go back and do one more step of f(i) for all i < n, then do the first step of f(n + 1) and so on. Whenever we reach the final computation of a particular f(n), print n or print f(n), depending on if you wanted to print out the domain of definition or the set of values.

Lemma 4. The union and intersection of recursively enumerable sets is recur- sively enumerable.

Proof.  Given two  recursively enumerable sets X  and Y alternate doing steps of the algorithms that print X  and Y.   To print out the union simply print out whatever gets printed by either  algorithm,  but before doing that check whether or not this number was printed previously to avoid printing duplicates. To print out the intersection whenever one of the algorithms produces a new element check whether or not the other algorithm already produce it, if yes print it, otherwise continue, this process will eventually print all the elements in the intersection.

What about complements? This is where it gets tricky. We can attempt to wait and see whether or not a given element x gets printed, but how long do we wait?  There seems to be no way of knowing whether or not the algorithm is done printing or is just taking its time to print the next element. There is a particular type of set whose complement is for sure recursively enumerable.

Definition 4. A set is called decidable  if there is an algorithm that determines in a finite amount of time whether or not the element belongs to the set.

For example, the set of even natural number is a decidable set because we can devise an algorithm to check whether or not a given number is even or odd.

Lemma 5. Every decidable set is recursively enumerable.

Proof.  Starting  with 0 run the algorithm that checks whether or not 0 is in the set, do a few steps, then switch to the algorithm that checks whether or not 1 is in the set, do a few steps, then go back to 0, then try 2 and so on, gradually increasing the range covered.  Whenever one of the sub-algorithms checking whether or not n is in the set completes its work, print or don’t print n depending on the result.

The following result is commonly referred to as Post’s theorem.

Theorem 6. A set A is decidable if and only if both A and its complement are recursively enumerable.

Proof.  The proof of the lemma above also shows that a complement of decidable set is recursively enumerable.

Given a recursive enumerable set A such that its complement Ac   is also recursively enumerable we want to devise an algorithm which decides whether or not an element n is in the set.  Fire up both the algorithms which print A and Ac , in a finite amount of time one of them will print the element n.

Here is another important result relating decidable and recursively enumer- able sets.  It will be used later on understand formulas expressing fact about arithmetic.

Theorem 7. A subset of the natural numbers A is recursively enumerable if and only if it is the projection of a decidable set of pair of natural numbers.

Proof.  The projection of a recursively enumerable  set is also recursively enu- merable, we simply don’t print the second coordinate.

Given a recursively enumerable set A consider the set of pairs (x, n) such that the element x is printed within n steps of the algorithm for A.  The projection of this set is clearly set A. This set is decidable: given a pair (x, n) run n steps of the algorithm for A, if x is printed then it belongs to the set.

Why aren’tall subsets of natural numbers decidable/recursively enumerable? Why aren’t all function from N to N computable?  The cheap answer is cardinal- ity. There are only countably many algorithms, but there are uncountably many subsets of the natural numbers and uncountably many function from N to N. In the next lecture we will nevertheless give a clear example of a non-computable function and of a set which is recursively enumerable, but not decidable.