Archive for the ‘Algorithms’ Category.

The Sexual Side of Life

by John H. Conway as told to Tanya Khovanova

Forty years ago, it took about 18 months for us to find the rules that eventually became the Game of Life. We thought in terms of birth rules and death rules. Maybe one day’s death rule would be a bit too strong compared to its birth rule. So the next day at coffee time we’d either try to weaken the death rule or strengthen the birth rule, but either way, only by a tiny bit. They had to be extremely well-balanced; if the death rule was even slightly too strong then almost every configuration would die off. And conversely, if the birth rule was even a little bit stronger than the death rule, almost every configuration would grow explosively.

What’s wrong with that, you might ask. Well, if the “radius” grows by 1 unit per generation, then after 9 or 10 moves, it’s off the (19 by 19) Go board. We can probably find more Go boards, of course, but after another 20 or so moves it will outflow the coffee table and then it is awfully hard to keep track. We wanted to be able to study configurations for much longer than that, which meant that we had to disallow rules that might lead to linear growth. Of course, we weren’t interested in rules that usually led to collapse.

Who were “we”? Well, I was the chief culprit and had an aim in mind — to find a simple set of rules that would lead to a system able to simulate a universal computer. Von Neumann had already shown that this was possible, but his system had 29 states and a very complicated set of rules. The rest of “us” were mostly graduate students who had no higher aim than amusing themselves. Every now and then some rather older colleagues or visitors took an interest.

So my plan was, first, to find a set of rules that almost always prevented explosive growth and catastrophic collapse. Second, I wanted to study it long enough to learn how it could be “programmed”. I hoped to find a system whose rules were much simpler than Von Neumann’s, preferably with only two states (on and off) per cell, rather than his 29.

I’ll just describe the last few rule fiddles. We had in fact given up on finding a two-state system, in favor of one with three states: 0, A, B. State 0 represented an empty cell, and it was natural to think of A and B as two sexes, but we only found their proper names when Martin Huxley walked by and said, “Actresses and bishops!”

Perhaps I should explain this. There is a British anecdote that starts like this:

“The actress sat on the left side of the bed, and removed her stockings. The bishop, on the right side of the bed, removed his gaiters. Then she unbuttoned her blouse and he took off his shirt…”

You are supposed to be getting excited, but it all ends quite tamely, because it turns out that the bishop was in his palace, while the actress was in her bedsit near the theater. There are lots of stories in England about the actress and the bishop, and if a person says something that has a salacious double meaning, it’s standard to respond “as the actress said to the bishop,” or “as the bishop said to the actress”.

Okay, back to Life! To inhibit explosive growth, we decided to imitate biology by letting death be a consequence of either overcrowding or isolation. The population would only grow if the number of neighbors was neither too large nor too small. Rather surprisingly, this turned out to mean that children had to have three or more parents. Let’s see why. If two parents could give birth, then in the figure below, the parents A and B, who are on the border of the population, would produce children A’ and B’ at the next time step, followed by grandchildren A” and B” and so on, thus giving us linear growth!

The Game of Life ExampleSo we moved to threesomes. Children were born to three parents, made up of both sexes. Moreover, the sex of the child was determined by the sex of its parents — two bishops and one actress would give birth to a little actress, while two actresses and one bishop would produce a tiny bishop. This was “the weaker-sex birth rule,” and it was accompanied by “the sexual frustration death rule,” which made death the punishment for not touching somebody of the opposite sex!

However, the weaker-sex birth rule lived up to its name, by being weaker than the death rule. Remember we weren’t interested in rules that led to disappointingly swift collapses, as the actress said to the bishop. Therefore, we strengthened the birth rule by allowing same-sex conception, but again by applying the weaker-sex rule — so that three actresses would produce a bishop or three bishops an actress. However this strengthened the birth rule too much, causing us to apply the death penalty more often.

We decided to apply the death penalty to those who weren’t touching at least two other people, whatever their sex. At first sight it was not obvious that this was stronger than the sexual frustration rule, but in fact it was, because the weaker-sex rule ensured that the sexes were fairly evenly mixed, so if you were touching at least two other people, there was a good chance that one of them would be of the opposite sex.

According to our new set of rules, the sex of parents played no role except to determine the sex of the children, so we abolished sex. After all, according to the bishop, Life without sex is much cleaner.

This is now called the Game of Life and these rules, at last, turned out to be clean and well-balanced.


The Second Doomsday Lesson

DoomsdayOn March 5, 2010 I visited Princeton and had dinner with John Conway at Tiger Noodles. He gave me the second Doomsday lesson right there on a napkin. I described the first Doomsday lesson earlier, in which John taught me to calculate the days of the week for 2009. Now was the time to expand that lesson to any year.

As you can see on the photo of the napkin, John uses his fingers to make calculations. The thumb represents the DoomsDay Difference, the number of days your birthday is ahead of DoomsDay for a given year. To calculate this number you have to go back to my previous post.

The index finger represents the century adjustment. For example, the Doomsday for the year 1900 is Wednesday. Conway remembers Wednesday as We-are-in-this-day. He invented his algorithm in the twentieth century, not to mention that most people who use his algorithm were born in that century. Conway remembers the Doomsday for the year 2000 as Twosday.

The next three fingers help you to calculate the adjustment for a particular year. Every non-leap year has 52 weeks and one day. So the Doomsday moves one day of the week forward in one year. A leap year has one extra day, so the Doomsday moves forward two days. Thus, every four years the Doomsday moves five days forward, and, consequently, every twelve years it moves forward to the next day of the week. This fact helps us to simplify our year adjustment by replacing every dozen of years with one day in the week.

The middle finger counts the number of dozens in the last two digits of your year. It is important to use “dozen” instead of “12” as later we will sum up all the numerals, and the word “dozen” will remind us that we do not need to include it in the sum.

The ring finger represents the remainder of the last two digits of the year modulo 12, and the pinkie finger represents the number of leap years in that remainder.

John made two sample calculations on the napkin. The first one was for his own birthday — December 26, 1937. John was born exactly on Doomsday. I suspect that that is the real reason he called his algorithm the Doomsday Algorithm. The century adjustment is Wednesday. There are 3 dozens in 37, with the remainder 1 and 0 leap years in the remainder. When we add four more days to Wednesday, we get Sunday. So John Conway was born on Sunday.

The second napkin example was the day we had dinner: March 5, 2010. March 5 is 5 days ahead of the Doomsday. The century adjustment is Twosday, plus 0 dozens, 10 years in the remainder and 2 leap years in the remainder. 5 + 0 + 10 + 2 equals 3 modulo 7. Hence, we add three days to Tuesday, demonstrating that we dined out together on Friday. But then, we already knew that.


Turing Tests’ Race

In a Turing test a human judge on one end of an interface interacts with either a computer or another human through this interface. If the judge can’t differentiate a machine from a human, then the computer is said to pass the test. One big goal of folks working in Artificial Intelligence is to build a computer that, when subjected to this test, is indistinguishable from a human.

However, while some people are working hard trying to build programs that can pass as humans, other people are working hard inventing tests that can differentiate between humans and those programs. Such tests are sometimes called Reverse Turing tests. As computer science progresses, the programs that are pretending to be humans as well as reverse tests are becoming increasingly complex.

For example, banks frequently want to prevent malicious computer programs from trying to log into their customers’ accounts. As a nice touch the judges are computers in this case. There are different methods designed to confirm that a human is trying to log in. In one of them a picture of a word, called CAPTCHA is presented on a screen, and the program requires that this word be typed in.

I wanted a CAPTCHA with words “Turing Test” in it for this posting. I looked online trying to find a way to do it. I couldn’t. There is a ton of software that can produce random CAPTCHAs from a dictionary but nothing could do a particular word. Finally, rather than looking for software, I found a human, a kind gentlemen named Leonid Grinberg who with some GIMP help manually implemented a self-referencing ” symbolizing the race between computers and tests.

CAPTCHAAs text recognition software becomes better and better, these CAPTCHAs become more and more difficult to read by a human. The last time I tried to login, I was only able to type the right word on my fourth try. Very soon computers will be better than humans at parsing CAPTCHAs. Humans are loosing the race on visual methods like this one.

Here’s another example. Some malicious software can recognize and capture email addresses on webpages to use for spam. While we don’t want them to recognize email addresses, we do want people to be able to do so. Thus we need a way to present email addresses as a reverse Turing test.

The standard safety recommendation is to avoid writing out the full and exact email address. Here’s an example: billgates AT gmail DOT com. Actually, I think computers are so smart nowadays that they can learn this trick. Another idea is to show a picture of your email address instead of using characters. Here we return to the image idea, which most computers can nowadays recognize.

Another idea of how to hide an email address is to give simple clues, which point to characters in the email address. For example, if you have “4” in your address, you might say that the character is the sum of two and two. I already invented a version of my email address in which each letter of my username is an answer to a simple question. Unfortunately, I think that the question answering systems like Start, as well as its huge new competitor Wolfram Alpha, will learn to answer these questions very soon. I can construct more sophisticated questions, but that would require my readers to spend more time to figure it out including going back to school for a calculus class.

So, recently, I’ve come up with a new idea. I made the description of my email simpler, but the paragraph describing my email didn’t contain all the necessary information:

I have an email account with Yahoo. My account name consists of seven lower case letters: five letters of my first name concatenated with the first two letters of my last name.

People who want to contact me can easily find my name in the title of my webpage or in my url, but I hoped it would take the evil computers some time to figure out what to look for, where it’s located and how to turn it into an address.

The day after I changed my contact web page, I went to my math coaching work at AMSA. During my break, I wanted to unwind by solving a light up puzzle, but it appeared that the new security system at AMSA forbids Internet access to all gaming sites. Thus, being still wound up I decided to do some work and went to my personal page for some materials. I was blocked again. The software politely informed me that access to personal websites was not permitted either. Oops. If a computer can understand that it is a personal website, it probably can figure out the name of the corresponding person. Oops-Oops-Oops. I am loosing the race against computers again. My recent idea to protect my email address from spam lasted one day until my first reality check.


Misunderstanding between Databases

I wrote a story a while ago about how a clerk at my previous job mistyped my resignation date, substituting January 2007 for my real date, January 2008. As a result, my medical insurance provider decided that I wasn’t covered in 2007, and requested that my doctor return the money he had already received.

After several phone calls my medical insurance was reinstated, but I kept receiving bills from my doctor. When I called my insurance, they assured me that everything was fine and that they had paid my doctor. However, my doctor continued to send me bills.

After half a year of phone calls back and forth, someone finally explained to me what was going on. My insurance company had initially requested the money back. The money was never returned to them, because my doctor’s office would not pay them a penny until I had paid the doctor first. In my doctor’s database, my visits were marked as unpaid.

When the problem was cleared up, the insurance company stopped requesting that the doctor pay them back. But the computer at my doctor’s office didn’t understand that stop-the-request command. It didn’t know what stopping the request meant.

The computers were talking different languages and I was caught in the middle.


Propagation Networks: A Flexible and Expressive Substrate for Computation

SudokuMy son, Alexey Radul, made his PhD thesis available to the public.

I was amazed at how much he had invested in the thesis. I assumed that the main goal for a dissertation in computer science is to write a ground-breaking code and that the accompanying text is just a formality. However, this is not the case with my son’s thesis. I am not fully qualified to appreciate the “ground-breakness” of his code, but his thesis text is just wonderful.

Alexey decided that he wanted to make his thesis accessible to a wide audience. He had to make a lot of choices and decisions while he was designing and coding his prototype, and in his thesis he devoted a lot of effort to explaining this process. He also tried to entertain: I certainly had fun trying to solve an evil sudoku puzzle on page 87, that turned out not to have a unique solution.

In addition to everything else, Alexey is an amazing writer.

I am a proud mother and as such I am biased. So I’ll let his thesis speak for itself. Below is the table of contents accompanied by some quotes:

  1. Time for a Revolution

    “Revolution is at hand. The revolution everyone talks about is, of course, the parallel hardware revolution; less noticed but maybe more important, a paradigm shift is also brewing in the structure of programming languages. Perhaps spurred by changes in hardware architecture, we are reaching away from the old, strictly time-bound expression-evaluation paradigm that has carried us so far, and looking for new means of expressiveness not constrained by over-rigid notions of computational time.”

    1. Expression Evaluation has been Wonderful
    2. But we Want More
    3. We Want More Freedom from Time
    4. Propagation Promises Liberty

      “Fortunately, there is a common theme in all these efforts to escape temporal tyranny. The commonality is to organize computation as a network of interconnected machines of some kind, each of which is free to run when it pleases, propagating information around the network as proves possible. The consequence of this freedom is that the structure of the aggregate does not impose an order of time. Instead the implementation, be it a constraint solver, or a logic programming system, or a functional reactive system, or what have you is free to attend to each conceptual machine as it pleases, and allow the order of operations to be determined by the needs of the solution of the problem at hand, rather then the structure of the problem’s description.”

  2. Design Principles
    1. Propagators are Asynchronous, Autonomous, and Stateless
    2. We Simulate the Network until Quiescence
    3. Cells Accumulate Information
  3. Core Implementation
    1. Numbers are Easy to Propagate
    2. Propagation can Go in Any Direction
    3. We can Propagate Intervals Too
    4. Generic Operations let us Propagate Anything!
  4. Dependencies

    “Every human harbors mutually inconsistent beliefs: an intelligent person may be committed to the scientific method, and yet have a strong attachment to some superstitious or ritual practices. A person may have a strong belief in the sanctity of all human life, yet also believe that capital punishment is sometimes justified. If we were really logicians this kind of inconsistency would be fatal, because were we to simultaneously believe both propositions P and NOT P then we would have to believe all propositions! Somehow we manage to keep inconsistent beliefs from inhibiting all useful thought. Our personal belief systems appear to be locally consistent, in that there are no contradictions apparent. If we observe inconsistencies we do not crash—we chuckle!”

    1. Dependencies Track Provenance
    2. Dependencies Support Alternate Worldviews
    3. Dependencies Explain Contradictions
    4. Dependencies Improve Search
  5. Expressive Power
    1. Dependency Directed Backtracking Just Works
    2. Probabilistic Programming Tantalizes
    3. Constraint Satisfaction Comes Naturally

      “This is power. By generalizing propagation to deal with arbitrary partial information structures, we are able to use it with structures that encode the state of the search as well as the usual domain information. We are consequently able to invert the flow of control between search and propagation: instead of the search being on top and calling the propagation when it needs it, the propagation is on top, and bits of search happen as contradictions are discovered. Even better, the structures that track the search are independent modules that just compose with the structures that track the domain information.”

    4. Logic Programming Remains Mysterious
    5. Functional Reactive Programming Embeds Nicely
    6. Rule-based Systems Have a Special Topology
    7. Type Inference Looks Like Propagation Too
  6. Towards a Programming Language
    1. Conditionals Just Work
    2. There are Many Possible Means of Abstraction
    3. What Partial Information to Keep about Compound Data?
    4. Scheduling can be Smarter
    5. Propagation Needs Better Garbage Collection
    6. Side Effects Always Cause Trouble
    7. Input is not Trivial Either
    8. What do we Need for Self-Reliance?
  7. Philosophical Insights

    “A shift such as from evaluation to propagation is transformative. You have followed me, gentle reader, through 137 pages of discussions, examples, implementations, technicalities, consequences and open problems attendant upon that transformation; sit back now and reflect with me, amid figurative pipe smoke, upon the deepest problems of computation, and the new way they can be seen after one’s eyes have been transformed.”

    1. On Concurrency

      “The “concurrency problem” is a bogeyman of the field of computer science that has reached the point of being used to frighten children. The problem is usually stated equivalently to “How do we make computer languages that effectively describe concurrent systems?”, where “effectively” is taken to mean “without tripping over our own coattails”. This problem statement contains a hidden assumption. Indeed, the concurrency itself is not difficult in the least—the problem comes from trying to maintain the illusion that the events of a concurrent system occur in a particular chronological order.”

    2. Time and Space

      “Time is nature’s way of keeping everything from happening at once; space is nature’s way of keeping everything from happening in the same place ( with apologies to Woody Allen, Albert Einstein, and John Archibald Wheeler, to whom variations of this quote are variously attributed).”

    3. On Side Effects
  8. Appendix A: Details

    “I’m meticulous. I like to dot every i and cross every t. The main text had glossed over a number of details in the interest of space and clarity, so those dots and cross-bars are collected here.”


Contact Me

I enjoyed a recent discussion on the sequences fans mailing list. David Wilson suggested an idea for hiding email addresses on webpages from bots: change your email slightly and explain how to change it back.

For example, if you want to contact me, you should reverse my login name in the following email address:

Or, remove all the digits from the following email address:


Frog Puzzle

FroggerThis puzzle was brought to me by Leonid Grinberg.

A frog needs to jump across the street. The time is discrete, and at each successive moment the frog considers whether to jump or not. Unfortunately, the frog has crappy eyesight. He knows there are dangerous cars out there, but he can’t see them. If a car appears at the same moment that he decides to jump, he will die.

The adversary sends cars, hoping to kill the frog. The adversary knows the frog’s algorithm, but can use only a finite number of cars. The frog wants to maximize his chances of survival with his algorithm. The frog is allowed to use a random number generator that the adversary can’t predict. Can you suggest an algorithm for the frog to cross the street and survive with a probability of at least 1 − ε?


Unrevealing Coin Weighings

In 2007 Alexander Shapovalov suggested a very interesting coin problem. Here is the kindergarten version:

You present 100 identical coins to a judge, who knows that among them are either one or two fake coins. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.

You yourself know that there are exactly two fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly two fake coins without revealing any information about any particular coin?

To solve this problem, divide the coins into two piles of 50 so that each pile contains exactly one fake coin. Put the piles in the different cups of the scale. The scale will balance, which means that you can’t have the total of exactly one fake coin. Moreover, this proves that each group contains exactly one fake coin. But for any particular coin, the judge won’t have a clue whether it is real or fake.

The puzzle is solved, and though you do not reveal any information about a particular coin, you still give out some information. I would like to introduce the notion of a revealing coefficient. The revealing coefficient is a portion of information you reveal, in addition to proving that there are exactly two fake coins. Before you weighed them all, any two coins out of 100 could have been the two fakes, so the number of equally probable possibilities was 100 choose 2, which is 5050 4950. After you’ve weighed them, it became clear that there was one fake in each pile, so the number of possibilities was reduced to 2500. The revealing coefficient shows the portion by which your possibilities have been reduced. In our case, it is (5050 − 2500)/5050 (4950-2500)/4950, slightly more less than one half.

Now that I’ve explained the kindergarten version, it’s time for you to try the elementary version. This problem is the same as above, except that this time you have 99 coins, instead of 100.

Hopefully you’ve finished that warm-up problem and we can move on to the original Shapovalov’s problem, which was designed for high schoolers.

A judge is presented with 100 coins that look the same, knowing that there are two or three fake coins among them. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.

You yourself know that there are exactly three fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly three fake coins, without revealing any information about any particular coin?

If you are lazy and do not want to solve this problem, but not too lazy to learn Russian, you can find several solutions to this problem in Russian in an essay by Konstantin Knop.

Your challenge is to solve the original Shapovalov puzzle, and for each solution to calculate the revealing coefficient. The best solution will be the one with the smallest revealing coefficient.


Propagation Networks

My son Alexey Radul defended his PhD thesis on Propagation Networks on August 4. Here is the abstract.

I propose a shift in the foundations of computation. Modern programming systems are not expressive enough. The traditional image of a single computer that has global effects on a large memory is too restrictive. The propagation paradigm replaces this with computing by networks of local, independent, stateless machines interconnected with stateful storage cells. It offers great flexibility and expressive power, and has therefore been much studied, but has not yet been tamed for general-purpose computation. The novel insight that should finally permit computing with general-purpose propagation is that a cell should not be seen as storing a value, but as accumulating information about a value.

Various forms of the general idea of propagation have been used with great success for various special purposes; perhaps the most immediate example is constraint propagation in constraint satisfaction systems. This success is evidence both that traditional linear computation is not expressive enough, and that propagation is more expressive. These special-purpose systems, however, are all complex and all different, and neither compose well, nor interoperate well, nor generalize well. A foundational layer is missing.

I present the design of a general-purpose propagation system. I illustrate on several examples how the resulting prototype supports arbitrary computation; recovers the expressivity benefits that have been derived from special-purpose propagation systems in a single general-purpose framework, allowing them to compose and interoperate; and offers further expressive power beyond what we have known in the past.


Langton’s Ant’s Life

Langton’s ant travels on the infinite square grid, colored black and white. At each time step the ant moves one cell forward. The ant’s direction changes according to the color of the cell he moves onto. The ant turns 90 degrees left if the cell is white, and 90 degrees right if the cell is black. After that, the cell he is on changes its color to the opposite color.

There is a symmetry of time and space for this ant. If at any point of the ant’s travel, someone interferes and reverses the ant’s direction in between the cells, the ant and the grid will traverse the steps and stages back to the starting point.

Let’s give this ant a life. I mean, let’s place him inside the Game of Life invented by John H. Conway. In addition to the Langton’s ant’s rules, I want the cells to change colors according to the rules of the Game of Life.

Let me remind you of the rules of Conway’s Game of Life. We call black cells live cells and white cells dead cells. Black is life and white is death. The cell has eight neighbors — horizontal, vertical, diagonal. At each time step:

  • A cell dies of agoraphobia, if it has more than three neighbors.
  • A cell dies of boredom, if it has less than two neighbors.
  • A dead cell can be born again, if it has exactly three neighbors.
  • Otherwise, the cell’s status doesn’t change.

So, our ant will be traveling in this dying and reproducing population and correcting nature’s mistakes. He revives dead cells and kills live cells.

There is an ambiguity in this ant’s life description. The life can happen at two different moments. In the first ant’s world, the ant jumps from one cell to the next, and while he is in the air, the cells have time to copulate, give birth and die. Upon landing, the ant changes direction and uses his magic wand to change the life status of its landing cell. In the second ant’s world, the ant moves to the destination cell, changes its own direction and the status of the cell and then takes a smoke. All the fun, sex and death happen while he is enjoying his cigarette.

The ant’s life has symmetry in a way that is similar to the symmetry of the ant without life. If we reverse the ant’s direction back and also switch his life-style from the first to the second or vice versa, then the ant and the grid will go backwards in their states.

The parameters for the Langton’s ant were chosen to make the ant’s behavior interesting. The parameters of the Game of Life were chosen to make the Game of Life’s behavior interesting. To make the ant’s life fascinating, we might want to modify the ant’s behavior or the Life’s rules. The synergy of the ant and the Life might be intriguing only if the ant changes its behavior and the Life changes its rules.

Let’s experiment and discover how we need to change the rules in order to make the ant’s life interesting.