I read Papadimitriou’s article on Algorithms, Games, and the Internet, and found it to be a rather nice overview strongly hinting at future emphasis within the Theoretical Computer Science community. I’ve long thought that a good game theoretic background would help in the development of network protocols, esp. wireless protocols. I particularly liked FON’s original approach (Bills, Linus’s, and Aliens) to popularizing the spread of wifi.

I also really liked section 6, Mechanism Design, where he says that:

If an artifact (a new congestion control protocol, a new caching scheme, a new routing algorithm, etc.) is demonstrated to have superior performance, this does not necessarily mean that it will be successful. For the artifact to be “fit,” there must exist a path leading from the present situation to its prevalence.

A formalization of this observation could really help out those in Software Software Engineering.

All in all I’d like to see the development of a Universal Protocol that lets all devices communicate in a wireless fashion. So that I can buy a TV, Computer, Equalizer, and Speakers all separately, and by simply having them in the same room, I can pipe video from Computer to TV, audio from Computer to Speakers, or from TV to Equalizer and then Equalizer to Speakers. A single protocol should be able to carry everything from audio to video to any device that publicly announces a stream or slot. Internet traffic should be similarly transparent. With the correct allocation algorithms, we can build a nation-wide wireless aethernet one $40 router at a time. (Even better if we could work in roaming.) And it’ll all come from a coupling of Game Theory and Computer Science.

Yesterday, a nice youth visited my dad’s weekly gathering. At 22 he brought back pictures of the death and carnage that he’s witnessed as part of his tour in the Mid-East.

Now, I dislike the idea of war, and the associated loss of human life. So I asked, what can be done about it? Well, he didn’t really know either. It’s a terrible political situation.

Never to be fully deterred I thought up the following solution:

One of the easiest ways to avoid war in the first place is to open up trade relations. Along with the exchange of goods and services an inevitable exchange of ideas and cultural values will take place. Unfortunately for the U.S. we don’t have anything really interesting to export. In fact we get all of our good stuff from China and Taiwan. But we can export some culture. So lets talk about the basis of western culture, and the reason for it’s stability.

Western Culture was founded upon Christianity, and has a prominent underlying narrative: The Martyr. This narrative has many instantiations (Jesus, Joan of Arc, Braveheart), but the important part is that the martyr dies at the hands of his enemies and thereby exposes his enemies weaknesses of fear and lack of understanding. By sacrificially dying for his cause he rallies his proponents via a grand display of intolerable injustice, and bloodies the hands of his enemies.

This is in fact a very dangerous narrative to popularize in the Mid-East. The fighting that occurs there is very much of a religious nature, but not along the Judeo-Christian lineage. The success of the martyr in the western hemisphere has been as a result of noble sacrifice of the self for one’s beliefs. But Muslims are all too happy to do the same. However, it has a subtle and crucial difference. The Muslim sacrifices himself in the hope that he takes out some of the enemies along the way, while the Christian martyr dies with clean hands. We will, therefore, not solve the problem of fighting by exporting the story of the martyr, because they already have an entrenched mindset of sacrifice which is too similar to gain enough traction to make a difference in the behavior of people in the Mid-East.

Instead we need a stronger tale. Even more enticing than the martyr is the tale of a hero who, in great adversity, learns about and understands his enemies. This can come about in many ways. Either, he learns about them after having to live with them in captivity, or he willingly hides himself amongst them in order to gather the intelligence for making as severe a strike as possible. In either case, after learning about his enemy, he finds that they are not so different from himself, that they too value human life, willingness to stand up for personal beliefs, etc, etc. After this experience, he decides not to kill his enemies, but instead profit through them, via creation of a trade empire or by evangelical conversion.

This narrative, of overcoming the adversary by greater understanding, can by sold and popularized in many ways, Movies, TV, Cinema, Music, Literature. In popularizing this narrative, we might hope to lengthen cultural patience and lessen the trigger reaction that gets so many killed today. In truth we could all benefit from this tale, because it says, quite directly, that nobody has to die, that mutual understanding is possible, and that we are all better off if we exercise control. Not only that, but the hero benefits both spiritually and materially, plus he lives to enjoy his successes.

Alas, the marketing of this idea can only really be effective if our own companies are willing to create works that will be popular in the Mid-East. This is highly doubtful, as they have far less infrastructure for distribution, transport is far riskier, and Hollywood studios are managed in such a way that they will favor the production of crap. In addition, sale of this idea will take generations, and the U.S. is unable to commit to a multi-generational program for the simple reason that leadership is re-elected every 4 years.

So my solution is a complete and practical flop…. but at least I can dream.

Today I watched the Evolution section of a Discovery program about the 100 Greatest Discoveries. In it Bill Nye talked about the Cambrian Explosion and the Burgess shale. I remember that back in High School I had an argument with a Creationist friend about the sudden explosion of life in that era, and though I never backed down from my belief in Evolution, I couldn’t think up a reason for such an event to occur.

Now, 10 years later, with exposure to many more ideas, I independently came up with the following explanation:

• Evolution is composed of natural selection, and relies upon variation within a population. It is a process relying upon feedback.
• Feedback can lead to exponential returns

I argue that before the explosion there must have been plentiful unicellular organisms of many different types, all sharing their genes in a horizontal fashion. When one day along comes a means of forming a multicellular collection, benefiting it’s unicellular components. Eventually this leads to even more variation of life than had existed previously. But until the time that life ceases to share genes in a horizontal fashion things will proceed more or less the same. That is all creatures of all types will bear very close resemblance to each other.

Once an organism viciously breaks this horizontal transfer mechanism, it can then proceed to evolve along it’s own path, always with respect to its environment. Suddenly it’s descendants will inherit both advantageous and disadvantageous traits while the rest of earth microbes get nothing. Natural selection will weed out the disadvantageous lines, and genetic recombination will experiment with the more successful lines. Now we enter the feedback loop. As these genetically selfish organisms change over time, more and more ecological niches open up for more evolution to occur. Changes begin to accelerate, and suddenly we have the Cambrian Explosion.

Had life stayed with the horizontal gene transfer mechanism, we would never have evolved. Any beneficial changes made by an organism would be spread directly back into the population at large. The microbes are not genetically in competition with each other. Once privatization of genes occurs, there begins a direct competition, a riposte and parry, that jumpstarts the process of evolution.

I am not alone in this observation, apparently the eminent Ray Kurzweil has argued about accelerating change, using the Cambrian Explosion as a particular example. (just remember, I thought of it second.)

Today, I was reading Sipser’s Theory of Computation and in chapter 6 it said:

For statement 3 (Machines cannot self-reproduce) we make the following argument that machines cannot self-reproduce. Consider a machine that constructs other machines, such as an automated factory that produces cars. Raw materials go in at one end, the manufacturing robots follow a set of instructions, and the completed vehicles come out at the other end.
We claim that the factory must be more complex than the cars produced, in the sense that designing the factory would be more difficult that designing a car. This claim must be true because the factory itself has the car’s design within it, in addition to the design of all the manufacturing robots. The same reasoning applies to any machine A that constructs machine B. But a machine cannot be more complex than itself. Consequently, no machine can construct itself, and thus self-reproduction is impossible.
How can we resolve this paradox? The answer is simple: Statement 3 is incorrect. Making machine that reproduce themselves is possible. The recursion theorem demonstrates how.

Sipser then goes on to talk about Turing Machines which behave as a quine.

This could be a resolution to a burning question that I have: Is it possible to have an Algebra of Algorithms?
It would be very useful if we could. I imagine that such a structure would be akin to the combining forms of Backus’ Functional Programming. But on the other hand, algorithms are more complex than an algebra, and their internal relations might be too complex to encode in an algebra. Intuitively you should not be able to talk about a complex thing in a language simpler than the object under discussion, yet the very existence of a quine suggests otherwise. I am very interested in resolving this issue, as it has deep applications to my primary area of study: The relationship between what we think (algorithms) and what we say (programs).
In order to resolve this issue I should probably ask: Does there exist an encoding of Turing Machines such that a machine computationally weaker than a Turing Machine (ex: Stack Machine, or Finite State Machine) can determine whether or not a string is a valid description of a Turing Machine?

Aside: this whole train of thought provides a nice rebuttal to anyone (religious-types) that prefer to maintain that a Finite beings can’t understand The Infinite. Honestly, humans made up the concept of the finite and the infinite, but most people haven’t gotten past the thinking prior to 1890’s, and are instead stuck in the christian apologetics of the dark ages, refusing to accept modern logic’s discoveries about the infinite.

Ahh, the lazy days of summer, and the delightful philosophy that imbues them. I absolutely love verbal fencing. Because through the dancing around of argument, you get to know more about yourself and why you believe the things you do, and why your partner believes the things they do. In addition there are usually plenty of opportunities for jokes and good humor. But most importantly, you share a learning experience about each other.

Today, after talking about Turing machines and reducibility (and going through a nice clever proof of the undecidable nature of the Post Correspondence Problem) I was able to have a rather lengthy conversation that touched on religion and the nature of thinking.

I attempted an instill in my friend an unsuccessful conversion from Christianity to … well, not atheism, but at least a state of questioning. I tried 2 methods.

1. Method 1: Logical contradiction
   Try to use the classical attack on an ‘All-Powerful Being.’ That is: Can God make a rock so heavy he cannot lift it? Unfortunately I didn’t get quite what I expected as a riposte. Instead I received “Only God can set limitation upon himself.” To which I parry, “Can God create a being that is powerful enough to put limits on God?” to which I receive the nice and simple “No.” I which case I’ve won the argument (and least in the limited logical sense) because I’ve trapped my opponent into naming something that God cannot do, in spite of the fact that he is supposed to be Omnipotent.

   Now this actually isn’t a satisfying win. In fact, I’ve never had success using this argument. Logic alone cannot make a person convert religions. In fact the more a religion preaches the finding and re-affirmation of belief through incidents in every-day life that I ascribe to mere coincidence or good fortune, the less success you will have with a purely logical critique of God’s existence.

2. Method 2: Demonstrate why God is unnecessary.
   This is actually the primary reason for my own atheism. For every reason that a person could come up with for answering the question “Why is a God necessary?” I come up with a perfectly materialistic method that satisfies that condition. I forget what the specific reasons were in this case, but I do remember mentioning that “The idea of a God is meme that lets you connect and communicate in a community among other similarly infected people, and thus the meme helps fulfill a very basic human psychological need, and thereby propagate itself at the same time.” (This last part was a back-reference to a previous part of the conversation about Dawkins memes.) Insulting someone is not exactly the best way to go about a conversion, no matter how cleverly performed. The other reason was to “put something higher than yourself.” Well, why a God, why not the more self-evident principles, or simply a set of morals? I couldn’t make any headway on this one, even though we both agreed that most morals are fairly axiomatic. So, in my view, if you wish to believe in something higher than yourself, and thereby transcend your more baser instincts, then why not simply adopt a moral system without a God? But, sadly, my friend just wouldn’t let go, not even to entertain the argument, copping out with a “If a simple moral system is enough for you then fine.”

   Interestingly, I fielded none of the more common reasons, like the need for a Creator, or the need for a Bestow-er of Morality.

For me, this was a really informative conversation, and it occurred to met that God is so powerful that He can effect all the wondrous things ascribed to him without the burden of existence. I wasn’t expecting to make a conversion, rather my aim was to try and understand what it is that Christian’s get from their beliefs. For my friend it was primarily a sense of belonging to a group, and the intellectual sharing that occurs within that group. A reason with which I can personally identify (this town is an intellectual wasteland, I’ve got to go back to grad school). I’d like to further understand the psychology of belief, in the hopes of formulating pro-atheist arguments that a Christian can identify with, arguments that are non-threatening. Because Dawkins is afraid of religion for exactly the same reasons and with the same level of vehemence that the more fundamentalist religious people are afraid of him. (the world has wonderful symmetry.)

Unfortunately for my friend, he is not yet well-skilled in the art of verbal fencing, so I end up doing most of the talking. He doesn’t go on the attack nearly as often as I’d like. It’s not until your own arguments and beliefs are challenged that you can really give them an honest look. In the end I just hope I encourage him to think, not only because belief without reason is empty, but because, whatever you believe, thinking about those beliefs is a Good Thing. Too many people in our society are intellectually lazy, so if I can just encourage one person to go home and think, I’ve done my good deed for the day.

PS. I’m also trying to cook up an argument against a God based on the concession that machines can think. It would use the following elements, but I don’t know in what way.

• Humans are a special creation of God, because we can think and we have souls (but animals can’t), therefore thinking and posessing a soul are somehow related.
• Machines can think. (the opponent has to concede this, I know Christians that wouldn’t)
• Machines don’t have a soul.
• Would machines need a God? If so, are we that god? If not, then why do we need a god?

To make things even stronger: Supposing that we make a thinking machine, we would do so taking our inspiration from biology. That is a thinking being is really a noosystem of thoughts fighting amongst each other for control of the entire system. That a brain is a collection of neural nets each specialized for processing a specific thing (center for vision, hearing, motor control, etc.) but with certain amount of leakage current and cross-connection to other neighboring nets. Therefore the thinking machine that we construct would be similar to ourselves in design (dynamic and robust), and would probably work without our knowing explicitly how. But it still wouldn’t have a soul. So why would something so similar to ourselves not have a soul, but we still do? Anthropocentrism.

Today I read TRUE NAMES by Vernor Vinge, as recommended by Andreessen.

It really is a a good novella. I’m am shocked and amazed that it was written in 1984, as it has elements not seen until much later in authors like Charles Stross (Accelerando) and David Brin (Earth). The Afterword (by Marvin Minsky) is also quite good and contains such elements as:

Now it is easy enough to say that the mind is a society, but that idea by itself is useless unless we can say more about how it is organized. If all those specialized parts were equally competitive, there would be only anarchy, and the more we learned, the less we’d be able to do.

I’m also quite surprised that anything written in 1984 about technology would seem very dated and drab by today’s standards, but it remains scant enough on details and strong enough on philosophy that it shall continue to be applicapable for a long time yet.

I was reading Andreessen’s thoughts about Web 2.0 and had a nice thought myself: Wall Street is behind. They have giant festering piles of business and financial logic, and are falling behind on the internet front. What is needed is an internet trading company that can provide free quotes (with better than 20min delay) and insanely low commission rates (because everything’s automated). A company that specializes in accepting trades over the internet through an open API. A company that disdains to doing thigs the old fashioned way. A company that is fully zen with the here and now of the marketplace of ideas.

Even better would be if they acted as a front end to foreign exchanges, thus giving the little guy (ubergeek math heavyweight with a rack of machine at home and algorithms coming out the wazoo) a convenient way to non-stop day trade by transparently moving the trades among the markets. ( Sony is traded on American, European, and Japanese exchanges, so why not trade 24hrs/day? )

A nice Web 2.0 interface would be the main attraction though, and the toughest to get right. People have been trading stocks for a very long time, and everyone does something different in their analysis. The AJAX stock plotting, and automatic signal generation shouldn’t be a stepping stone for the open API, it should in fact replace it. It’s time that we had a web-site that could be user-programmable. And I don’t mean dropping in widgets, I mean full-on IDE.

As a start though, figure out what the majority of traders need, and how best to represent that in GUI, and work from there, providing the trading API so nobody gets left out while the fundamental user-interface research gets done live, the instant-feedback Web 2.0 way.

Also, free registration for a ‘paper’ account, so that users can back-test and familiarize themselves with trading before actually plunking down hard-earned wealth. The free account should do everything except actually trade on the exchanges. It shouldn’t be crippled in any other way.

GStock is wonderful, but they don’t go far enough.

Well, my car battery is died yesterday. It seems that everything in the universe has conspired to attack me this week.

On the plus side, I purchased a set of jumper cables, and an Xpower PowerPack 300 EP. It provides a battery for jump starting a car, an air compressor that would help fix flats, and a power inverter that would conviently run my new laptop for an additional couple hours at the lake.

Nothing like a good excuse for purchasing new tools.

The last routine left us with markings on the bits of the current state. Conveniently, it also left us to the left, while the UTM’s Start state has a loop which moves right to check wether or not a symbol is marked on the simulated tape. We’ll simply modify this loop to clean up after ourselves, and viola!

Weighing in at 17 symbols and 58 states we have some python code and output for a simulation of the (01)* Turing machine.

First: Last weekend I met with a friend and we reviewed this UTM subroutine by subroutine, finding a few errata, which have been fixed.

Finally, we’ve reached the end. The last step of simulation is to find and mark the state with has been copied into the register.
This procedure resembles the find symbol subroutine.

1. Move Right until we find an unmarked Q and mark it with a Q.
2. Move Left and step over the B symbol.
3. Keep moving Left and mark all the 0’s and 1’s.
4. If we hit the B that means all bits have been verified and we can exit the loop; Else, we pick up and unmark the least significant 0 or 1.
5. Move Right until we hit the state we are trying to verify. (it’ll be designated by a Q)
• If the least significant unmarked bit corresponds to the bit we just picked up, then mark it off and return to pick up the next bit.
• If it doesn’t match, then move back erasing marked bits, until we hit the state marker, Q, and unmark it, stepping to the Right so that we’ll pick up the next state in the next iteration of the loop.