December 2014

# Driving Through Houston

` 1The Magazine of Fantasy and Science FictionMar-Apr 2014 2That Hideous StrengthC. S. Lewis 3ThemJon Ronson 4Tower of GlassRobert Silverberg 5Awake in the Night LandsJohn C. Wright 6FrankensteinMary W. Shelley 7Surely You're Joking, Mr. FeynmanRichard P. Feynman 8A History of HeresyDavid Christie-Murray 9The Decline and Fall of IBMRobert X. Cringely 10Mountain Spirits: A Chronicle ...Joseph Earl Dabney 11Luckiest Man: The Life and Death of Lou GehrigJonathan Eig 12Art Theory: A Very Short IntroductionCynthia Freeland 13Almost PerfectW. E. Pete Peterson 14One Bright Star to Guide ThemJohn C. Wright 15FridayRobert Heinlein 16The Falling WomanPat Murphy 17FlatlandEdwin A. Abbott 18The Unpleasant Profession of Jonathan HoagRobert Heinlein 19Farnham's FreeholdRobert Heinlein`Slightly better than 2013, but still nowhere near where I should be.

# The Halting Problem and Human Behavior

The "halting problem" considers whether or not it is possible to write a function that takes as input a function Pn and the inputs to Pn, Pin, and provides as output whether or not Pn will halt.

It is obvious that the function
`(defun P1 ()  "Hello, World!")`
will return the string "Hello, World!" and halt.

It is also obvious that the function
`(defun P2 ()  (P2))`
never halts. Or is it obvious? Depending on how the program is translated, it might eventually run out of stack space and crash. But, for ease of exposition, we'll ignore this kind of detail, and put
P2 in the "won't halt" column.

`(defun P3 (n)  (when (> n 1)    (if (evenp n)      (P3 (/ n 2))      (P3 (+ (* 3 n) 1)))))`
Whether or not, for all N greater than 1, this sequence converges to 1 is an unsolved problem in mathematics (see
The Collatz Conjecture). It's trivial to test the sequence for many values of N. We know that it converges to 1 for N up to 1,000,000,000 (actually, higher, but one billion is a nice number). So part of the test for whether or not P3 halts might be:
`(defun halt? (Pn Pin)  …  (if (and (is-program Pn collatz-function) (<= 1 Pin 1000000000))     t  …)`
But what about values greater than one billion? We can't run a test case because it might not stop and so
halt? would never return.

We can show that a general algorithm to determine whether or not any arbitrary function halts does not exist using an easy proof.

Suppose that
halt? exists. Now create this function:
`(defun snafu ()  (if (halt? snafu nil)      (snafu)))`
If
halt? says that snafu halts, then snafu will loop forever. If halt? says that snafu will loop, snafu will halt. This shows that the function halt? can't exist when knowledge is symmetrical.

As discussed
here, Douglas Hofstadter, in Gödel, Escher, Bach, wrote:

It is an inherent property of intelligence that it can jump out of the task which it is performing, and survey what it is done; it is always looking for, and often finding, patterns. (pg. 37)

Over 400 pages later, he repeats this idea:

This drive to jump out of the system is a pervasive one, and lies behind all progress and art, music, and other human endeavors. It also lies behind such trivial undertakings as the making of radio and television commercials. (pg. 478).

This behavior can be seen in looking at the halting problem. After all, one is tempted to say, "Wait a minute. What if I take the environment in which
halt? is called into account? halt? could say, 'when I'm analyzing a program and I see it trying to use me to change the outcome of my prediction, I'll return that the program will halt, but when I'm running as a part of snafu, I'll return true. That way, when snafu is running, it will then halt and so the analysis will agree with the execution.' We have "jumped out of the system" and made use of information not available to snafu, and solved the problem.

Except that we haven't. The moment we formally extend the definition of
halt? to include the environment, then snafu can make use of it to thwart halt?
`(defun snafu-extended ()  (if (halt? snafu-extended nil 'running)      (snafu-extended)))`
We can say that our brains view
halt? and snafu as two systems that compete against each other: halt? to determine the behavior of snafu and snafu to thwart halt?. If halt? can gain information about snafu, that snafu does not know, then halt? can get the upper hand. But if snafu knows what halt? knows, snafu can get the upper hand. At what point do we say, "this is madness?" and attempt to cooperate with each other?

I am reminded of the words of St. Paul:

Knowledge puffs up, but love builds up. — 1 Cor 8:1b

# When Wright Is Wrong

Author John C. Wright attempts to prove that materialism is false in his blog post The Cosmic Chessboard, or, ONCE MORE FOR OLD TIMES SAKE! In this post, I show how his proof does not work.

In mathematics, a proof is a sequence of steps that follow an agreed upon set of rules that results in an answer. In computer science, this same idea is called an
algorithm. Because Wright attempts to use both the technique of proof by contradiction and the technique of self-reference in his proof, let me begin by showing how these techniques are correctly used.

As an example of a proof by contradiction, let's show that √2 is irrational. By definition, a rational number can be written as the ratio of two integers, a and b, where b is not zero. Let's assume the opposite of what we want to prove, that is, that √2 is rational. That means that:

√2 = a / b (by definition)

Furthermore, let a and b be relatively prime (that is, they have no common divisors).

Then the proof proceeds as follows:
2 = a
2 / b2 (by squaring both sides)
2b
2 = a2 (by multiplying both sides by b2)

Since a
2 is of the form 2n, a2 is an even number. This means that a is an even number (since an odd number times itself results in an odd number). Since a is even, let's rename it as 2c. Then:

√2 = 2c / b (by substitution of equals)
2 = 4c
2 / b2 (by squaring both sides)
2b
2 = 4c2 (by multiplying both sides by b2)
b
2 = 2c2 (by dividing both sides by 2)

This means that b
2 is even and therefore b is even.
But since a and b are both even, they share the common divisor 2, which contradicts the initial condition that they be relatively prime.
Since the initial assumption leads to a contradiction, the initial assumption is wrong. Therefore, there are no integers a and b such that a / b = √2 and so √2 is irrational. QED.

Compare this elegant legal proof with invalid proofs. There are many ways a proof can go wrong. Suppose I want to show that I can drive from point A to point B. This means that I have to stay on the roads, follow all traffic laws, and I have to arrive at point B. If I have to drive the wrong way on a one-way street, while I might have arrived at point B, I didn't follow the rules, so the proof isn't valid. Or suppose the car runs out of gas. Running out of gas isn't considered a valid step (nor would be getting into an accident). Suppose I enter a traffic circle and can't get out and I drive forever in a loop. Since the proof doesn't end, it isn't a valid proof.

Driving in a circle — getting stuck in a loop — can still be a useful technique in proofs. It can be used to show that something is undecidable.

Consider the statement:

This statement is false.

If "this statement is false" is true, then "this statement is false" is false. But if "this statement is false" is false, then it's true. We're stuck in a loop. We say that we cannot decide the truth or falsity of the statement.

This statement can also be expressed as two statements:

The next statement is true.
The previous statement is false.

Again, we end up with an infinite loop so the truth of these two statements is undecidable.

Finally, for completeness, it may be that we simply do not know whether something is true, false, or undecidable.
Goldbach's Conjecture is a famous unsolved problem in math. Perhaps tomorrow someone will figure it out but, today, its status remains unknown.

With this as background, let's consider Wright's approach to his proof.

If mental states are material, then ideas are just arrangements of matter and a particular idea is one arrangement of atoms and another idea is another arrangement of atoms. Without loss of generality, we could use the number 42 as a label to the arrangement of atoms that corresponds to the idea "all glorps are fleems" and the number 6 as the label to the arrangement of atoms that corresponds to the idea "all fleems are blurgs". Whatever a "glorp", "fleem", or "blurg" is, those ideas would also have a particular material state and could be assigned their own numbers. So far so good. The material states that correspond to ideas have been informally mapped to numbers. 42 represents "all glorps are fleems".

But are all gorps fleems? That is, is "all glorps are fleems" a true statement, false statement, undecidable statement, or an unsolved statement, i.e. a statement that is not known to be true, false, or undecidable? If ideas are material states, what distinguishes a "true" material state from a "false" material state?

Wright doesn't say. But we can fix this deficiency. A proof is a statement about a statement. If something is true, then there exists a set of statements, constructed via agreed upon rules, that end with the label "true" (i.e. the computation that these things are the same) or "false" (the computation that these things are not the same). If we can label statements with numbers and have these numbers represent material states, we can likewise label statements about statements. We could, if we wanted, augment the number associated with a statement with the truth value of the statement. And this number would correspond to a particular arrangement of atoms in the universe. So we can number statements, true statements, false statements, etc.

Now, one part of Wright's proof that needs to be stated is that there should be only one mind in the universe. The arrangement of atoms in Wright's head is a small subset of all of the arrangements of atoms in the universe. When Wright thinks "all glorps are fleems," another sentient creature could, at the same time, be thinking "all glorps are not fleems," while yet another creature could be thinking "I want lunch." I would hope that Wright does not think that what happens locally in his head affects the entire universe, although his commentary on his proof may actually suggest he does. In either case, let's update the proof to say that the universe consists solely of the atoms in Wright's brain, a pencil, and the paper on which statements are written. The proof does not suffer if it ends up showing that there is something in his head that does not correspond to an arrangement of atoms.

So what Wright wants to do is to construct a true statement whose arbitrary number does not map to any arrangement of atoms. If he can do that, then there exists something which we acknowledge to be true, but which doesn't depend on atoms for its truth. It really is immaterial.

So let's now consider the heart of Wright's proof. He reasons as follows:

Statement G is “statement R is true.”

And statement R is “There is no number that represents Statement G.”

A paradox arises: Statement G is either false or true. In other words, either it corresponds to the physical conditions of the universe (the entire universe including all human brains within it[1]), or it does not.

If Statement G is false, then it does not correspond to the conditions of the universe, in which case the conditions of the universe are some number other than 07.

But if Statement G is false then statement R is false, and therefore there is a number that represents Statement G, that is, a condition of atoms whose positions on the cosmic chessboard, including those lined up in my brain, which represent Statement G. We have already said this number is 07. Since the universe cannot both be and not be in condition 07, it is impossible that Statement G be false.

But if statement G is true, then the universe corresponds to the condition that obtains when statement R is true. And if Statement R is true then the statement there is no number that represents Statement G is also true. If there is no number that represents Statement G, or my brain thinking Statement G, or even one of any possible arrangements of atoms in the cosmos, then materialism is false, because then something exists aside from what exists in the arrangement of atoms on our cosmic chessboard.

So what's wrong? A couple of things.

First, the assertion "Statement G is either false or true" isn't necessarily true. G could be undecidable or it could be unknown at this time. If you're going to claim something is true, you have to provide the proof (or take it as an axiom). To prove G, one has to prove "statement R is true". But watch what happens when we start substituting equal things:

G=“statement R is true.”
R=“There is no number that represents Statement G.”
Substituting for G gives: R=“There is no number that represents statement R is true.”
Substituting for R gives: “There is no number that represents There is no number that represents statement R is true is true.”

Trying to express R results in an infinite expansion. Using this technique, G is undecideable. Therefore, the claim that "Statement G is either false or true" is false. And the proof fails.

But we can approach the proof another way. Wright has a strange notion of "truth". He seems to think that "true" statements correspond to physical conditions in the universe (which is true) but that false statements do not. But a false statement is just as much an arrangement of atoms as a true statement is an arrangement of atoms. Clearly this is so. "
There are four lights" is a true statement and is an arrangement of atoms of ink on paper or photons emitted from a display. "There are five lights" is a false statement but it, too, is an arrangement of atoms.

Assigning arbitrary numbers to statements only serves to confuse the issue, so let's get rid of the numbers. And let's do this by showing that numbers aren't needed. We can certainly arbitrarily assign numbers to statements, as Wright did. But we can also encode the statements as if they were polynomials. Count the numbers in the character set and that will be the base. Map the first character in the alphabet to 0, the second to 1 and, finally, the last character to base - 1. Then treat each statement as if the letters were coefficients of a polynomial and evaluate it via
Horner's method. With this method, each statement can be converted to a number and can be converted back to the original statement. Since numbers and statements are equivalent, we can get rid of the numbers and just use the statements directly.

Then the proof becomes:

Statement G is “statement R is true.”
Statement R is “There is no statement that represents Statement G.”

Statement R is then clearly false, so statement G is false, and the proof falls apart.

Two different ways of looking at the proof give the same result that the proof is wrong.

QED.

[1] The arrangement of atoms in his head affects the entire universe? That some people believe this is not unheard of, as the quote from Gene Wolfe at the end of
this post shows.