Monomorphic

Flood-it, a color filling game. This version was made by Lab Pixies for the iPhone, but many others exist.

There’s a veritable torrent of little games constantly being released for the iPhone. One of the more likable ones is Flood-It, which I’ve been playing recently. The premise is extremely simple: you start off with a grid divided into squares of different, randomized colors. You are given a tool that works a bit like the bucket fill in a picture editor. At each turn, the player chooses a color to fill the grid with, starting from the upper left corner. The monochromatic area slowly grows, and the aim is to fill the entire grid with a single color within a limited number of turns.

A recent analysis showed that finding an optimal solution to games like Flood-It is a NP-hard problem. In addition, deciding whether the game can be solved in n steps for some n is NP-complete. The analysis relies on a reduction of Flood-It to an instance of the SCS problem (shortest common superstring). (It’s important to note that what is NP-complete is deciding whether a particular board can be solved in a certain number of steps, not solving the game with a bounded number of steps. This can be done in polynomial time.) For those who need a summary, ACM Communications had an excellent review of the state of the P/NP problem in September last year.

For a NP-hard problem H, there exists a polynomial time reduction of any problem in NP to H, meaning that if we can solve H in P-time, we can solve any problem in NP in P-time. Many optimization problems in society rely on approximate solutions to difficult problems: routing traffic, assembling DNA sequences from partial subsequences, mathematical theorem proving… On the hypothesis that evolution has turned people into efficient solvers of hard problems (i.e. we have good heuristics in our brains from birth and from experience), we ought to pay people to play these games on their phones, but map real problems into game instances, so that people effectively work while they’re playing. We ought to design games that act as front-ends for real combinatorial problems.

A computer game, as we understand it, can be defined as a very smooth learning curve, and if we only “play” very tricky instances of combinatorial problems, the game would probably present too much of a barrier to new players. So maybe the best way of executing this kind of scheme would be that a majority of all game instances do not represent real problems, but mere training or verification of already solved problems — but every once in a while, a real problem pops up. The player should still get paid though.

A double benefit would be blurring the line between work time and  play time, what is useful and what is useless — I think this line is often artificially constructed. Has technology ever before given us the possibility to literally turn work into play?

Acknowledgements. I am indebted to Christian Sommer for showing me the complexity analysis of Flood-it.

The Flood-It game, easy difficulty setting, with the player having made some progress.

In the Japanese summer, minor cockroach infestations are common. Every pharmacy makes a fortune selling a wide variety of cockroach repellents, traps and poisons.

Cockroaches are interesting from an evolutionary point of view. They are inherently passive and defensive in their approach to life. When danger threatens, they run to the darkest possible place. They seem to  eat whatever is left over by larger animals. It is sometimes said that they would be the only species to survive nuclear fallout. But it turns out other insects, like the fruit fly, have a much higher radiation resistance.

Maybe cockroaches have some similarities with mold, then. Possessing minimal initiative, they are like a chemical reaction of nature that sets in wherever there is some energy gain to be had by consuming and breaking down some leftovers. Their boundary can be pushed away, but banishing them from the surface of the earth would be an impossible feat (and probably undesirable).

Sometimes it is suggested that these days, there is an ecosystem of ideas – “memetics”. Surely, in this ecosystem too, there are large and small “animals”. Animals that feed selectively, and animals that eat just about anything (that is, ideas that can take root in just about any sort of mind). Animals that take initiative and seek to change their environment, and animals that only react, only defend, only hide in the dark.

In daily life, we must be careful so as to not fall prey to the small ideas that hide in the dark. Seek out the large beasts, and hunt them in the light of day.

The Guardian reports that a new government panel will henceforth judge what research is worthy of funding in the UK. Universities will have to make the case for their research projects in order to receive money. Reuters UK, perhaps keen to draw attention, blurt out that “‘Mickey Mouse’ degrees face [a] funding battle”.

Examples cited by Reuters UK include surf science, golf management and winemaking. I agree that these are probably vocational qualifications rather than fields meriting university study. But for blue skies projects in the natural sciences or the humanities, the payoff and effects on society are very hard to judge in advance. After all, we very often conduct the research precisely to evaluate these benefits.

The incentive situation with basic research is different today from what it was during the cold war era. When basic research was a national affair, not to be shared freely in the scientific community, it was probably possible to gain a national advantage by investing more in basic research. Today it’s all too easy to make the argument that other countries will reap the benefits, so why pay for the investment? Essentially a reverse prisoner’s dilemma: out of selfishness, you are tempted not to invest, but everybody benefits more if everybody invests. But surely this is too simple a view of the situation.

Where will countries that cut down on basic research be in the league tables of the future?

I’m currently in Sweden, enjoying the Scandinavian nature, catching up with family and a few old friends.

This time, some quick notes on a few ideas that have been brewing.

Orthopraxy is when people do things the same way: “correct” action/praxis. On Artima developer spotlight, there was a lively discussion on this in the Ruby community: is Ruby a language that is less patronizing to the programmer than many other languages? That is, does it enforce orthopraxy to a lesser extent than other languages? In very established languages such as Java, orthopraxy does not just come from language design though; it comes from the culture surrounding the language. Today it is so mature that there is a very small number of accepted styles and accepted ways of coding. This does make people more productive by easing communication, but I wonder if we could have both ease of communication and stylistic freedom…?

Garbage collection in society is the collection of discarded resources: entropy has gone so far that we banish used up objects to a heap of rubbish. Some of these may be immediately recyclable, most of them will take a long time to disintegrate fully. In software, garbage collection is about reclaiming the space used by lost objects that can no longer be used by the program. As such it’s more about recycling – all the memory is reused pretty much instantaneously. The trick here is finding those lost objects and putting the memory to use in a good way. Finally, in life, when plants or animals die, they become part of new plants and animals in a normal ecosystem. Isn’t this garbage collection on a molecular/atomic level? Maybe even as high as on the protein level.

Actor programming in Scala is something I casually started experimenting with for a text processing tool, and it turned out to be a very pleasant way of doing parallel computation. The asynchronous message queues were a much nicer way of doing things than the conventional monitor/mutex methods. I recommend trying to use it for something. In Scala they can equally easily be made threadless (usually each runs on its own thread), making support for a huge number of actors trivial.

I have something of an engineering background, so I easily end up thinking of success in terms of quantity. Maximizing this variable or that. Ensuring the greatest possible reward, or the smallest possible cost. But sometimes this is fallacious thinking.

As an academic, I would like to publish prestigious articles. It would be nice to publish 10 papers at second or third rate conferences, but they might all be made irrelevant by a single article at a first rate conference (or even an article in Nature or Science, say). So quality is a better measure than quantity.

I would also like to come up with new and influential ideas, but I suspect I would probably be happier if I managed to influence 10 very highly regarded people than if I managed to influence 10 000 laymen. (These exact numbers were computed using the “wild guess” algorithm and further evaluation may be needed.)

In professional life, I’ve found it dangerously easy to fall into a mode of thinking where you evaluate yourself by your income. This is true up to a point, but I’ve found that there’s a point beyond which additional income has diminishing returns in terms of how much it adds to my overall rewards from life. So beyond this point, quality is a better measure than quantity. What are my tasks, how do they force me to learn and evolve, what kind of satisfaction do I feel and why? So quality is a better measure than quantity.

User satisfaction with computer software can, to some extent, be measured using response time and latency. A snappy, responsive user interface usually produces more satisfaction than a sluggish one. But this can often be compensated for to a surprising extent by having appropriate progress indicators, animations and design features that placate the user in some way, assuring them something is being done. This is in a sense the opposite of the money situation: up to a certain point, quality makes up for quantity, after that point (when the slowness becomes impossible to mask), quantity becomes increasingly important.

What’s most interesting is perhaps the convertibility between quality and quantity. In engineering a device or a software system, quantitative metrics can be crucial tools in the construction process, but the final user experience must be qualitatively right. So quantity is a tool to construct quality. And in the real life situations where quantity is actually the best measure — bargaining, comparing, communicating, constructing, … — I think of it as a way to mask qualities. The numbers are simply easier to consider than the vast number of qualities that lie underneath.

Today an oppressive, passivizing heat covers Tokyoites like a massive woollen blanket. Summer is here. In a feeble attempt to defy the heat, I follow up on my previous post on languages and automata.

That post ended with the suggestion that we can apply these concepts to interactions in society. But can we? As a starting point, let’s think about stateless and stateful interactions in a system. Stateful interactions involve a change of state, in some sense. Stateless interactions involve no such change. What counts as stateful depends very much on how detailed the model is – these might be examples:

• You make a purchase in a convenience store – the obvious changes of state are the balance in your wallet/bank account, the amount of items you possess/carry with you, and the corresponding opposite changes on behalf of the store.
• You greet somebody you know on the street and exchange some small talk. Even though no actionable information is exchanged, you both feel happier afterwards and in a better mood because you were acknowledged by someone else. This is a change of state. The precondition is that you are in a state where you know the other person – this interaction would not be possible with a random person in a random state. (On a different level, a typical such exchange goes through at least three discrete states in itself – “greeting”, “exchange of information”, “goodbye”).
• You go to your job in an office, read some documents, write some reports and leave. We can think about the wear and tear on the furniture and the building, the carbon dioxide-oxygen exchange in the air, and the changes to your company’s total body of information as changes of state. Which to choose depends, again, on the model.

Are there any stateless interactions then? Within the context of a particular model, yes. If we only care about monetary and material transactions, the meeting on the street might be stateless. If we only care about “mood” states, the purchase in the store might be stateless, and the office job might have a negative effect on accumulated mood.

In software engineering, we always try to hide state as much as possible. State makes the system far harder to understand and reason about.  We like immutable objects, whose state never change. If we look at reality through abstractions, maybe such things can exist, but in the physical world I don’t believe they do (I’d have to ask a physicist to know the answer though).

The most complex interactions in society, I think, take place among people and organisations that have long lasting relationships. These entities can modify each other’s state over a long period of time. If I’ve known somebody for years, there’s a very large number of possible states a conversation with that person might be in, a large number of topics I might possibly bring up and discuss. But the limitations of societal norms and my own knowledge imply that a conversation with a stranger might be a very small state machine indeed. (On the other hand, maybe this is why getting to know a new person can be very satisfying – the newness of building a new structure from scratch in your head to represent this person’s states). Companies that interact with customers in short, anonymous relationships almost never present them with complex interactions (convenience stores, taxi drivers). With other companies we have more complex interactions and longer relationships (doctors, banks).

These transitions of state are, again, like words that make up sentences in formal languages. We all live these languages every day. How many states do you have?

Computing is very new as a science. Blaise Pascal devised a mechanical calculator in 1645, but Charles Babbage’s analytical engine, widely considered the first programmable computer, was not conceived of until the mid-19th century. However, it was never constructed (unlike Babbage’s simpler “difference engine”), and even at this time there was almost no theory to go with the invention. Today, the fundamental abstractions of computing and programming are Turing machines and Lambda calculus, described in the 1930’s. So essentially, the theory has had less than a century to mature, and is being viewed by many as a branch of mathematics.

The newness of computing means that we don’t know that much about its role or its applicability outside of devices built specifically for computing, nor do we know if today’s fundamental computing abstractions are the best ones.

Languages and automata are two of the most fundamental ideas in computing. In contrast to human languages, which are informal and rather unsystematic, in computing we often speak of formal languages. Something like the following is an example of a formal grammar:

• Sequence-list: Sequence [ Sequence-list ]
• Sequence: Wake up Action-list Have lunch Action-list Go to sleep
• Action-list: Action [ Action-list ]
• Action: Work | Answer the phone | Attend meeting | Relax

Using this grammar we can model the life of an office worker. We can generate an infinite list of potentially infinitely long “sentences”. The following are examples of valid sentences in the grammar:

• Wake up, Work, Have lunch, Attend meeting, Go to sleep
• Wake up, Work, Have lunch, Work, Go to sleep, Wake up, Work, Have lunch, Work, Go to sleep
• Wake up, Answer the phone, Answer the phone, Answer the phone, Have lunch, Work, Go to sleep

A grammar such as this has a 1-1 correspondence with what is known as a deterministic finite automaton (DFA) – a very simple building block of software and hardware models. A formal grammar like the above is in a sense just a more natural way of thinking about a DFA.

What is the applicability of formal languages outside computing hardware and software?

For one thing, we see them in nature, not least in ferns, which on a miniature level appear to have used the same rules as on the macro level. We see them in trees and flowers. In fact, the formal language paradigm appears to be a very good fit for many natural phenomena. One reason for this might be that formal languages allow rich structures to be constructed from a very small description.

One idea I find fascinating is trying to apply these models to human society: people and institutions. Can we describe the interactions in society as automata and formal languages, and if so, what can we learn about them?

We’ve now had just over a decade of truly mainstream access to and use of the internet. I think I personally took my first stumbling steps on the web around 1995-1996. At the time, it was a limited phenomenon, rife with poor design. It was hard to see what was eventually going to come out of that. And even today, it’s hard to see what today’s internet will eventually evolve into.

If it wasn’t clear before, the events of the past week have made it clear that the internet is a valuable tool for democracy. When everybody can broadcast to everybody else, as opposed to just a select few broadcasting, it’s difficult to control the information flow. Repressing select bits of information becomes hard – the repression just results in the information getting more attention. In the aftermath of Iran’s elections, it seems one of the most important communication channels for protesters was Twitter.  The situation is being likened to Tiananmen square. Together with everybody else, I could follow #IranElection as the events unfolded. It went to the point where the US State Department asked Twitter to delay upgrades in order to keep the service operative, supposedly because of Twitter’s importance in Iran.

I don’t know enough about the candidates to take sides in Iran, but I think one of our fundamental principles should be that nobody should seek to rule by repressing communication. Today, the Internet is a free communications device that anyone can use. How long will it stay this way? When legislators seek to clamp down on the Internet’s uncontrolled nature and regulate it for one reason or another, we should protest. Unrestricted mass communication for everyone is too important an invention to give up.

For those who read Swedish, Rasmus Fleischer has written a brilliant post on the events from a philosophical-historical perspective.

Micropayments are an old idea.

Examples of services using something that might be called micropayments today are Apple’s App Store (for the iPhone), Sony’s Playstation Network, various MMORPGs, etc. However the typical payment sizes are still quite large:  the smallest possible payment on the App Store is 100 yen (1 dollar). With even smaller payments, say around the value of 0.001 dollars or less, a new range of possibilities is opened up. For those who worry about payment costs, it will probably soon be economically feasible to make payments in the order of 1 millionth of a dollar, given that network costs, processing costs, and storage costs go down all the time – the economics of electronic payment are really changing. Fraud is probably a much bigger hurdle to overcome.

My case for micropayments is about derivative works. I’m not sure what copyright laws will look like in the future, but it is likely that payments and some kind of monetary system will remain in the picture. With the rise of the internet and various kinds of legal and quasilegal file sharing (the American term “fair use” might apply here), a certain kind of derivative work has proliferated. Songs being remixed, music videos being created by fans on Youtube (usually consisting of the song in its original form and fan-made footage), memes floating around. The available technology eases the process of creating derivative works massively.

The existing legal framework was clearly not designed for this. As an amateur musician, I sometimes make music. Once, several years ago, I wanted to sample a tape recording made by Andy Warhol and use it as part of one of my works. After having e-mailed the Andy Warhol Museum, I was told that a written agreement would have to be set up with the Andy Warhol estate. (I have never made a penny from my recordings; they are made strictly for my own amusement, so there was no benefit for me in going through with a cumbersome process). Different countries have different sampling laws, for instance in Sweden sampling something like 10 seconds for use in your own music is allowed without prior agreement. However, the point here is that with a sufficiently advanced major micropayment system, this process could be made much smoother.

Consider completely original works, their derivative works, derivatives of the derivatives, and so on for a certain number of steps. In mathematical terms, this forms a graph (or rather a tree/DAG), branching out and connecting all the included and indirectly included items. With micropayments, it might be possible to pay the creators of each included work automatically by sending money down these connections, slightly reducing the payment amount on each depth level. (The hard thing here is determining the amount to pay and the reduction amount on each step – this would depend on how much the included work has been changed and how prominent it is, among other things). All of this should be fully automatic.

With such a system in place, anyone could sample anything at any time without worrying about legal agreements. Creators might receive a very large number of possibly very small payments. It’s unclear if the final payment distribution would be different from today, but I’m convinced that more derived works would be created.

However, it’s an open question whether these payments always have to be monetary. Can we envision other compensation systems for the digital world (which do not convert to cash)?

Computers are connected to people, and to the physical world, through input/output devices. These are not just keyboards, mice, monitors, printers etc, but also various sensors, e.g. temperature, light, movement sensors and video cameras, and output devices like industrial control systems or robots. Every day, we increase the extent of what computers can observe, and what they can affect.

Computers are also more connected to each other, thanks to the internet. So now, by virtue of being connected to computers, physical objects are becoming indirectly connected to each other more and more. One of the consequences of this is that physical objects can manipulate other physical objects in different ways, even when they are far away or otherwise unrelated to the sending object. In other words, the internet is converging with the physical world. This is sometimes called the internet of things.

An example: The Nabaztag is a rabbit like internet connected object that has many novel ways of interacting with its environment. However, it’s an artificial object created for this purpose – the real changes are when conventional objects around us become connected unexpectedly. The Economist has an article about what happens when cars become connected. Quote from the article:

“We can stop looking at a car as one system,” says Rahul Mangharam, an engineer at the University of Pennsylvania, “and look at it as a node in a network.”

In preparing for the future, it would be prudent to anticipate a world where things are interconnected even more strongly today. I can think of several problems and opportunities that would arise in such a world:

• Safety, ownership and security become much more important. Today buildings and property are protected by locks and physical barriers. What happens when the weakest link in a security chain is a bit switch in computer memory? (We already have this in many situations today, but those systems tend to be less connected. The pressure to be more connected will turn those bit switches into greater risks.)
• Privacy and anonymity on one hand, versus openness and identification on the other, will acquire even more importance. I expect we will have the ability to control in great detail what information we want to reveal about ourselves and our objects, and to whom and what. For instance, there are experiments with software to accumulate footage from many different CCTV cameras and reconstruct a realistic three-dimensional model of physical reality. There are as many exciting applications as there are dangerous ones (from a surveillance state perspective).
• Completely unrelated objects might be linked to each other in interesting ways by their owners. I might set up a Rubik’s cube so that entering a particular combination on its faces makes my computer decrypt a hidden file (maybe this isn’t very good from a security perspective). The color and intensities of highway streetlights might change dynamically depending on where the cars are. Depending on whether my friends did something interesting today (found out by observing, for instance, their twitter feeds), I might want the speed dial numbers to appear in a different order on my phone. (The system could also try to figure out which friends I might be likely to contact based on my own actions).

But these are all trivial examples.

A related, but different (as I understand it) topic is being researched by Neil Gershenfeld at the MIT Media Lab. They call it “bringing the programmability of the digital world to the physical world”. This seems focussed on creating programmability without conventional computer equipment. If brought to fruition, it might have some consequences in common with increased connectivity.

Indubitably, these questions will enter mainstream politics increasingly in this century. Ideally, the necessary debates will be informed ones, and held early rather than at the last minute when faced with crises.

Image by Great Beyond. Some rights reserved (CC).