I’ve done a bit of writing about Turing Machines (TMs) and the Halting Problem. For the most part, I’ve only wanted to cover them in at a high-level. However, it’s become clear to me how basic they are to the form of my philosophy. As such, I want to skim a little deeper.

By exposing some of the detail involved in computability theory, can I best give you a window into what is provable by some explicit process and what is not. The theory comments on all processes that rely on an explicit manipulation of symbols.

In essence, TM theory and the implications of Gödel’s Incompleteness make up a good portion of my skepticism.

The Basics

I like the formulation in Davis, Sigal, and Weyuker’s (DSW) Computability, Complexity, and Languages. So we’ll start there. I will keep mainly to that strategy of presentation. Even though it does not deal with the reading and writing cells in Alan Turing’s machines, it still illustrates the concept of an algorithm reduced to a number.

Basically, the DSW book gives us three elementary instructions as:

  1. Store X in X 1
  2. Store X + 1 in X
  3. Store X - 1 in X
  4. If X ≠ 0 GOTO L (Where L is some label)
With this structure they show that the function *Add_Two” can be constructed as follows:

Store X + 1 in X
Store X + 1 in X

In addition, X + Y can be constructed in this fashion

[A] Store X + 1 in X
     Store Y - 1 in Y
     If Y ≠ 0 GOTO A

Thus we are storing X + Y in X.

So how does this become a number, right?

What’s in a Number?

Well DSW introduce a pairing function, which they write as ⟨ x, y ⟩:

⟨ x, y ⟩ ⇒ 2x( 2y + 1 ) - 1

Rendering a unique number for a pair of numbers ( x, y ). For example, given ( x = 2, and y = 3 ), we get 22( 2 * 3 + 1 ) - 1 = 27. And if we are given a number 13, there is only one “decomposition”.

13 + 1 = 14 = 2 * 7 = 21( 2 * 3 + 1 ), so x = 1, and y = 3.

After you divide away all the possible 2’s, all that can be left is an odd number. A fundamental definition of odd numbers in higher mathematics is 2n + 1, meaning that there is always a number n, so that the odd number o = 2n + 1.

You can add to that successive pairings. For example, in the previous computation, we were satisfied with the second number being factored to 3, but 3 can be written as ⟨ 2, 0 ⟩, thus creating the possibilities of denoting ⟨ x, ⟨ y, z ⟩⟩ with a single number 13.

I hope that you’ve followed me this far.

Now, to encode a single instruction, they recommend the following:

  1. Assign a number to each variable, starting from 0.
  2. Assign a number to each label, starting at 1.
  3. Given a to represent a label (a = 0 if no label), and c to represent the variable acted upon, we use b to determine the instruction.
    a. b = 0 if we Store V in V
    b. b = 1 if we Store V + 1 in V
    c. b = 2 if we Store V - 1 in V
    d. b = n if we goto Label # n - 2 if V ≠ 0

Recall the X + Y program 1. Assign 0 to X 1. Assign 1 to Y 1. Assign 1 to Label A

The first line

[A] Store X + 1 in X

translates to ⟨ 1, ⟨ 1, 0 ⟩⟩ = 5

Store Y - 1 in Y

translates to ⟨ 0, ⟨ 2, 1 ⟩⟩ = 22

If Y ≠ 0 GOTO A

translates to ⟨ 0, ⟨ 3, 1 ⟩⟩ = 46

Now, that shows how an instruction becomes a number, perhaps, but we need Gödel (pronounced “girdle”) Numbers in order to properly capture a sequence of instructions.

Prime Time

Remembering that any number has one–and only one–prime factoring, you might see how we use a prime factoring, we can get a number which can only be one program in this system. For example the program above could be given the number: 25 * 322 * 546 then we have a number that, in that encoding can only be the X + Y program.

It’s huge, no doubt. In fact, it is out of the range of most computers to casually compute this number. (OpenOffice.org’s Calc Program gives it as 142,704,537,252,030,000,000,000,000,000,000,000,000,000,000). 546 itself is 1.42 * 1032. The standard computer process of computing 546 loses enough accuracy that we lose which number it is.

The standard computer method is to accept that if you have a number this big, your scale of measurement will probably make it impossible to tell 142,000,000,000,000,000,000,000,000,000,000 from 142,000,000,000,000,000,000,000,000,000,001. The computer uses an approximation of a rational number raised to a power, expecting that in a vast majority of cases it will be “close enough”. But in encoding schemes, anything less than dead-on exact, will give us another prime decomposition, and another “program”.

But we’ll put that aside for a time, and discuss decomposition. For this purpose, I’m going to change the terminology of the variables and labels. Vn indicates the variable to which we assign the number n. Thus V0 is the first variable. Likewise, *L1 refers to the first label.

Given the number 1 it can only be 20 = ⟨ 1, ⟨ 0, 0 ⟩⟩ and thus the “program”

[L1] Store *V0 in V0

2 can only be 21 = ⟨ 0, ⟨ 1, 0 ⟩⟩, or

Store V0 + 1 in V0

3 is 20 * 31, thus ⟨ 0, ⟨ 0, 0 ⟩⟩, ⟨ 1, ⟨ 0, 0 ⟩⟩ …

Store *V<sub>0</sub>* in *V<sub>0</sub>*

[L1] Store V0 in V0

4 is 22 = ⟨ 0, ⟨ 1, 0 ⟩⟩ …

Store V0 + 1 in V0

It’s pretty obvious that the “programs” don’t start to get interesting until we get to larger numbers, so

36 : 2 * 2 * 3 * 3 = 22 * 32.

So it’s instruction 2, followed by instruction 2 or ⟨ 0, ⟨ 1, 0 ⟩⟩ repeated

2 => ⟨ 0, ⟨ 1, 0 ⟩⟩ => Store V0 + 1 in V0

2 => ⟨ 0, ⟨ 1, 0 ⟩⟩ => Store V0 + 1 in V0

So it’s our old friend “Add_Two”

As the last point we can touch on, this is bascially “Add_Two” as well:

Store X + 1 in X
Store X + 1 in X
Store X + 1 in X
Store X - 1 in X

So that’s 22 * 32 * 52 * 76 … or 105,884,100.

  1. Basically a null operation. ↩