In A View to Computation, I tried to lay some ground for Computational theory. I also said at the top that Computational theory contributes to my basic skepticism, as a formal (not fluffy) basis for it. In this post I would like to carry that idea a little further.
Long Streams of Digits
Before we get too far, I wanted to give you one more way to see how numbers represent programs, by taking a look at text in the computer world.
Consider a string of digits. As we add more digits, we get a larger number. In the same way, this post is basically a string of digits:
I=73, n=110, SPACE=32 A=65, SPACE=32, V=86…
Those are the first six characters in this post. Now, because we have 3-digit numbers we can represent each character as 3 digits, creating a number looking something like this: 73,110,032,065,032,086. It should be easy to see that if we continue on in this fashion we have a string of digits that 1) represent this post, and 2) is a number (although large) like any other number.
I should stress here, for those of you who are less familiar with this idea, that this IS how your computer sees it. When it sees a 65, it knows that I intended an “A” and shows you a picture that we both recognize as “A”. There is nothing especially “A-ish” about 65 and nothing especially “65-ish” about an A. It’s just a mapping. It happens to work especially good in Roman-character-based languages, but it’s just a standardized way to get a computer, which only stores numbers, to store text.
Of course, the computer doesn’t see a “6″ and a “5″—and it really doesn’t even see the binary equivalent, which is another string of digits (100001). What it sees is high-current or low current circuits in a pattern that matches then ones and zeros in this one: 100001. If we can imagine that a “1″ represents high-current and a “0″ represents low current, that’s as close as we can come in a brief over view. Since the circuits only have two states, we can think of them as binary digits (where the word b(inary)+(dig)its comes from).
Now, I want to skip ahead, because I’m close to boring myself. We only need 8 bits (a byte) to represent characters, because we have more than enough slots for English letters and punctuation with 255. But, unless 255 is the largest number, we aren’t set with numbers. So we just add a couple of bytes together. When we add 4 of them, we can get a number 4,294,967,295 which we’ll call 4 billion, just for ease. But we can only count this high, when we don’t care or expect negatives. Otherwise, 2,147,483,647 is our limit.
Some other applications have seen a need to count in integers higher than 4 billion. So they string 8-bytes together and get a really large number. Thus any number of bytes with their “ones and zeros” can be considered “a number“. Which means that there is a very large number which represents the Microsoft Word program of a specific release. If any other program had the same number, it would be complete with the identification section that had the characters “Microsoft Word” in them–so for all intents and purposes would be Microsoft Word.
Let’s call this number M. A number is just a number unless a machine knows how to decode it.
Let’s journey back in a time machine: before you read my last piece, if I told you 36 is a program, could you decipher what 36 “did”? Unless you’d seen this scheme, or read the book, you probably wouldn’t. The coupling function is a really neat function—but is it implicit in 36 that it is derived by the coupling function? Not really, because 36 can just be the number of people in a certain room.
To think that a number is an encoded program is kind of backwards. We can, through our cleverness, find ways of making numbers stand for letters or programs. But it all is dependent on what the clever human was trying to do. It can only be interpreted through those means. But it’s not much different than a computer’s inability to take a shape that looks like an “A” and understanding it as an “A”.
I wanted to show yet another thing here: In the last post, I showed you a very simple algorithm. I called it Add_Two. Now since we know that the number system is infinite, we also know that there is an Add_Three, Add_Four, and on up forever.
The weird thing is that doesn’t even begin to scratch the surface. I showed an alternate version of Add_Two as my very last step. It looked like this:
Store X + 1 in X
Store X + 1 in X
Store X + 1 in X
Store X - 1 in X
But there can be any number of Add_Two programs, just as long as I end up adding two more than I subtract. What’s even weirder, is that there are an infinite number of Add_Two programs no more than 3 lines long. Remember when I introduced the mapping of instructions to numbers? Remember when I discussed the variable as Vn? Thus all the following can be Add_Two programs for all n > 1.
Store Vn + 1 in Vn
Store V0 + 1 in V0
Store V0 + 1 in V0
And I believe that any reasonably intelligent person can realize that the first (or second or third) argument could as well be “Store Vn - 1 in Vn” as well, or even the null op “Store Vn in Vn” so we don’t run out of Add_Two programs. Plus there are three slots to put the triple-fold infinite number of no-effect statements as well. And we can see how this would go for any integer above 2 as well.
So this made our pioneers wonder, is there someway that we can decipher which algorithms do what? First of all it was decided that some poorly-constructed—but no less possible—algorithms would loop forever. In view of that, they wanted to know if there were there anyway to tell what algorithms looped forever and which ones didn’t, just be analyzing the number? And the answer was “No”. As presented in Alan Turing’s famous Halting problem. If there was a way to tell what programs would loop forever—and on what input—certain, cleverly constructed programs would make that impossible.
