PDF version of this book

Arithmetical Hierarchy

The Arithmetical Hierarchy predated Gödel's result, but his work led to recognizing it as a hierarchy of unsolvable problems of increasing difficulty. Traditionally it was defined as the hierarchy that comes from logical expressions that contain quantifiers over the integers. This chapter develops the hierarchy by relating it to the Halting Problem for computers.

Consider the function $h(n)$ that is 1 if the computer program with Gödel number $n$ halts and 0 otherwise. This function cannot be generated by a computer program. But one can write a program to output the Gödel numbers of any computer program $n$ for which $h(n)$ = 1. That is one can write a computer program that outputs the Gödel numbers of all computer programs that halt. What one cannot do is list the Gödel numbers of programs that do not halt.

To output the Gödel numbers of all computer programs that halt, program a single computer to execute the program corresponding to every Gödel number. This involves a sequence of steps. In the first step one instruction from the program with Gödel number 1 is executed. In the next step 2 instructions for programs 1 and 2 are executed. This is 4 instructions total. In the $n$th step $n$ instructions are executed for programs 1 through $n$. This is $n^2$ instructions total. If any program halts during any step then the Gödel number of that program is output. Eventually, if any program halts, its Gödel number will be output. This is not a solution to the halting problem because it provides no way to know if a program does not halt. We have to wait an infinite time before we can be sure a program's Gödel number will not be output.

This simulation of many programs by a single program is called nondeterministic programming although there is nothing random or unpredictable about it. A computer running such a program is called a nondeterministic computer.

A set that can be listed using a computer program is said to be recursively enumerable. If one can also list by a computer the complement of the set (those integers not in the set) than it is said to be recursive. The set of Gödel numbers of computer programs that halt is recursively enumerable but not recursive. This is the first in a hierarchy of recursively unsolvable problems that form the Arithmetical Hierarchy.

One can speculate about `more difficult' problems by assuming one had a solution for the halting problem and ask what new problems would remain unsolvable. This led to the idea of a computer with an oracle. An oracle is a magical device that solves some unsolvable problem like the Halting Problem. You input to it an integer $n$ and in a finite time it outputs 1 or 0 to indicate if the program with Gödel number $n$ will or will not halt.

Assuming a computer exists that has access to an oracle for the Halting Problem, are there functions it cannot compute? One can apply the original Halting Problem proof to this machine to prove it could not solve its own Halting Problem. One could give an oracle for this higher level Halting Problem and generate an even higher level problem. Thus was introduced the notion of degrees of unsolvability.

A related way to extend the hierarchy of unsolvable problems is to ask if a computer program will generate an infinite number of outputs. This property can be generalized by interpreting the output of a computer as the Gödel number of another computer. One can thin ask this question. Does a program have an infinite number of outputs an infinite subset of which, when interpreted as computer programs, have an infinite number of outputs? This can be iterated any finite number of times to create the Arithmetical Hierarchy.

This hierarchy is usually developed with the universal ($\forall$) and existential ($\exists$) quantifiers restricted to the integers rather than ranging over all possible sets.

An alternating pair of these quantifiers ( $\forall\exists$) restricted to the integers has been shown to be equivalent to the $Un$ quantifier. $Un\hspace{.05in}g(n)$ is true if and only if $g(n)$ is true for an infinite subset of the integers. The Arithmetical Hierarchy can be defined using either the $U$ quantifier or alternating pairs of existential and universal quantifiers.

Levels in the Arithmetical Hierarchy are labeled as $\Sigma_n$ if they can be defined with an expression limited to $n-1$ pairs of alternating quantifiers starting with $\Sigma$. Similarly statements that start with $\forall$ are labeled as $\Pi_n$. $\Sigma_0$ and $\Pi_0$ are defined as having no quantifiers and are equivalent. $\Sigma_1$ and $\Pi_1$ are defined as having a single quantifier. Table 6.1 summarizes these definitions.

Only alternating pairs of quantifiers are counted because two quantifiers of the same type occurring together are equivalent to a single quantifier. Table 6.2 shows a map from the integers onto all pairs of integers. Using this map one can convert a sequence like $\forall x \forall y\hspace{.05in} g(x,y)$ to $\forall z \hspace{.05in} g(x(z),y(z))$. The same technique applies to two consecutive existential ($\exists$) quantifiers. An expressions ending with $\forall x \exists w \forall y \hspace{.05in} g(x,w,y)$ can be rewritten as an expression ending with $\forall z \exists w\hspace{.05in}g(x(z),w,y(z))$. A similar reduction works with $\exists x \forall w \exists y \hspace{.05in} g(x,w,y)$. So Table 6.1 gives all unique possibilities.

Table 6.1: Arithmetical Hierarchy

Level	Questions one can ask: will a computer program
$\Sigma_0$	halt in fixed time
$\Sigma_1$	ever halt
$\Pi_1$	never halt
$\Sigma_2$	have at most a finite number of outputs
$\Pi_2$	have an infinite number of outputs
$\Sigma_3$	have at most a finite number of $\Pi_2$ outputs
$\Pi_3$	have an infinite number of $\Pi_2$ outputs
$\Sigma_n$	have at most a finite number of $\Pi_{n-1}$ outputs
$\Pi_n$	have an infinite number of $\Pi_{n-1}$ outputs

Table 6.2: Mapping pairs of integers onto the integers

x	z
...	...	...	...	...	...	...	...	...	...	...	...
9	81	82	83	84	85	86	87	88	89	90	...
8	64	65	66	67	68	69	70	71	72	91	...
7	49	50	51	52	53	54	55	56	73	92	...
6	36	37	38	39	40	41	42	57	74	93	...
5	25	26	27	28	29	30	43	58	75	94	...
4	16	17	18	19	20	31	44	59	76	95	...
3	9	10	11	12	21	32	45	60	77	96	...
2	4	5	6	13	22	33	46	61	78	97	...
1	1	2	7	14	23	34	47	62	79	98	...
0	0	3	8	15	24	35	48	63	80	99	...
y	0	1	2	3	4	5	6	7	8	9	...

This table shows part of a mapping from the integers onto all pairs of integers. For every integer pair $(x,y)$ there is a unique $z$. The table is generated by placing 0 at $(0,0)$ and adding one to each successive entry. The sequence of entries go across to the diagonal and then down. The across down sequence is continually repeated starting just above the previous row.

PDF version of this book