Arithmetical Hierarchy

The function

that is 1 if the computer program with Gödel number

halts and 0 otherwise cannot be generated by a computer program. But we can write a computer program to output the Gödel numbers of any computer program

for which

= 1. That is we can write a computer program that outputs the Gödel numbers of all computer programs that halt. What we 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 we program a single computer to execute all possible computer programs. We do this in a sequence of steps. In the first step we do one instruction from one program. In the next step we do 2 instructions for 2 programs (or four instructions total). In the

th step we do

instructions for

programs. If any program halts during any step then we output the Gödel number of that program. 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 we can list using a computer program is said to be recursively enumerable. If we can also list by a computer the complement of 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.

We 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

and in a finite time it outputs 1 or 0 to indicate if the program with Gödel number

will or will not halt.

Assuming we have a computer 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. We can generalize this property by interpreting the output of a computer as the Gödel number of another computer. We then ask 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

quantifier. $Un\hspace{.05in}g(n)$ is true if and only if

is true for an infinite subset of the integers. The Arithmetical Hierarchy can be defined using either types of quantifiers

Levels in the Arithmetical Hierarchy are labeled as $\Sigma_n$ if they can be defined with an expression limited to

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 4.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 4.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. Expressions ending with $\forall x \exists w \forall y \hspace{.05in} g(x,w,y)$ can be reduced to one 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 4.1 represent all the unique possibilities.

Table 4.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 4.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 there is a unique . The table is generated by placing 0 at and then moving up to row 1. All entries are made by adding one to the previous entry. Entries are made across each new row up to the diagonal. Then that columns entries below the diagonal are filled highest row first. This process is repeated starting at the lowest empty row. The sequence is across then then down with the turn occurring along the diagonal.