21st-century Christian Philosopher

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 ¹
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 ⟩ ⇒ 2^x( 2y + 1 ) – 1

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

13 + 1 = 14 = 2 * 7 = 2¹( 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: 2⁵ * 3²² * 5⁴⁶ 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). 5⁴⁶ itself is 1.42 * 10³². The standard computer process of computing 5⁴⁶ 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. V_n indicates the variable to which we assign the number n. Thus V₀ is the first variable. Likewise, *L₁ refers to the first label.

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

[L₁] Store *V₀ in V₀

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

Store V₀ + 1 in V₀

3 is 2⁰ * 3¹, thus ⟨ 0, ⟨ 0, 0 ⟩⟩, ⟨ 1, ⟨ 0, 0 ⟩⟩ …

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

[L₁] Store V₀ in V₀

4 is 2² = ⟨ 0, ⟨ 1, 0 ⟩⟩ …

Store V₀ + 1 in V₀

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 = 2² * 3².

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

2 => ⟨ 0, ⟨ 1, 0 ⟩⟩ => Store V₀ + 1 in V₀

2 => ⟨ 0, ⟨ 1, 0 ⟩⟩ => Store V₀ + 1 in V₀

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 2² * 3² * 5² * 7⁶ … or 105,884,100.

Here’s an interesting tidbit I ran across on the web.

Daniel Dennet says:

“If we don’t understand religion, we’re going to miss our chance to improve the world in the 21st century.” http://www.ted.com/index.php/talks/view/id/94

It’s funny because this is the bio page off of a tape of the talk that Dennett gave at the TED conference (Technology, Entertainment, Design), where he invokes “Orgel’s Second Rule” : “Evolution is cleverer than you are.”

He believes that religion came about through evolution. Apparently, nobody had to understand religion to get us this far. Nobody had to understand it to “create” it, make it “beautiful” (as he relents). But all of a sudden, we have to understand it to do something clever.

Keep in mind that Dennet invests in this “rule”, because he says:

If you understand Orgel’s Second Rule, then you understand why Intelligent Design is basically a hoax.

See, ID is a hoax based on Orgel’s second rule. You can’t understand the real implications of something based on just a precept. A more rational man would say “So you understand why if Orgel’s Second Rule is true, ID is a hoax” if he meant that. No, he means by understanding Orgel, we understand the state of ID. Orgel’s Second Rule (despite being a pretty flimsy ad hoc rule) is a fact in that context.

So Evolution is cleverer than we are. But somehow, not cleverer than Dennett because he thinks he sees what reins have to be siezed to make the evolutionary product of religion run other than its course.

Or do we just have to understand it because we’re going to be graded on it at the end of the 21st century?

I can imagine Evolution showing up and critiquing Dennett about the “flaw” he sees about the state of things.

Who has put wisdom in the innermost being Or given understanding to the mind? Do you give the horse his might? Do you clothe his neck with a mane? Do you make him leap like the locust? His majestic snorting is terrible Is it by your understanding that the hawk soars, Stretching his wings toward the south? Is it at your command that the eagle mounts up And makes his nest on high? Will the faultfinder contend with [Evolution]? Let him who reproves [Evolution] answer it.

You see, I think that if evolution is all that is going on, the reverence for “the Creator’s” being more clever than we are is more faithfully carried out by the worshipper than the smartypants, who thinks its time to jump up and grab the reins now. God’s wisdom or Evolution’s cleverness be damned. We can no more turn Evolution into God than we can turn God into Evolution. It’s out of our hands, the yielding to the greater wisdom of “the plan” is the portion of what remains as a practical matter.

It’s not just something compartmentalized into the slapping-down-opponents mode.

What’s untouched is the question: HOW is Evolution cleverer than we are?

Well, I get tired of explaining the logical implications of their worldview to them, but here goes:

What works survives and theories about what might have worked, what should have worked are discarded. Natural selection is not about deciding what species gets The Best Manifest Idea award, it TESTS every variation so that the animals adapted to survive. Eohippus did not die out because the horses thought they saw a flaw in their logic, or didn’t like what they were doing, or thought that they had a fundamental flaw which would jeopardize the entire world. It’s not about getting ideas into a our overtaxed survival-brains of how we’re going to save the species from extinction. It’s about unproductive patterns adapting or dying.

It’s not about any seeing process coming up with a solution at all, but (as we are consistently told) a blind one grinding away the chaff.

But Dennett, I guess, thinks he has a better idea.