Imagine you have a multiple choice test with 20 questions. Each question can be answered by choosing one of four choices. A compete answer to the test consists of a string of 20 characters, each of which is chosen from the set {A, B, C, D}. The solution to the test is an answer string where every answer is correct.

A valid, but not necessarily correct, answer string would look like this:

ABDCBDABDBCABDCCBABD

How many possible answer strings are there? Well, each position in the string can take on 4 different values, and there are 20 of them, so there are 4^20 = 1,099,511,627,776 possible ways to answer the test. That’s “just” over 1 trillion (over by 99 billion, that is). To give you a sense of perspective, that’s about as many seconds as there are in 35,000 years. Yeah, that’s a lot.

Imagine you have access to an oracle to whom you can submit a solution string. He will look at your string, and tell you how many answers you got right, but he wont tell you which ones are right, just the raw score. Based on this information, how many answer strings do you think you would have to look at to find the right answer?

If you are just pulling random strings out of thin air, its entirely possible to choose the right one instantly. But that’s not likely to happen. When choosing a string at random, each string has a 1 in 1,099,511,627,776 chance of being chosen. If there is only one correct solution, you have a 1 in 1,099,511,627,776 chance of choosing the correct string on the first go, a 1 in 1,099,511,627,775 chance on the second (since you’ve already eliminated one string), and so on. You would have to examine billions of strings before your chance of choosing the correct string at random starts to even approach the chance that you will win the lottery. You would have to examine 99% of of the strings before the chance that a string picked at random from the remaining set is the correct one approach “normal” odds of 1 in a million.

“What does this have to do with computation?” you may ask. If, instead of choosing strings at random, we used a genetic algorithm, we can drastically reduce the number of strings that have to be checked to find the correct solution.

Feel free to skip this section if you don’t want the gory details.

Here is how I created a genetic algorithm to find the solution to a given test. I created an initial random population of 20,000 random strings. And by “random", I mean just that: each string was chosen by randomly picking which letter would go at which spot in the string. Each of these strings was checked against the correct solution string for the number of answers it got right. This number became the fitness value of the string. The 1,000 most highly fit strings were carried over into the next generation unchanged. The remaining spots in the population were filled via two methods: mutation, and crossover.

For any one mutation, there are two possibilities. A string is selected from the population, on the basis of its fitness, i.e. more fit strings have a higher chance of being chosen than less fit strings, but every string has a chance to be chosen. The first possibility is that a random point in the string is chosen, and the letter at that point is randomly changed to one of the four possibilities. This gives a 1 in 4 chance that the mutation wouldn’t change anything at all. The second possibility is that a range in the string is selected and reversed. This also has the possibility of leaving the string intact, if the randomly selected range is only one character long. Either way, the resulting string was added to the new population.

For crossover, two strings are chosen from the population, and again the chance of being selected is weighted by fitness. A random point in the strings is chosen at which to preform crossover. The two strings are split at these points, and two new strings generated by combining the ends of the parts.

The fitness of the new population of strings is evaluated, and the process repeated until a correct solution was found.

Here are the results of the experiment.

What is the smallest number of generations this method took to find the correct string? When I ran the experiment, the shortest time was 12 generations. That means examining 12,000 strings, out of a possible 1,099,511,627,776, or, just 0.0000000001% (1.09139364 x 10^-9 to be exact) of the total possible strings. Obviously, this is more than slightly better than chance. The most generations it took was 22, a total of 22,000 strings. The average number of generations was 16. In the starting populations, the average fitness was generally 8, with 13 being the highest individual fitness I ever saw.

It is interesting to note that the operations performed on the strings are not guaranteed to produce a more fit string. Very often the change makes the resulting string less fit than its parents. But in general, the average fitness of the whole population goes up, even though most mutations are not beneficial. This is because when a beneficial mutation occurs, it tends to rapidly spread through the population. The new, more fit string has a better chance of mating than the other strings. This string’s offspring tend to inherit its higher fitness, so they have a better chance of reproducing than the offspring of other strings. In short order, all of the strings will be descended from the successful mutated string.

The take home point is that even without any knowledge of why a particular string fares better than another, the simple act of making random changes to fit strings gives rise to more fit strings, and converges on the most fit string in a surprisingly short time.

Now, this is not to say that evolution in the natural world works exactly as I have implemented it here. But it does serve to show that IF you have a means of varying the organisms in an environment and ALSO some way of making some of them survive and others die off that’s related to the traits possessed by individuals, THEN those traits which cause the individuals to survive will spread throughout the population.

Some people argue that evolution cannot give rise to new information, as culling members of an existing population serves to reduce genetic diversity. While it is true that culling members reduces genetic diversity, and by extension (in some sense) information, their claim that this rules out evolution is wrong. It’s the mutation that introduces new information into the gene pool. Natural selection serves to cull out information that is detrimental to survival.

Some people accept “micro” evolution, but not “macro” evolution. I’ve dealt with this in a previous post, so I’ll just point out here that, if two populations of the same species end up in different areas, where different traits are required for survival, then evolution dictates that they diverge into separate species. This is caused by two factors: the selection criteria for survival will probably be different in the different areas, and geographic separation means that any new traits introduced by mutation will not spread to the other population.

To summarize, in order for evolution to occur, the ONLY things needed are 1. variation in a population of individuals and 2. some individuals more fit to their environment than others. If these two properties are present, evolution WILL happen. Not just may, or might, but WILL. If you admit that species change over time, no matter how minor the changes, and that members of a species survive or die depending on individual traits, you must accept that evolution takes place. Furthermore, you must accept that speciation will happen when populations are split into different geographic areas with different environments. To do otherwise should result in your head exploding from the cognitive dissonance of holding two contradictory ideas at the same time.

One of the comments she reproduces in her post says:

Society has not conditioned us, evolution has. Men are attracted to women that represent the best chance of bearing their young and caring for them. This means young and physically fit.... This is not opinion, it is fact.

The idiocy and wrongness of this comment astound me. Evolution actually selected for chunky woman. Who do you think took better care of an infant: a woman who had the fat reserves to produce a continuous supply of milk even if she wasn’t eating regularly herself, or a woman who had no fat reserves at all, and wasn’t able to produce milk on days when the hunters didn’t bring home any food? Furthermore, there is a reason woman’s hips, and hence their gait, differ from men’s. Evolution selected for wide hips that allowed for easy birth. Those women who died in childbirth, and took their babies with them, obviously didn’t get to contribute to the gene pool. In fact, its only because of modern science that this selection effect doesn’t continue. The human infants head is rather large compared to the birth canal. Until very recently, as in the last 100 years, a woman was more likely to die in child birth than any other circumstance.

I’m sure the person who posted this comment imagined in his head that a physically fit woman, when attacked, could grab her infant and run with it, leaving a fatter woman behind to get eaten. But its been a long time since humans have been a prey animal for any large predator, and that has been the case for thousands of years. When you exist in the context of a hunter gatherer society, being “physically fit” is no longer a pre-requisite for survival. On the other hand, easy child birth is damn useful, as is being able to survive lean times on fat reserves.

The other point I want to touch on is exemplified by this comment:

Are you really that naive? seriously. You KNOW what guys want, look around! They want that hot, sexy, body, a gal to make them look good too. MOST men do not prefer an overweight woman.

Its that last clause, that “MOST men do not prefer an overweight woman.” Well, duh. Most men don’t. And most men don’t prefer an underweight woman, for example Victoria Beckham.

Its like this. Overweight and underweight implicitly refer to an average weight that you are over/under in relation to. If MOST men preferred overweight woman, the average weight of woman in the population would shift towards the heavier side (over a few generations), and they would cease to be over weight. They would be the new average weight. Similarly, if most men preferred underweight woman, the average weight would shift towards the thinner side (again, over generations), and they would cease to be underweight. Obviously, this is a process that happens over generations (as I said), and it is possible that at this moment in time, we are shifting to a thinner standard. But only time will tell if that’s the case, and if so, we are moving away from a historical preference that held sway as recently as 100 years ago.

Here is an experiment that could be carried out. Take the weight of every woman in a region, and find the average. Take a photo of every woman in the same region, and ask the men of the region to rate the attractiveness of each. Find the average attractiveness of each woman. How do you think the average weight and the average attractiveness will be related to each other? I contend that the closer to the average weight a woman is, the higher her averaged attractiveness. Any other outcome would be surprising, and in need of an explanation. The reason they should closely correlate is that, contrary to some peoples opinion, weight is heavily influenced by genetics. As such, the most attractive weight has an evolutionary advantage in terms of reproduction, hence it should be represented in the population at a higher rate than other weights.

Now, obviously this is vastly simplified, as other factors do play into the genetics. For example, having blue eyes are a recessive trait. If one parent has brown eyes, and one blue, chances are that the offspring will have brown eyes. Something similar may happen with weight, i.e. the “thin” gene is dominate, and the “fat” gene is recessive. But the point remains: The average person in a society should be averagely attractive. Hence, the average weight should be the most commonly considered to be an attractive weight.

The fact is, sexual selection is a stupidly powerful force, and sometimes selects for things that most certainly DO NOT help the individual survive. Sexual selection only affects your chance to reproduce. Does anyone really think that the peacocks giant ass-feathers make it harder for its predators to find the males of the species? And there is a damn good reason the females don’t have them. The males just have to live long enough to have sex. The females have to live long enough to rear young. If you think of this in relation to humans… well,sexually selecting for females that are prone to die in childbirth seems like a recipe for disaster. Maybe modern medicine can make up for it. I don’t know.

I do know, however, that if only thin people reproduced, which would be the case if “most” men wanted a mate that looked like Victoria Beckham and wouldn’t settle for anything less, then most woman would look like her. If most woman wanted an Adonis and wouldn’t settle for anything less… well, then that’s what most men would look like. But that’s not what we see when we look at the world, hence we can infer that the “hypotheses” in the above comment is wrong.

None of this is to say that I think evolutionary psychology is a real scientific field. But people who argue as the commenter above did fail by their own standards.

Now this post has largely talked about some sort of “average” attractiveness. But the fact is, this is a crock of shit, and I’ve only used it to illustrate that claims like the above just don’t make sense. Attractiveness is not a hierarchy, with a well ordering. It exists on a horizontal spectrum, and we clump at various places along the spectrum, just like we do with tomato sauce. If everybody was attracted to the same thing, we should expect to find porn to be pretty homogeneous. This is most certainly not the case, as can be verified if you are brave enough to google for “free porn” and survey the results.

The laws of science are a harsh mistress, those people have been looking for the perfect Pepsi, they are wrong, and should be looking for the perfect Pepsis.

As explained in this article (Warning: graphic picture), a man was mauled to death by two tigers when he climbed over a protective barrier, and stuck his arm through the bars of the cage to take a close up picture with his cell phone. To paraphrase a comment from bash.org, they should put something in the cage to deter people from getting near it. Perhaps a fierce animal that would attack anyone that got too close?

A sad point to this story is that his wife and kid saw the whole thing. But one just had to wonder… What the hell did he think was going to happen?!? Did he expect to just snap a few pictures while the tigers sat there? Maybe that they would do a little dance for him? I wish this were an isolated incident, but it is not.

Binky the polar bear was kept at the Anchorage zoo in Alaska, and become famous for mauling tourists. One incident involved an Australian women climbing over two fences in order to get to the bars of the cage to take a close up shot. Binky stuck his head through the bars of the cage and grabbed her leg. More recently, different woman, different zoo, different polar bear, same result. I am unable to find a more detailed version of the news story at the moment, but if i recall correctly the women made statements like “I didn’t think it would move so fast,” and “I didn’t think they would keep a dangerous animal in a zoo.”

Its that last statement in particular that leaves me scratching my head.

Have you ever walked down the street and encountered someone with a dog who assures you that “Snugly poo doesn’t bite!"? This is a dangerous attitude for an animal owner to have. What it seems to boil down to is that a lot of people think that there are two types of dogs: dogs that bite, and dogs that don’t. You just gotta make sure that you got the non-biting kind, and everything will be good. But if he EVER bites, dump his ass as quick as you can, cause he is crazy and vicious and unpredictable.

The simple fact of the matter is that EVERY dog is capable of biting, and in fact WILL bite, given the proper circumstances. Deluding yourself into thinking that your dog wouldn’t bite you, no matter what you do to it, is lulling yourself into a false and dangerous sense of security.

Viki Hearne, in one of her numerous books, offers the interesting anecdote that the number of accidents involving animals (domestic and other wise) went up immediately after the rise of the automobile. She speculates that, pre-automobile, horses where the primary mode of transportation, and hence were everywhere. You couldn’t help but get to know how to behave around a horse, and to know that even the most mild horse will bite and kick if provoked. These days, it is entirely possible to go through life with essentially no interaction with an animal. This has left us in a position where most people in the urban areas of the west simply do not know how act around animals. For example, they do stupid things like stick there arms into animal enclosures at the zoo.

But it has implications for the animals as well. A lot of people honestly seem to believe that any dog that bites must be killed, regardless of circumstances. A few years ago, I saw a news article about several teenage boys who were attacked by a dog. The full story is that the dog was in a fenced in yard. The kids started throwing rocks at it, and hit it several times. It jumped the fence and bit several of them. The dog was put down as being dangerous and vicious.

I cannot conceive of what kind of twisted logic leads you to the conclusion that a dog that was provoked into attacking in self defense is vicious or dangerous. Doesn’t it defeat the point of having a guard dog, if the dog is too chicken shit to defend itself? Doesn’t it also defeat the point of having a guard dog if the dog isn’t allowed to, you know… guard?

An even more bizarre example of animal ignorance occurred a little over a year ago. I cannot find a link to the article, but what happened is that a park ranger had to stop a women who was posing her 4 year old son in front of a wild grizzly bear so she could take a cute picture. The whole idea of it just leaves me speechless, so I don’t even know what to say about it.

Unfortunately, the victims of peoples animal ignorance aren’t always themselves. This article, for example, is about a 4 year old boy who was killed by several rottweilers. The father of the boy left him alone while he and several friends went into the basement to do electrical work. There was one dog in the house with the boy, and 2 more outside. The dogs belonged to a friend staying with them. It seems the toddler went out side looking for his farther, and ended up being killed by the dogs.

Several things immediately spring to mind here. First of all, who the hell leaves a 4 year old kid alone with one big dog, let alone three? For that matter, who leaves a 4 year old kid alone at all? Why were the dogs loose and unsupervised when a kid was around? The inquest the article mentions is going to “make recommendations about how to prevent a similar tragedy.” Here’s one: realize that dogs of any size and breed are inherently dangerous animals. Don’t leave them loose and unsupervised.

Needless to say, the dogs were destroyed. But why? Essentially, for being dogs. Untrained, unsupervised, poorly owned dogs with bad owners, but essentially just being dogs.

The bottom line to this that animals are dangerous for a very simple reason: they have brains. They can decide to do something. They can offer novel behavior in response to stimulus. The dog that you’ve smacked every day for years can decide he is sick of it, and fight back.

Guns are dangerous too, but in a very different way. To quote Portal, the Weighted Companion Cube will never try to harm you. Neither will your gun. But the only reason we can make these claims is because the damn things are inanimate, and hence cannot “try” to do anything. If you want something soft and cuddly and totally safe, get a stuffed animal and leave the real ones alone. But if you get a real animal, remember: it has teeth, claws, and a brain. If it decides it wants to hurt you, it can and will, and anyone who tells you that it would never do such a thing is either lying or profoundly ignorant.

You hear about mauling in regards to dogs more often than any other animal, but that just a result of the fact that most of us have a much, much higher chance of interacting with dogs than any other animal. The maulings at the zoo show that this isn’t a problem with a particular animal, or a particular species. Its a conceptual problem people have in regard to animals in general.

Unfortunetly, the conceptual problems aren’t limited only to underestimating the safety of some animals. Certain breeds of dogs are portrayed as extremly dangerous. But when you sit down and crunch the numbers, you find out that dogs bite, but balloons and slippers are more dangerous.

UPDATE

Since I originally wrote this article, I saw a documentary on the Discovery Channel about Timothy Treadwell called “Grizzly Man.” The shear stupidity of this man astounds me, and I feel that basically anything and everything I want to convey in this article can be gleaned from watching this documentary.

Timothy spent 13 seasons living among the bears in Katmai National Park in Alaska (USA). At the end of his last season, he and his girlfriend were killed and eaten by a bear. Watching the documentary, which is made up of footage he shot himself interspersed with interviews with friends and family, you see him repeatably getting dangerously close to wild bears. In addition to the close proximity, he clearly has a dangerously anthropomorphic conception of the animals behaviors.

Listing here all the dangerously stupid things he did would drastically increase the size of this post, so I will leave it to interested parties to watch it. Suffice it to say that in Timothy Treadwell, we have a micosom of the fundamental misconceptions many people in our society have in regard to animals.

Over the last few weeks, a lot of articles have been submitted to reddit with titles like “Stop posting Ron Paul stories! We don’t care!” or “The top 10 articles are on Ron Paul! Lay off it!". Aside from the obvious stupidity of posting something that says you-all (damn the English lack of a 2nd person plural!) don’t care about topic X when topic X is consistently at the top of the hot page, it seems to me that anyone who would post such an article has fundamentally misunderstood what the hell is going on with Reddit, Digg and all the other social news sites.

The sites are not there to provide you with all and only stories you will find interesting. By their very definitions, the “hot” page and the “top stories” page are going to be filled with the trash that appeals to greatest number of people using the site. In other words, it will be full of what ever appeals to the least common denominator. The more you dislike the contents of the front page, the farther from the “average” user you are. As an example, I’ve posted several of my posts to this blog on reddit. Here are some of the stats:

Up Down Title
1 0 The Game Of Go
3 1 The Turing Test and Philosophical Zombies
6 1 Micro/Macro Evolution and the Paradox of the Heap

Obviously, it would’ve been great for them to reach the hot page so I could bask in the glory. But these results are pretty much exactly what I expected. I understand that the subject matter of this blog, and by extension my interests, are not all that universally appealing. If one of these posts was an “I can has cheezburger” picture, I’m sure it would’ve done a whole hell of a lot better than any dry exposition of an obscure philosophical position. That’s just how this works. No one feels strongly about these subjects either way, so they went nowhere.

In the early prehistory of reddit, I loved it. It was populated by tech minded people and had many interesting articles on programming and science. But as it became more popular, the composition of the audience changed, and the content of the articles submitted and up-voted changed with it. Several months ago, the top stories page were clogged with links to stupid pictures and funny news stories. Now they are clogged with articles dueling about how great/horrid Ron Paul is. Frankly, I think this sucks. But I’m not in the least surprised and have no intention of posting a story to reddit to bemoan this fact, or turn this post into bitching about it.

Here’s a tip for you: If you want a list of only articles you will find amusing and interesting, go to reader.google.com and sign up for a bunch of RSS feeds from blogs you like. It’s that simple. The social news sites will never be anything other than collections of stupid crap that appeals to the most people, and expecting it to be otherwise is fundamentally naive. For them to be anything but that would require

1. A stipulation that this site is only for articles about X
2. A dedicated user base that will down vote into oblivion anything that ISN’T about X
3. Editors that deliberately delete articles not about X

But notice, now, that to do this we must abandon several of the features that make reddit and digg popular. By limiting yourself to a particular subject, your user base will be limited, and hence the number of sources for potential articles will be smaller. By depending on users to downvote out stories that don’t meet the criteria, you are expecting the users to AGREE on how to apply the criteria. By having editors sort through the submissions, you introduce a delay before articles are visible (unless you wish to do ex-post-facto deletions), and also depend on your editors to apply the criteria correctly. Looming in the background in this scenario, if you choose to fore-go editors, is the potential for a cadre of rogue users to start submitting and up-voting off-topic stories that essentially turn the site into reddit/digg.

Now, I can understand the up-vote brigade. If you feel passionately about something, you want to spread the word (this is the biggest problem I have with evangelical religions). But what the hell are the down-vote brigades doing? The only possible explanation that I can come up with is that they are essentially trying to exert tyrannical control over the hot page of reddit. I understand being sick of seeing things with X in the title, but when you start deliberately burying anything on the subject, you start skirting dangerously close to appointing yourself to the position of public censor.

Yes, I am arguing that the the up-vote brigade and the down-vote brigade are not symmetrical positions and that one is definitely more morally questionable than the other. In fact, this very position is embedded in the notion of free speech. You are free to NOT click on the links with Ron Paul in the title. But to deny those people who do want to see those stories the opportunity to do so… Well. Lets just say its a bad idea in real life, and I fail to see why it’s not a bad idea online.

So, to sum up:

1. On any social new site, the most popular stories will be the ones that appeal to the most people
2. It’s stupid to complain that there are too many popular stories about X
3. Arbitrarily down-voting anything with X in the title skirts close to a morally repugnant position
4. If you want custom-tailored content, roll your own with RSS

But whether or not time travel is possible is still an open debate among physicists. In this post I want to discuss some of the paradoxes that would seem to result if time travel is possible, as well as an interesting algorithm for solving NP problems using a time machine.

Some reject the possibility of time travel out of hand. Their arguments rest on the fact that time travel seems to engender several paradoxes.

The most well known paradox is referred to as the “Grandfather Paradox,” which involves an individual who travels back in time and changes history in such a way that negates his own existence, from which it follows that he could never have existed to change history in the first place. It is called the grandfather paradox because it usualy involves our intrepid traveler (whom we shall from here on call Fred) killing his own grandfather before his father is born, thus breaking the sequence of events that lead to Fred’s birth, which is necessary for him to go back in time to kill his ancestor.

While on the face of it, this paradox might seem to indicate that time travel is impossible, it only does so if one is willing to postulate that the time traveller has a sort of radical free will whilst in the “past", i.e. that nothing conspires to prevent Fred from doing his deed. Of course, the only way to leverage this claim is to suppose that for some reason Fred, while having every intention and means to kill his grandfather, fails to do so. Perhaps he is run over by a car before he can do so. Or perhaps the rifle he is using jams when the trigger is pulled. The obvious problem with this line of reasoning is that we seem to be postulating a number of metaphysical assumptions that seem dubious at best.

Interestingly enough, a scientist calculated the probability that a mass sent back in time could engender a paradoxical situation. He found that though there are many trajectories a mass could take, the probability that the mass would take a trajectory that resulted in a paradox was zero. This led him to postulate what is now known as the Novikov Self-consistency Principle. If correct, this would put the grandfather paradox argument to rest for good, but leave us with the even thornier problem of a reality that seems to “know” that certain events must not be allowed to happen.

Another paradox is called the Ontological Paradox. This paradox revolves around the creation of objects and information. Consider this example: I go to the book store and buy the complete works of Shakespeare. I travel back in time to find a young Shakespeare who has not yet written any plays. I give him the complete works, along with a detailed chronology telling him when to “produce” each work. The question then becomes, who wrote Shakespeare’s plays?

The information in the plays has become a closed causal loop. They had to have been preformed in the past to be written down and known in the future. But they had to be written down in the future in order to be transmitted to the past. The information contained in the plays causes itself to exist, without having been created.

An even stranger version of this paradox involves the time machine itself. Let us say I resolve to create a time machine. I spend months working on it but find some problems insurmountable. One day, an older gentleman appears on my door. He gives me detail schematics for a time machine, as well as a large sum of money to finance its development. I build the machine according to his plans, and using it I get rich playing the stock market. Many years in the future, I travel back in time to visit my younger self, to whom I give the plans for the time machine, as well as the money to build it.

Once again, in this story we have information that has a confused causal history, which makes a loop in time with no discernible start point.

The ability to transmit information into the past would have serious ramifications for computer science and mathematics. With this ability, it is trivial to develop an algorithm that instantly provides the answer to any NP question. Here is how the algorithm works.

For 1 minute, listen for an answer transmitted from the future.
If an answer is received, check to see if it is correct.
If the answer is correct, transmit it to the past, output the answer and halt.
If the answer is incorrect, choose a random answer, and transmit it back in time.

The way this algorithm is structured, the computer (from our point of view) must immediately produce a correct answer, with essentially no computational effort.

It would also be possible to prove that any given proposition has or lacks a finite length proof. Let us suppose we wish to test if some proposition has a non-infinite proof. Proof checking algorithms exist, and are reasonably efficient. So imagine this algorithm:

Wait for a proof from the future.
If no proof is received, generate a random proof and transmit it to the past.
If a proof is received, check to see if the proof has already been verified.
If the proof was verified, transmit it the past, output it and halt.
If the proof was not verified, check the proof for validity.
If the proof is a valid proof of the proposition, transmit the proof to the past with the validity bit set.
If the proof is not a valid proof of the proposition, generate a new random proof and transmit to the past.

There are practical limits to the length of a proof. These limits are fixed by the amount of time it takes to verify the proof, and how large a proof a human can hold in his head. Surely there are proofs out that that are so long as to be basically incomprehensible. We have proof checking algorithms, but if it takes them 1 trillion years to verify a proof, they are not much use to us. A time machine would throw these limits out the window, by making time a reusable commodity. The machine would take 1 trillion years to verify the proof, but we wouldn’t have to wait those years. From our point of view, the correct answer pops out of the machine as soon as we turn it on.

These two algorithms are examples of Time Loop Logic, or Temporal Computing. Note that in both these algorithms, the potential for a paradox exists. If the answer we receive from the future is not the correct one, we transmit a different answer to the past. This is a paradox. But if the self consistency principal is correct, paradoxes cannot happen. So the initial answer we receive from the future must be the correct one.

Perhaps the thorniest problem with those who believe in the possibility of time travel is an analogue of Fermis’ paradox: If there are time travelers, where are they?

Surely in the course of history there must be events that many people would desire to see. The birth of Jesus (or any other major religious figure) for example. And yet we do not have accounts of millions of strangers flooding Bethlehem. This fact would seem to indicate that time travel is never discovered. Or, at least, if it is discovered, it is so far in the future that people no longer care about this time period.

To seek proof of the existence of time travelers, in May of 2005, a student organization at MIT hosted a time travelers convention. Their intention was to broadcast a particular space time location at which time travelers can show up and make themselves known. As mentioned in the article, “The space-time coordinates continue to be publicized prominently and indefinitely, so that future time travelers will be aware and have the opportunity to have attended.” Setting aside the amusement factor of the confusing tense of that sentence, the idea itself seems sound.

Of course, there are people who claim to be time travelers, such as John Titor. Unfortunately, their claims have never stood up to verification. Perhaps if time travelers do exist, they follow a temporal analogue of the environmentalists “Take only pictures, leave only footprints.” After all, it would not be any fun if your vacation to the distant past altered the future you came from from an idyllic paradise to a hell on earth, would it?

In closing, I would like to point out that an anthropic explanation of why time travel is impossible also exists. This line of reasoning states that any universe in which history is mutable is inherently unstable. If we could go back and tinker with the past, eventually one of two situations would occur: Either a history would result in which humans never developed, or a history results where humans do develop but never discover time travel. The first situation is stable because, obviously, we wouldn’t exist to do the tinkering. The second is stable because we would lack the means to tinker.

The second situation has troubling metaphysical implications, however. It postulates that by a simple historical accident, we never discover a technology that we could in fact discover.

If you are interested in pursuing these further, I would suggest obtaining a copy of The Philosophy Of Time, and in particular the chapter titled “The Paradoxes of Time Travel” by David Lewis.

If anyone from the future is reading this, feel free to contact me with verifiable information to back up your claim of being from the future. I do not require much. The winning lottery numbers for the next several years would do nicely. Or perhaps sport scores, or horse race results….

Go is a strategy game from Asia. It is played on a 19 x 19 grid. Two players, one playing black the other white, take turns placing stones on one of the initially empty 361 intersections of the grid. The object of the game is to surround more territory then your opponent. Territory is considered surrounded by a player if there is no sequence of adjacent points in a region which connects to an opponent’s stones. Once placed on the board, stones do not move, and are only removed if all 4 adjacent intersections are occupied by enemy stones. Empty points around a stone are called its liberties, and two adjacent stones of the same color share their liberties. With the addition of a rule, called the Ko rule, which forbids the repetition of a previous board state, these are the only rules to the game.

Playing Go has a quite different feel to it than playing chess. Rather than starting with all pieces at set positions on the board, and then maneuvering them around, the initial board is totally empty, offering black (who goes first) a choice of 361 initial moves. Taking symmetry and transposition into account, he has a total of 90 55 unique moves to choose from. I do not mean to disparage chess; indeed, when I was young I played a lot of chess. But every since I began to seriously play go, I find my taste for chess has waned almost to naught. These days chess feels to me to be confined and lacking in elegance.

A lot of the strategy that happens in go, and one of the things the intrigues me about the game, depends on emergent phenomena that are a direct result of the very simple rules of the game. For example, certain shapes of stones are unconditionally alive. These shapes surround two separate empty positions of one space each. Since either position would be a suicide move for the opponent, the opponent can never take all the liberties of the group. Hence it cannot be killed. Each stone is identical, and so the value of a stone is entirely dependent on the pattern it makes with the rest of the stones on the board.

Conway’s Game of Life was directly inspired by Go. In fact, lacking a computer to run it on, Conway experimented with his “game” using a Go board and its stones. If you are familiar with life, you know about all the strange structures that rise out of its very simple rules. The same thing happens in Go. Certain formations of stones are very strong, others are very weak. Sometimes the difference between a formation being weak or strong depends on who gets to play next. Sometimes you play on one section of the board to a point where one player has an obviously dominating position, and so the play moves elsewhere. But then, as the influence of distant battles propagates across the board, suddenly that dominating position wobbles and falls.

To new comers watching a game, it can seem quite random, with each player plunking stones down seemingly at random, and occasionally taking groups off the board. But to an experienced player, each move has significance. Two moves that might appear practically identical, i.e. the choice between two adjacent points on the board, can and often do have drastically different purposes and significance. For example, consider the first move either player makes. Almost everyone plays the first move in the corner. This is to secure some easy territory, as it is generally the case that a stone behind the 5,5 point can be built into a base. Most people play either on the 3,3 point or the 4,4 point. The 3,3, point is considered an edge facing position, securing the corner quite firmly, but lacking in the ability to project strength towards the center of the board. The 4,4 point, on the other hand, only weakly controls the corner, and is considered a canter facing position. The difference between that two is that from the 4,4 point, your opponent has a 9x9 block of stones in which ti make a position, and it is generally accepted that you cannot stop someone from doing so in the corner unless it is played badly. From the 3,3 point, on the other hand, your opponent only has a 2x2 square in which to try to maneuver, which is simply too tight to do much. The best that can be hoped for is a stalemate in the corner, where each person has a position projecting strength along one side of the board, and one person controls the corner itself, which will generally be the person occupying the 3,3 point.

Often when people see me playing Go with others for the first time, they ask if it is Chinese checkers. While it maybe (very, very) superficially similar, they are very different. The fact is, until you’ve played the game a couple of times, the true complexity of it is not at all apparent. In fact, the first few games people play tend to be confusing. The moves an more experienced opponent makes seem to make no sense, until suddenly they put down a stone and remove a good chunk of yours. Or you find that a position you have been working towards for 10 turns was long ago seen by your opponent, who at that time placed a single stone in a key spot, destroying your position long before it was even formed. It is these kinds of things that set Go apart from Chess, with its more localized character.

In terms of complexity (in the technical, theoretical sense) Go is more complicated then Chess. This is partly because of the drastically larger board space. But it is also caused by the highly abstract nature of the game play. Ever since Deep Blue beat the world chess champion, the AI community has switched its focus to Go. At the current moment, the best Go software players at about an intermediate armature level. The difficulties faced in programing Go are two fold. The first is that the search space is insanely large. The average branching factor of a game tree for Go is 200. As a comparison, for chess it is about 10. The other problem with go is no one has come up with good heuristics to determine what makes one Go position better than another. Without this, standard techniques like Mini-Max cannot be applied. Of course, they cannot be applied anyway when the Mini-Max tree has 200+ children off each branch of the tree.

As is obligatory in any article talking about Chess and Go, a number of obvious differences between the two:

Chess starts with a board crowded with pieces, and removes them one by one. Go starts with an empty board and adds pieces to it one by one.
Chess has complicated rules, go has simple rules.
Chess has several different types of pieces, each of which has different properties. Go has one type of piece, so each piece is identical to every other.
The first move of chess dictates the structure of the whole board. The first move of Go structures only a signal corner.
Chess focuses more on tactical considerations. Go depends in large part of large strategic considerations.
The first moves in chess are a fast paced struggle for domination of the center. The first moves in go are peaceful sketches of future skirmish lines.

If you wish to try out Go, GNU Go is freely available, and you can also play against other people on line for free via the Internet Go Server. In either case, be prepared to have your ass handed to you repeatedly. A wise man once said you should loose your first 50 games of go as fast as possible. The point being that you must bang your brainagainst the go board for a while until certain formations start to glow when you look at them. At that point, you are ready to start learning how to play. You would also be wise to read The Way To Go a free 25 page pdf that explains basic strategy.

This is an interesting result from modal logic that I will try to sketch here. The upshot of the result, depending on which side of a divide you fall into, is either that there are some truths that are logically impossible to know, or that every truth is already known by someone.

The dividing line in this case is whether you are a realist or anti-realist. The realists posit that there is an external reality that has certain definite properties. The anti-realist deny that such an external reality exists (or, in some cases, that we can have access to it). I'll get more into this distinction after I sketch the proof. If you find logic boring, feel free to skip the proof and scroll to the end for a brief discussion on the implications of this result.

First, we have to state two assumptions. The first assumption is referred to as the knowability principle, hereon referred to as KP. This can be expressed as:

(KP) All truths are knowable by someone at some time.

To express this in modal logic, where "Lp" means "it is necessary that p" or "in every possible world it is the case that p", and "Mp" means "it is possible that p" or "in some possible world it is the case that p" we write:

(KP) ∀p(p -> MKp)

This could be read as "If p is necessarily true, then it is possible to know that p (is true)."

he second assumption we make is that we are not omniscient, i.e. that there are truths that we don’t know. Symbolically:

(NO) ∃Lp(p ^ ~Kp)

This reads as "There exists a necessary truth p such that p is true, and no one knows that p." We call this non-omniscience, and will refer to it as NO.

The thrust of the paradox is that these two statements contradict each other, so one of these assumptions is false. It is either the case that there are truths we cannot know, or we already know all truths.

The formal proof of this comes in two pieces. The first piece flows thus:

(1) If the existential statement NO is true, then some instance of it is true, i.e. we can drop the existential quantifier and work with the resulting statement:

p ^ ~Kp

(2) In KP, the predicate p is unbound, so we can replace all instances of p with some other predicate. In this instance, we will replace it with the predicate from the preceding step (p ^ ~Kp). Since the predicate is necessarily true, we will also drop the ∀p to get:

(p ^ ~Kp) -> MK(p ^ ~Kp)

(3) The left hand side of this implication is the statement from line 1, so the consequent is true:

MK(p ^ ~Kp)

This reads as "It is possible to know that 'p is true and that it is not known that p.'"

The first hint of where the problem lies is that we can prove with a separate proof that it is impossible to know the conjunction in line 3. In other words, line 3 is false.

The proof of this relies on two separate epistemic assumptions, neither of which is particularly troubling in its own regard.

The first assumption is that the K operator, which we have been using to represent "it is known that", and is commonly referred to as a knowledge operator, is transitive under conjunction.

(A) K(p ^ q) -> Kp ^ Kq

The upshot of this statement is that if you "know x and y" then you "know x" and you "know y".

The second assumption is that the K operator is at least as strong as truth. This means that if you know something it is true; or that it is impossible to know a false statement. (Note that it is possible to believe a false statement. We are just assuming here that real knowledge is equivalent to truth.)

(B) Kp -> p

This states that "p is known implies that p is true."

The proof also depends on two modal assumptions, which are also fairly untroubling.

The first assumption is that if you can prove a statement, then that statement is necessarily true. It is impossible to prove a false hood.

(C) If |- p, then Mp.

The inverse of this statement would be that if you cannot prove a statement, then that statement is necessarily false.

The second assumption is that "L~" ("it is necessarily false that") is logically equivalent to "~Mp" ("it is not possible that").

(D) L~p -> ~Mp.

This reads as "If p is necessarily false, then it is not possible that p."

Consider now this second proof:

(4) Assume K(p ^ ~Kp) for purposes of a reduction ad absurdum

K(p ^ ~Kp)

(5) According to assumption A we can distribute the K in the preceding statement over the conjuncts, getting:

Kp ^ K~Kp

(6) Using assumption B, we can drop the K from the right conjunct in the preceding statement, obtaining:

Kp ^ ~Kp

(7) The preceding statement is a contradiction. Our assumption at line 4 must be false, so we negate it:

~K(p ^ ~Kp)

(8) Assumption C tells us that if we cannot prove something, then it is necessarily false. So we can swap a "~" ("it is not true that") with "L~" ("it is necessarily not true that"):

L~K(p ^ L~Kp)

(9) Assumption D lets us exchange a "L~" for a "~M" giving us:

~MK(p ^ ~Kp)

Where are we now? Well line 3 from the first proof was

MK(p ^ ~Kp) - It is possible to know that "p is true and that it is not known that p."

But we’ve just proven that

~MK(p ^ M~Kp) – It is not possible to know that "p is true and that it is not known that p."

So we have a contradiction on our hands. One of our assumptions must be wrong. Now, the 2 modal assumptions and 2 epistemic assumptions from the second proof are generally considered as not up for debate. (Note that this is true only in a very loose sense. There are versions of logic where some of these assumptions are rejected, but they are far beyond the scope of this.)

So the contradiction must lie between KP and NO.

If you want to hold on to the view that all truths are knowable (KP), then you must deny that we are not omniscient, and therefore conclude that all truths are already known:

∀p(p -> Kp)

If you are a hard headed scientists, i.e. a realist, this statement is obviously false. So you are forced to conclude that there are truths which are logically unknowable. I.e., you must conclude that

∀p(p -> MKp)

is false. I.e. that

∃p(p ^ ~Kp)

is true.

On the other hand, if you are an anti-realist and don't believe in an external world, its obviously the case that all truths are already known. If the world is a product of our thoughts and beliefs, then truth is also a product of them. So we define the set of true propositions, and obviously we know what the set contains.

Now here is an interesting twist on the idea. The function that we are refereeing to as K only has to satisfy the requirement that it is at least as strong as "truth." So we could reinterpret K as any factive function that is at least as strong as truth.

For example, we could say that K means "At some point in time, it is known that." This would then become a proof that there are truths that cannot be known at any point in time.

We could say that K means "At some point in space, it is known that," and then we have a proof that there must exists regions of space about which there are things we cannot logically know, or from which it is impossible to know certain truths.

Several philosophers that I've discussed this problem with are left scratching their heads as to why it constitutes a paradox, because the result is obvious. The import of the result is that we've shown it to be logically necessary, and with damn few assumptions to begin with.

But the implications are deep, especially if you are a scientist. Scientists are going about the job of discovering what the properties of reality are. They do this using a process called the scientific method. It seems intuitively obvious that, in the limit, the scientific method provides better and better descriptions of reality. But this result shows that there must be some parts of reality that epistemologicaly inaccessible to us.

Furthermore, you can never be sure what truths fall into this category. For if we wished to know if some proposition P is true, and P is unknowable, it follows trivially that there cannot exist a proof (or some empirical method of testing) of P or a proof of ~P. For if one of these proofs existed it would contradict that fact that P was unknowable.

We can get a hint of what this may be like with the Continumm Hypothesis. I won't go into detail in regards to what it is, but just point out that it has been proven that you can neither prove or disprove the hypothesis from number theory as it currently exists. To prove it, we must add some new axiom to number theory that would allow us to derive a proof. But unless that new axiom has empirical justification, we are essentially just assuming that it is true (or false), and this would destroy any claim that mathematics would have to be an objective science.

It is a distinct possibility that many of the open questions in logic, mathematics and computer science are actually unknowable propositions. For example, consider the implications if it were true that the proposition that P = NP is unknowable, though true. It would follow that we would never disprove it (because you cannot prove a falsehood), but it would also follow that we would never discover a p-time algorithm that solves an NP-complete problem, even though one must exist! Some how, some why, we would never find it, even if it were trivially simple.

Now if THAT doesn't strike you as a surprising, deep, and puzzling result, I don't know why the hell you are reading my blog.

Rather than futilely attempt to make myself heard above the din, I’m writing this post which explains what the solution is, how you get to the conclusion, why it is in fact correct, and why the guru’s statement is necessary.

Here is the main part of the problem:

A group of people with assorted eye colors live on an island. They are all perfect logicians – if a conclusion can be logically deduced, they will do it instantly. No one knows the color of their eyes. Every night at midnight, a ferry stops at the island. If anyone has figured out the color of their own eyes, they [must] leave the island that midnight. Everyone can see everyone else at all times and keeps a count of the number of people they see with each eye color (excluding themselves), but they cannot otherwise communicate. Everyone on the island knows all the rules in this paragraph.

On this island there are 100 blue-eyed people, 100 brown-eyed people, and the Guru (she happens to have green eyes). So any given blue-eyed person can see 100 people with brown eyes and 99 people with blue eyes (and one with green), but that does not tell him his own eye color; as far as he knows the totals could be 101 brown and 99 blue. Or 100 brown, 99 blue, and he could have red eyes.

The Guru is allowed to speak once (let’s say at noon), on one day in all their endless years on the island. Standing before the islanders, she says the following:

“I can see someone who has blue eyes.”

Who leaves the island, and on what night?

The answer is that the 100 blue eyed people leave the island on the 100th night.

To work out why this is the answer, consider the case where only 1 person on the island has blue eyes. He sees that everyone else does not have blue eyes, and concludes that he does, so he leaves the first night.

Now consider the case of two people with blue eyes. They both know that one person on the island has blue eyes. So they can safely assume that that person, if he sees no one with blue eyes, will leave the island on the first night. When they wake up on the second morning and see that the only blue eyed person they know of is still on the island, they can infer that the other person sees an individual with blue eyes, and since no one else has blue eyes, it must be themselves, so they both leave on the second night.

Consider the case of three people with blue eyes. All 3 will know of 2 people on the island with blue eyes. On the 3rd day, when both of the blue eyes people are present, they can infer that the two blue eyed people also see a blue eyes person, and since everyone else does not have blue eyes, they themselves must the 3rd blue eyed person.

This reasoning will carry you all the way to the given case of 100 people with blue eyes.

If you are the 100th blue eyes person, when you wake up on the 100th day and see that the 99 blue eyed people you knew of are still present, you can infer that all them also see 99 blue eyed people, hence you have blue eyes. So you all leave the 100th night.

In other words, if there are X blue eyed people on the island, it will take X days for all of them to conclude their own eye color.

A lot of people wondered why the gurus statement is necessary. In fact, the gurus statement is vital.

The gurus statement is an indirect way of giving you information about your own eye color. No one leaves the island if he doesn’t say it. If you are a blue eyed person walking around the island, the only thing you know is you see 99 blue eyed people, 100 brown eyed people, and 1 green eyed person. You have no way of discovering your own eye color because there are no mirrors. But as shown above, once the guru makes his statement, you can conclude that the X blue eyed people will leave on the Xth day. You only see X - 1 blue eyed people. When day X comes along and all the blue eyed people are still present, you conclude that your count of blue eyed people is off by 1, and the extra one is you. Every other blue eyed person makes the same inference.

Essentially, and this is key to understand why the guru’s statement is needed, you are doing an inductive proof to conclude if you have blue eyes or not. In an inductive proof, you prove something holds for a base case, and then prove that if it holds in an arbitrary case X then it holds in case X + 1. Note that while both these pieces are necessary, the first is the logical foundation upon which such a proof rests.

The second statement lets us infer that, say, some property holds of every positive integer provided that the first statement is correct. Without the first statement, we are merely showing that if the first statement were correct, then this would hold for all positive integers.

The base case in this instance is the situation in which there is one blue eyed person, who leaves on the first day. His inference that he has blue eyes is only valid because the guru made his statement that he sees someone with blue eyes. If the guru didn’t make that statement, his inference would not be valid. So the base case in our inductive proof needs the guru’s statement to be valid.

The inductive step is to then show that a similar line of reasoning works in a case where there are X blue eyed people, i.e. in the base case it takes 1 day for the 1 blue eyed person to leave, and in general it takes X days for X blue eyed people to figure out their eye color and leave.

Every other inference in an inductive proof depends on the base case being justified. The people on the island are all perfect logicians, so they would immediately realize when they got to the island that if someone were able to communicate that they see a blue eyed person, then they could deduce whether or not they have blue eyes. The statement would justify the base case, and the inductive inference would carry then out to the X number of blue eyed people they see. Hence, the gurus statement is necessary, and you can see how the gurus statement provides needed information.

You might think that what the guru said was common knowledge. But, in the base case, it wasn’t. In the base case, everyone can see a blue eyed person except for the blue eyed person. Since no one knows their own eye color, the only blue eyed person wouldn’t know that anyone else sees a blue eyed person, and everyone else would not know whether or not the blue eyed person does (because they themselves might have blue eyes, in which case the other blue eyed person would also see a blue eyed person).

The gurus statement makes it the case that everybody knows that everybody knows that there is a blue eyed person, whereas before (in the base case), no one was sure that everyone knew there was blue eyed person. After the gurus statement, the lone blue eyed person knows that everyone but him sees a blue eyed person. There is a distinction here between first order knowledge (i.e. knowledge I know) and what is called common knowledge (i.e. knowledge I know that everyone else knows).

To put it another way, after the guru has made his statement, you can make the logical inference that everyone else sees at least X blue eyed persons, and that there are at most X + 1 blue eyed persons present as you may have blue eyes. To discover if the number of blue eyed persons is X or X + 1 requires you to wait X + 1 days. If on the X + 1th day, X blue eyed people are still present, you infer that you have blue eyes and the blue eyed count is really X + 1.

So what was the new information that the guru’s statement gave to the people? It was this: the people learned that in the counterfactual case where there was one blue eyed person, that person would be able to figure out their eye color. This is the information that lets the deductions to the actual case possible. The guru gave information about what would have happened had the situation been different. But from that, the islanders can make a logical inference to obtain information about the actual situation.

According to Kleene’s recursion theorem, fixed points exist in every programming language; i.e. in every programming language, there is at least one program (actually infinitely many, trivially different from each other.) the output of which is an exact duplicate of the program.

Attached you will find a fixed point program written in perl.

The program starts by defining an array of data. The data is actually a hexadecimal encoding of the text of the program itself. This is one of the simplest ways of implementing a quine, as these programs are called.

The data in the array is first treated as simple strings, in order to produce the initial contents of the file. Then, each line in the array is converted back to its ascii equivalent, producing the lines of code from the program itself.

This may seem trivial to do, but there is a certain level of self-reference buried here that can be hard to get around.

Consider a naive way of implementing a quine in c. You just write a program that produces its own source code right? Well here is a naive attempt:

void main(void) {
printf("void main(void){ \n");
printf("printf(\"void main(void){ \\n\");");
printf("printf(\"printf(\\\"void main(void){ \\\n\\\");\");");
..

The problem should be obvious.

We need to print out the function declaration in the body of the function, so the first statement of the function prints out the main declaration with its opening curly brace. But then we need to produce the line that prints out the line containing the function declaration. And then we need a line that produces that line, and so on. We run into an infinite regress, where each line requires that there be a succeeding line to produce it as output.

The way around this problem is represent the entirety of the code in a form that can be manipulated. Then we can use this data twice: first as uninterpreted data that gets spat out, and then as interpreted data that produces the program source code.

I wrote the perl program in a bootstrapped way. First I wrote the “hex_to_ascii” function, as well as a “ascii to hex” function. I then wrote the initial line declaring the array, the informative comment, and the bits of code to print out the data array uninterpreted, and then interpreted. I fed all this code through the “ascii_to_hex” function, and took its output and placed it into the array at the top of the file. I deleted the “ascii_to_hex” function, and it was done.

The gist of it is to write everything you need except for the contents of the array itself. Run all the code through an ascii to hex converter and use that as the data for the array. The result will be a program that produces itself as output.

As I mentioned before, this is a simple example of a quine. They can be much more obscure, or very elegant. For example, this is a classic quine in lisp, which anyone with a passing knowledge of lisp should be able to write or understand:

((lambda (x)
(list x (list (quote quote) x)))
(quote
(lambda (x)
(list x (list (quote quote) x)))))

For those unfamiliar with lisp, I will elaborate.

Lisp treats everything as lists. So to invoke a function, you make a list where the first element of the list is the function you are calling, and the remaining elements are the arguments to the function (which can themselves be lists).

So (+ x y) calls the addition function on the values x and y. Lambda is a special function that essentially defines anonymous one off functions. The syntax of lambda is

(lambda (argument list) (function definition))

Now this whole thing can be the first element of a list, in which case we can define a new function and pass it some data, and throw away the function at the end of the block. This would look like

( (lambda (argument list) (function definition)) arg1 arg2 arg3..)

So the lisp quine works by defining a lambda function that takes its arguments and constructs a list containing the contents of its argument (which is the string “(lambda (x)(list x (list (quote quote) x))))” ) plus a second list containing the word “quote” (which is a lisp keyword that functions like \ does in c) followed by the contents of x again.

A proof of the fixed point theorem

First, some definitions.

A computable function is a function that can be computed by some turing machine. A partial function is defined for some subset of its inputs, and a total function is defined for the entire set of possible inputs.

We need to number all possible programs in some way, the details of which are not important. Sn(…) will refer to the output of the n-th program acting on the input in the parenthesis.

There exists a universal turing machine, u such that Su(n, …) = Sn(…). In other words, there is a program that can take as its arguments a program and some other arguments, and return the result of applying the program to the argument list. The universal function is able to mimic any other function.

You can substitute a value for an argument in a function. If you have a program n taking some input, you can, for any input x, construct a program

t(n,x) that does the same thing as n, but takes x as an input. In other words, t is a function that calculates the same value as n when n has x as an input.

The fixed point theorem states that for any computable total function h there exists a program n such that Sn(…) = Sh(n)(…). This is read as “the output of the program with index Sn(…) is equivalent to the output of the program defined by the number of the program found by taking the number of the program found by taking the universal function acting on n [Sh(n)], and applying that program to the same arguments.”

To get from this theorem to quines, consider for a given program t, the program h(t) that prints a listing of t. h is a total computable function.

The theorem tells us that there exists a program n such that h(n) and n do the same thing, i.e. printing the listing of n. So n prints the listing of n. So for any universal turing machine, there is a function that produces as its output a listing of itself. Therefore, any turing complete programming language is capable of expressing a qunie.

Code:

The story is about a piece of software that was evolved to be indistinguishable from a paranoid schizophrenic. In the course of discussing the plot, someone asked if the paranoid schizophrenic chip would pass the Turing Test, with their inclination being no, it couldn’t.

The reason that their instinct was to say “no” was that certain speech patterns the chip used seem stilted, and not particularly normal. My response was to point out that PhD-level philosophers don’t talk like normal humans either, when they start babbling about qualia, sensory apparatus, ect. Just because something doesn’t use the queen’s English isn’t grounds for failing the test, especially when with the added consideration that it is taking a specialized version (I and several others took the position that in the story, the software passes a specialized Turing Test, i.e. one that differentiates between a paranoid schizophrenic human and a computer).

Reflecting on this further, I find I like the idea of specialized Turing tests, and want to argue that we use them all the time. For example, if I encounter someone who claims to be a computer scientist, I’ll talk to them and ask them questions that a computer scientist should be able to answer. If they answer satisfactorily, I conclude that they are what they say they are. This is essentially the only means I have of verifying their claim, as I cannot (yet) open up their brain and check to see if they have the knowledge they claim to. A PhD dissertation defense comes to the same thing. Are you really a PhD level human? Etc. and so on, and so forth. The Turing test, as Turing described it, is merely a generalization of something we do all the time.

Even the captcha at the end of this post is a form of the test, as is obvious if you know what it is an acronym of (Completely Automated Public Turing test to tell Computers and Humans Apart). Are you the sort of entity that can read the letters in the box against the noisy background? The implicit assumption here is, of course, that there is only one type of entity that can do it: humans.

As I usually do when the subject comes up, I pointed out that the Turing Test is only useful when it is passed. I.e., passing the test means we grant that you are intelligent, but failing the test doesn’t justify us denying that you are intelligent. Put more succinctly, passing the Turing test is sufficient for us to grant that you are intelligent, but not necessary for us to grant you are intelligent. You can be intelligent and fail the test.

Philosophers that discount the usefulness of the test are the ones that believe in philosophical zombies, or p-zombies. There are various types of p-zombies, but their common feature is that they lack consciousness. For example, Searle’s Chinese Room argument (on which I plan write a lengthy post in the near future) is essentially a p-zombie argument. We are asked to imagine an entity which can converse with us in an intelligent manner, but nevertheless lacks consciousness, hence Searle concludes that being able to converse with us, as this theoretical entity does, doesn’t warrant the conclusion that the entity is conscious. Philosophers like Dan Dennett claim that the whole idea of a p-zombie is vacuous, i.e. makes no sense at all. I would tend to agree with him. To do Searle justice, however, I must point out that he insists he is a physicalist, with the added assumption that the matter that makes up the conscious entity is important, i.e. maybe carbon based life forms can be conscious, but silicon ones cannot. Looked at in this light, the Chinese Room argument can be spun either as a defense of dualism, or of Searle’s brand of physicalism. Since it is Searle’s argument, we should take it as a defence of his brand of physicalism.

Other versions of p-zombie arguments would talk about entities that lack certain phenomenal experiences, which philosophers call qualia. If you shoot a p-zombie, he cries out as if he feels pain, but he really doesn’t, because there is no consciousness there to do the feeling. The best way I’ve seen of describing this to laymen is that there is something it is like to be me, i.e. there is a subjective experience of being a particular person. There isn’t anything it is like to be a p-zombie.

Dennett and others would claim that you cannot be exactly like a normal human being, and still lack consciousness. Flipped around, they claim that you cannot be unconscious and do the things that humans do. So if we have a machine that passes the turning test, we must conclude that not only is it intelligent, but conscious as well. If this weren’t the case then it would not mean anything tangible to be conscious. If one can be unconscious and behave exactly the same as a conscious entity, then there is no functional difference between them.

Zombie arguments are generally used against claims of phyiscalism, the position that everything has a physical property, and they support a form of dualism, though not every dualist believes in p-zombies. In the p-zombie cases, the dualism they support is that there are two types of substances in the world: physical substances and mental substances. The Chinese Room argument aims to show that having something that is functionally equivalent to a Chinese language speaker does not entail that it has the proper mental substances to make it conscious. In other words, a simulation of my mind is not conscious, even if my actual mind is.

The most famous zombie argument, and the origin of the concept, which you cannot help but run into when you start to delve into the philosophy of artificial intelligence, comes from David Chalmers. The argument aims to show that physicalism is false.

The gist of this argument is this: If physicalism is true, there cannot be a world where all the physical facts are the same as ours, AND there are some additional facts (because the physical facts determine all the facts). But we can imagine such a world ,for example, a world where all the people are p-zombies. Therefore, physicalism is false.

Obviously, I’ve boiled a lengthy argument down to its skeleton, and probably done it an injustice along the way, but this is its essence. Dennett and others argue that the second claim is false. Such a world could not exist.

What does all this boil down to? That in some sense the Turning Test is an acid test about people’s opinions regarding philosophy of mind. If you believe p-zombies are possible, then you must conclude that passing the Turing Test warrants a different belief about an entity than for someone who does not believe in p-zombies.

In its classical formulation, the paradox is expressed as follows:

One grain of sand is not a heap.
If one grain of sand is not a heap, adding one grain of sand will not make it a heap.
So two grains of sand are not a heap.
So three grains of sand do not make a heap.
…
X grains of sand do not make a heap.
Therefore, 10,000 grains of sand do not make a heap.

The form of this argument boils down to:

X grains of sand are not a heap.
If X grains of sand are not a heap, adding 1 grain of sand will not make it a heap.
(Some arbitrary large number of grains of sand) do not make a heap.

The paradox also works in the other direction, where we start with a certain number that everyone acknowledges makes a heap, and point out that removing one grain doesn’t turn it into a non-heap, hence we still have a heap with only one grain left (or no grains left, if we really want to be absurd).

The heart of the matter is the problem of vagueness. In the technical/philosophical sense of the word, a concept is vague when there are cases where it is not clear whether or not the concept holds. In the example of the heap, this comes up because we don’t know where to draw the dividing line between “heap” and “not heap.”

Many fixes have been proposed. These range from setting arbitrary limits, to multi-valued logics. All the fixes have deep problems of their own, if they even avoid the sorities problem at all. For example, if you use a multi-valued logic to distinguish between “heap”, “non-heap”, and “indeterminate” you now have two sorities problems for the price of one. The boundary between “heap” and “indeterminate” is just as fuzzy as the original heap/non-heap problem it was supposed to fix. The same holds for the indeterminate/non-heap boundary.

Similar problems attend to baldness (just replace grains of sand with hairs, and heap with bald), human life (a single celled fertilized egg is not a human, etc.), race (old slaves laws in the USA would legislate that you were African American if you had one as a great grandparent), etc. In a more technical sense, the problem attends to concepts such as provable, satisfiable, etc. As with many things, the problem of vagueness is all around us and jumps and once we become aware of its existence, we see it everywhere.

One of the places I’ve noticed it crops up is a certain argument of the creationists.

Some creationists acknowledge that “micro” evolution occurs, but deny that “macro” evolution does. Biologists in general deny that such a distinction can be made. Defined loosely, micro-evolution is minor changes in an organism, i.e. small changes that do not drastically alter the organism. For example, a mutant human might have orange hair, with the gene for the coloration being able to propagate through sexual reproduction.

Macro-evolution, on the other hand, is much more drastic changes, to the point where you would deny the resulting creature is of the same species as the parent. For example, a mutant human might have 3 fully functioning eyes, and be able to pass on the gene for this structural change. Or they might have a skull shaped more like an orangutan than a normal human.

The gist of this is that (creationist claim) micro evolution still leaves you with a single species, where as macro-evolution is necessary for the diversification of species to occur. They acknowledge that micro-evolution occurs, but deny that macro-evolution occurs.

If we unpack that just a small bit, we see those he creationists are using a sorities argument. It goes like this.

If you take a dog, and make a minor change (micro-evolution), it is still a dog. If you’ve made X minor changes to the dog, and make one more change, it is still a dog. So no number of minor changes to the dog will result in a non-dog.

To really drive home the absurdity of this argument, lets jump back to a sorities argument for a second. Take myself for example. If you replace one molecule of my body with a molecule of scrambled eggs, then I’m still me, right? So if you’ve replaced X number of molecules of me with scrambled eggs, and you replace one more, then I’m still me. So I’m still me when you’ve replaced all of my molecules with scrambled eggs….?

This argument is obviously fallacious. The problem is not that there is no dividing line between me and scrambled eggs; the problem is that it is not so much a line as a hazy area, the boundaries of which seem to be impossible to pin down precisely.

Getting back to the creationists, the problem with their argument is it is denying the simple claim that lots of small changes add up to big changes. I take the dog and I shorten the snout a tiny bit, maybe a millimeter. And then I do it again… and again… Then at some point, I modify the tail to give a little more control over it… and then a little more… Then I make minor changes to the eyes…

The creationists will insist (if they want to be consistent, anyway) at every step of the way that I still have a dog. But at some point, my “dog” starts looking a lot like a cat. At some further point, my “dog” is physically indistinguishable from a house cat. Somewhere in this sequence, the creature in question crossed a boundary from “more like a dog” to “more like a cat.” Finally, it cross another boundary and becomes a cat in truth. But as I’ve been belaboring, these point are very vague, and cannot be pinned down precisely.

A tangential argument that some creationists offer, which I will address here because it can be used against my hypothetical, is that there is no sequence of changes can turn a dog into a cat. This seems to me to be trivially and obviously false, but I believe in evolution, and draw my argument from it, so it is really of limited usefulness.

Cats and dogs are both mammals, so they descend from a common ancestor. Starting from that ancestor, there were two sequences of changes, one that turned the ancestor into a dog, and one into a cat. So there must exist a sequence of changes that turns a dog into a cat. That sequence is this: Take all the changes that turned the ancestor into the dog, in reverse order. I.e., undo the last change, then the change before that, etc., until you are back at the ancestor. Then apply the changes that took the ancestor to the cat. QED.

Lets do a little thought experiment.

You are an archaeologist. You and your partner are returning from a dig in a foreign country, and each of you has an identical artifact from the dig among your luggage, the only ones of their kind ever found. During the flight, both of your artifacts get damaged. The manager of the airline wants to reimburse you for the damage, but is faced with the problem that, being unique, there is obviously no established value of the objects.

However, he is a clever guy, and realizes he can use your greed to determine a fair value. He sets an upper limit of compensation at $100. He then states that, he will ask each of you to secretly tell him the value of the objects. He will assume that the value of the object is the lower amount told to him. To reward the honest person, he will give them twice the value, and to punish the greedy person, he will give them half the value, rounded up to the nearest dollar. If you both tell him the same amount, you each get that amount.

What should you tell him to maximize your GUARANTEED payoff?

The answer is $1.

The reasoning that leads to $1 is this. You might both say $100 (and I’ll address this in a moment), in which case you each get $100. But then you realize that if you say $99 while your companion says $100, you will instead get $149. So you should say $99. But wait a moment. Your companion is just as smart as you, and so he has realized the same thing (that he should say $99 in hopes that you say $100). So to out bid him, you really have to say $98, and get a $148 payoff. But wait a moment! He’ll realize this as well!

This process will continue until you hit $1, at which point there is no reason to go go lower. If you both say $1, you both get $1. If you say $1 and he says a higher number, you get $2, and he gets $1. If he says $1, and you say a higher number, he gets $2 and you get $1.

So your response to maximize your guaranteed payoff is $1.

Now, i know some people will say “Why not just say $100 and hope for the best?” The reason not to is that the way the problem is described, it is asking what is the highest payout you can assure yourself of, and what number do you say to get it. Economists and game theorists like to pretend we are perfectly rational, and they assume that a perfectly rational individual will want to maximize their guaranteed payout, not risk loosing everything in the hopes of a big gain.

The technical name for the $1 position is the Nash Equilibrium. Essentially, the Nash Equilibrium is a set of strategies in a game where no player does any better by changing his strategy unilaterally. In the above example, lets say you had decided on saying $100, but were then told that your companion is going to say $99. You would want to change your strategy to $98. The point at which you don’t change your strategy based on what the other player does is $1. So the Nash Equilibrium in the above example is $1, and in a certain sense is the most “rational” response.

What is the point of all this setup?

Well, recently I came across a website called SoLow. SoLow is an auction site with a twist: the lowest unique bid wins.

For example, lets say they are auctioning off a nice shiny new LCD television. Lets say that 6 people bid on it, with their bids being $0.01, $0.01, $0.03, $0.03, $50 and $100.00. The person who bid $50 wins the auction. The people who bid $0.01 loose because though they bid low, they didn’t bid unique. Same for those who bid $0.03. The $100 bid was unique, but not the lowest unique bid.

I think the similarities to this bid process and the above thought experiment are pretty clear.

Obviously, since no one is going to bid more than the lowest price they can find on the net for the item in question, we have a definite upper bound on the bids. But what about a lower bound? Should we even bother to bid $0.01? Surely everyone will bid $0.01, so there is no point in doing so. But, on the other hand, maybe everyone else came to the same conclusion, so we can outsmart them all by bidding it!

Its a fairly interesting system, and I am curious about the average price items go for in terms of a percentage of retail price. Where is that magic sweet spot between enough of a discount to make it worth while, but high enough to bypass all the “obvious” low bids? Furthermore, is there a Nash Equilibrium for this game? There has to be, as it has been proven (by Nash) that such a strategy must exist for all finite games with any number of players. Before Nash, it had been shown to hold in two player, zero sum games.

But I have difficulty seeing how this can hold for the auction. Any player who doesn’t have the lowest unique bid will want to change his bid when he discovers that fact. By definition, only one player can have the lowest, unique bid, so every other player would want to replace his bid if he knew everyone else’s bids. So the game is inherently unstable, and the only way to “win” is to be holding the lowest unique bid when the clock runs out.

Maybe there is a technical detail to the Nash Equilibrium i am missing, and it doesn’t actually hold for the auction. I’ll update this post if i become more enlightened.

Update:

After talking about this with a friend, I realized as I was walking back to my office afterward that SoLow does indeed have a Nash Equilibrium, and that in the course of our conversation, we had skirted it several times.

Consider it this way. SoLow has a time limit, so what happens is that bidding starts at $0.01 and works upwards. At some point, the auction expires and someone wins. But what if there were no time limit, and bidding continues until no one wants to change their bid?

Then the game ends when the Nash Equilibrium is reached, as the NE is defined to be the point where no one would change their bid if they knew what everyone else was bidding. So where would the game end?

The game would end when one person bids the exact retail value of the item, all lower bids already having been used by multiple people. As mentioned above, he won’t change his bid because he is already winning, and everyone else will just go elsewhere for the item in question. This, then, is the NE for SoLow.

This still leaves the interesting question as to whether we should say SoLow is depending on peoples greed to make money (i.e., the price of the item will be driven up because greedy people will fill in all the stupid low bids, like $0.01) or if it is depending on peoples rationality to make money (i.e., people will bid a reasonable amount, in the knowledge that the idiots will outbid each other in the low end). Maybe both?

An interesting repercussion of the fact that the Nash Equilibrium is as stated above is that SoLow can basically count on many items not going for a stupidly cheap amount. If the NE was at $1, for example, the company would obviously fold in short order (if this was their only revenue source). It only works because the NE is essentially selling the item at fair market value.

To drop my two cents in on the matter, I must say that the answer to the question is obviously yes; but we have to define “body.”

If you define body to be a physical object in the world that is capable of moving around and interacting with reality, the answer is no. If, on the other hand, you define “body” simply as “a means of obtaining input for the mental processes to act on,” then by all means the answer is yes.

My point is that, while intelligence needs some sort of sensory input to act on (else what the hell would it mean for it to be intelligent?), we shouldn’t be physical chauvinists about where those sensory inputs come from. They can be byte streams from a network interface, the pixels of a camera, or the electrical signals from a piece of meat sensitive to touch.

Now, we can modify this question and ask “can an artificial intelligence have human like intelligence without a body?”

One comment in particular seems to answer this formulation of the question in the negative:

“Can an AI understand the written or spoken word “ball” without associating it with the visual patterns of seeing various balls, the feeling (real or virtual) of holding one, the intuitive physics of throwing, bouncing, and catching one, the concept of games, other spherical objects, etc.?

….

I believe that computational AI is possible (along with machine consciousness) and that many tasks expected of an AI may be possible with limited sensory connectivity, but some tasks necessary, say, to pass a Turing Test might require a “body” (real or virtual, humanoid or abstract) with a full (or augmented) set of senses in order to understand the depth and nuance of language, not to mention human behavior, art, humor, etc.”

Well, why couldn’t it understand “ball"? Don’t we all claim to understand words associated with objects that don’t, or in some cases couldn’t really exist? We sometimes talk about square circles, even though the concept is a logical (and physical) contradiction (boxing rings to the contrary), but that doesn’t seem to stop us from thinking we understand what the (non-existent) referent of the word is.

And what about something like Grahams Number, which I mentioned in my previous post? Does anyone really know what Graham’s number is? Certainly not in the same sense that we “know” what 3 is. But this doesn’t stop us from intelligently talking about it, reasoning about it, ect.

You could argue that we are only able to do so because we have interacted with other things in a physical way, and are extrapolating from the existent objects to the non-existent ones. I have some understanding of Grahams Number, because I already posses understanding of numbers in general.

What it boils down to is a claim that to get to a “understand the depth and nuance of language, art, etc.” requires you to get to the understanding in a certain way, i.e. by interacting with a sensory environment of a certain type (virtual or actual). This is an empirical question that we cannot solve from the comfort of our armchairs, but my gut feeling is that the claim is wrong. Violating my previous statement, from the comfort of my armchair, I fail to see why we can’t start with, say, just raw logic or some other incredibly weird sense data and arrive at the same place that humans do via another path.

But, then, what are we to think of people who are truly color blind, as in they see only monochromatic colors? Do we want to say that they could not possible understand the word “color"? Or how about someone who was born a blind paraplegic? Could they ever truly appreciate the word “ball” since they have never seen nor felt a spherical object, or watched the physical actions of objects? Can a blind person really understand what a triangle is? Interesting questions to which I do not have the answer, though I’m inclined to say yes, with the qualification that their understanding obviously won’t be exactly the same as ours, but that doesn’t make ours “right” and theirs “wrong.”

As to the second part of his comment, I’m not entirely sure I buy it. Certainly Good Old Fashioned AI (GOFAI), the idea that we could just program a human grade artificial intelligence, turned out to be much harder then initial estimates. But just because it is hard does not mean it is impossible. We’ve never logically proven that you cannot write an imperative computer program that would pass the turing test, so the jury is still out on whether or not it is possible. A mountain of empirical evidence in the form of “every attempt so far has failed” doesn’t mean it is impossible.

How could we show that it is impossible? By showing that the brain computes a non-computable function would do nicely. For attempts in this direction, consult J. R. Lucas Minds, Machines, and Godel and Mechanism: A Rejoinder.

I’ll post a review of Lucas’s position in a future post.

One last, small tangent. Someone posted a lengthy reply on their own blog, where they also make many interesting points, but fall victim to a common misunderstanding regarding the Turing Test. Specifically, many people, both inside and outside the AI community, seems to think that the turing test is an intelligence test. I.e. if you cannot pass the turing test, then you are not intelligent.

This is absolutely wrong, as I think is clear if you read Turing’s original paper. The test is only meaningful in the positive, and not the negative, aspect. If you can pass the turing test, we must grant that you are intelligent. On the other hand, if you fail the turing test, we must do nothing. Failing the turing test is not grounds for denying intelligence, but passing it IS grounds for asserting intelligence.

The article is fairly long, but also quite interesting. The associated thread on reddit is also interesting, but is topped by a very similar discussion on the XKCD blog about naming large numbers.

The XKCD discussion is associated with a funny comic wherein he suggests calling the Ackermann function with Graham’s number to horrify mathematicians.

The Ackermann function is a computable function that is not primitive recursive, and grows astoundingly fast (though, as noted elsewhere, apparently not as fast as the busy beaver function).

Graham’s number is a number so ridiculously huge that it cannot be meaningfully expressed in scientific notation. Instead, a special notation had to be invented to write it down. This number acctualy has a practical (?) use: it is currently the smallest upper bound on an unsolved problem from a field of mathematics called Ramsey theory. The current lower bound? Six. That’s right… We know for a fact that the smallest answer to this question is 6, and the largest is greater than the number of seconds since the big bang, plus the number of atoms in the universe, plus the total number of possible chess games, plus… you get the idea.

Or maybe you don’t. Put it this way. If we turned every atom in the universe into pen and paper, there wouldn’t be enough matter to write out this number in base 10 notation. If we had a printer that was able to magically make paper and ink out of thin air, and was capable of printing a billion sheets of paper in 1 second, and set it to printing this number, it wouldn’t be done for several hundred trillion years. For that matter, it wouldn’t even be able to print out a googolplex in under several hundred billion years. (A google is a 1 followed by 100 zeros, or 10^100. A googolplex is a 1 followed by a google of zeros, or 10^(10^100). Most people only know out to billion, which is a 1 followed by 9 zeroes or 10^9, or a trillion, 1 followed by 12 zeros or 10^12.) In the mean time, all that paper would completely fill the universe several times over.

Needless to say that when you take a function that grows insanely fast, and feed it a number that is basically inconceivably large, you get another number that simply defies conception.

Of particular note, from these threads I stumbled across an interesting “game” called MineField, apparently developed by Bram Cohen.

Essentially, the game is about naming large numbers, and as is pointed out in some of the threads listed above, this eventually turns into a game of developing stronger logics. Apparently this is the case because there is a limit to the complexity of a statement in a given logic. I’m going to hazard a guess and say this is directly related to the Berry Paradox, a subject on which I intend to write my next entry.

MineField makes the connection to stronger logics explicit, by setting up the game in such a way that on a given players turn, they can add a new axiom to the shared logic the players are using to describe numbers. They start with an axiomatic basis of set theory, any of the common bases which are accepted as consistent. So a player adds an axiom to the logic, and uses the now stronger logic to name an infinite number.

There are a few more details relating to how to “win” the game, but I leave it to the reader to click through if interested.

The busy beaver function, denoted here as B(x), is a function that returns the highest number of 1s a turing machine with x states can print on an initially blank tape before halting. An alternative formulation of the questions asks “How many steps can the turing machine take before halting?”. The two questions have essentially the same properties, but the later is slightly easier to reason about, so for the purpose of this discussion, we will use it as our working definition.

This function happens to be incomputable, i.e. there is no program that when carried out by a computer will calculate the value of B(x) for any x.

There are several ways of proving this to be the case, but perhaps the simplest is this.
As Turing proved, the halting problem (giving a computer and a program, determine if the computer ever stops once started executing the program) is non-computable.
If the busy beaver problem were computable, then the halting problem would be computable as well. But we already know the halting problem cannot be computed. So B(x) cannot be computed either.

How can we use B(x) to solve the halting problem? Like this: Say we have an n state turning machine and some program, and we wish to know if it halts or not when started on a blank tape. First, calculate the value B(x). This value will place an upper limit on the number of internal states the program in questions can go through. Then, run the program on the turing machine. Either the turing machine will execute a certain number of steps less than or equal to B(x) and halt, or it will execute a number of steps greater than B(x) and never halt. We keep track of the number of states the machine has gone through, and once it crosses the critical threshold at B(x), we know the machine will not halt. The limitation of working on a blank tape really is not a limitation, as any program can be re-written with all the needed variables coded into the machine.

So B(x) is uncomputable. But we can still discover information about it. For example, B(1) = 1. The machine has 1 state and starts on a blank square. So the condition the machine is in when started (in state 1, looking at a blank spot on the tape) is identical to every state the machine can ever be in. So it either halts immediately (i.e. 1 step) or it never does.

Below are all the possible configurations of this single state.

Tape Symbol Write Symbol Move Head Next state
0 1 Left 1
0 1 Left Halt
0 1 Right 1
0 1 Right Halt
0 0 Left 1
0 0 Left Halt
0 0 Right 1
0 0 Right Halt
1 1 Left 1
1 1 Left Halt
1 1 Right 1
1 1 Right Halt
1 0 Left 1
1 0 Left Halt
1 0 Right 1
1 0 Right Halt

There are 16 ways the single state can be arranged. In our formulation of the problem, we are considering a machine acting on a blank tape, so all configurations that consider a square with a 1 in it are thrown out immediately, leaving us with 8 possible states. Of these 8, 4 of them write a 0 (or blank) on the tape, so these are thrown out as well, leaving us 4. Of these 4, two of them write a 1, move one square left or right and halt, and two of them write a 1, move one square left or right, and go back into state 1. It is obvious that the latter machines must never halt. They go into an infinite loop, wherein they are considering a blank square, write a 1 on that square move left/right, and repeat, forever. It is also obvious that the former machines will only print a single 1 before halting.

So from this exhaustive examination of 1 state machines, we can conclude that B(1) = 1. We can also conclude (indeed, we just showed this in the preceding paragraph) that a single state machine will either execute one instruction or halt, or execute an infinite number of instructions and never halt.

Present knowledge about the value of B(x) looks something like this:

n B(n)
1 1
2 4
4 13
5 >=4098

A curious property of B(x), and part of the reason it is uncomputable, is that f(B(x)) is smaller than B(x+1) for infinitely many x. The function B(x) grows at a truly astronomical rate. In fact, it grows faster than any computable function, and is therefore not one of the set of computable functions.

Put more precisely, for any computable function f, B(x + 1) > f(B(x)) for infinitely many x. For example, if f were x^10,000, then B(x + 1) > x^10,000 for infinitely many x. Since this holds for all computable function, it follows that the output of B(x) is not identical to the output of any particular computable function, and hence B(x) is not itself a computable function.

I think that some people don’t accept the (what I believe to be) self evident proposition that reality must be consistent.

My gut feeling is something like this.

There are natural laws that dictate (or perhaps explain…) how sub atomic particles work. If those laws varied from one moment to the next, things like us, or planets or basically anything else we see the universe would not exist, for the simple fact that we are a product of a certain configuration of those rules. If those rules changed in certain ways, matter as we know it, or chemical process as we know them, (insert a huge list of things here) would no longer exist/work/what have you.

The fact that we are here and haven’t blinked out of existence* is pretty good evidence that, if the laws of physics do vary from moment to moment, they don’t vary in any way that would affect our existence. If they do vary, then they vary consistently, i.e. they can only vary in ways that don’t destroy us… in other words they vary in a law-like way, so in actuality the universe is still consistent

The laws can’t be broken. If they seem to be broken according to current understanding, then it’s the case that current understanding is wrong, and not that the laws are broken.

Now there is still the question of “maybe the laws of physics vary in space even if they don’t vary in time. In other words, we exist in a part of space with one set of physical laws, but on the other “side” of the universe, there is a place with different laws.

That’s a slightly thornier question, but the same basic argument forms apply.

If everything that exists came from the same initial starting singularity, and there are in fact parts of the universe with different laws of physics, the fact that those places exist have to be accounted for by an overarching set of laws, and you’re right back to a set of inviolate laws that hold everywhere and everywhen.

Tangentially, one consequence of this is that there is a problem with any sort of creature that can contravene the laws of physics. Meaning, such a creature cannot exist. Any creature that appears to do something that contravenes the laws of physics is really doing something that is allowed by the laws of physics; we just don’t have a good enough understanding (yet) to explain how.

*Note: We can make an anthropic argument argument about why the laws in this particular universe we inhabit must be consistent, but I wish to put forth the stronger claim that they must be consistent in any possible universe. An inconsistent universe cannot exist.