« May 2017 | Main

Saturday, June 24, 2017

Cellular Automata Laboratory: Reproduction, Evolution, Abiogenesis, and Sex

The latest collection of rules for Cellular Automata Laboratory (CelLab) illustrates aspects of self-reproduction and analogues to biological systems. Basic self-reproduction is demonstrated by the Langton rule, in which a loop of digital “DNA” provides the instructions to replicate itself and its enclosing structure, creating new identical digital organisms.

Ever since John von Neumann discovered the first self-reproducing cellular automaton rule in 1952, a challenge has been to find simpler and faster-replicating rules. Von Neumann's original rule used 29 states, while Langton, in 1984, simplified this to just 8 states, an initial pattern of 86 cells, and 151 generations to replicate. The latest update to CelLab includes the Byl and Chou-Reggia rules, which further simplify a replicator to (Byl) 12 cells, 6 states, and 25 generations to replicate; and (Chou-Reggia) 5 cells, 8 states, and replication in just 15 generations.

These are all exact replication: every descendant is a precise copy of its ancestor. Biological replication is messier yet more powerful, since it permits evolutionary change and adaptation to the environment. In 1998, Hirokia Sayama published Evoloops, a generalisation of Langton's replicator which allows individual replicators that collide in a world of limited space to mutate, often leading to selection for smaller, faster-replicating organisms not present in the original simulation. Precisely the same phenomenon is observed in bacteria grown with limited resources. Evoloops can also demonstrate abiogenesis: the appearance of replicators from random interactions of non-replicating structures in a “primordial soup”.

In 2007 and 2009, Nicholas Oros further generalised Evoloops to create Sexyloop, which stirs recombination of genetic information, similar to that which occurs in sexual reproduction, into the mix. Now, when digital organisms interact, they can exchange genetic information, so a behaviour which appears spontaneously in one organism can propagate to others, similar to gene transmission in bacterial conjugation and, if adaptive, come to dominate the population.

Run the Byl replicator in CelLab
Run the Chou-Reggia replicator
Run Evoloops evolution experiment
Run Evoloops abiogenesis experiment
Run Sexyloop simulation

Posted at 23:27 Permalink

Tuesday, June 20, 2017

Cellular Automata Laboratory: Langton's Ant

I have added another new rule to Cellular Automata Laboratory (CelLab): Langton's Ant. This rule was discovered by Christopher Langton in 1986, and is one of the simplest known moving-head Turing machine rules which exhibits complex behaviour.

It is a two-dimensional Turing machine with a head (ant) that moves on a map of cells which can be in one of two states. In each generation, the head moves to an adjacent cell, inverting the state of the cell it departs. The head can move in one of the four directions in the von Neumann neighborhood; the direction it moves is set by the current state of the head. Upon moving to a new cell, the head adjusts its direction by turning clockwise if the cell's state is zero and counterclockwise if it is one.

When started with an all-zero map, the head starts by tracing out a lacy pattern exhibiting symmetries, but then, as the pattern grows, appears to be following a random walk, occasionally adding to the borders of the pattern. After around 10,000 generations, however, the head will begin to create a “highway” which extends in a diagonal direction in a cycle of 104 generations. This is an example of spontaneous emergence of order after a long period of apparently chaotic behavior. If run on an infinite map, the highway would extend without bound, but on our wrap-around map, it will eventually collide with the original random pattern, producing interesting interactions. All starting configurations which have been tested eventually produce a highway, but it has not been proved that every possible configuration does so. It has, however, been proved that the pattern always grows without bound in some manner. Try starting the rule on the square pattern and watch how it evolves into a lattice of ordered highways and burl-like intersections.

Run the Langton's Ant rule in CelLab

Posted at 23:09 Permalink

Monday, June 19, 2017

Autour de la Lune: Web Edition Updated

I have just posted an updated version of Jules Verne's 1870 novel Autour de la Lune (Around the Moon). This is the sequel to 1865's De la terre à la lune (From the Earth to the Moon), which left our intrepid explorers apparently stranded in orbit around the Moon.

The present novel picks up the story from inside the projectile moments before it was fired from the giant cannon toward the Moon and recounts their subsequent adventures. As always, Verne does not stint on details, and readers will learn much of what was known in the mid-19th century about selenography. The story is not the classic the original work was, nor does it have the subtext of technology as a modern sacrament, but it is a worthy sequel.

The original version Web version was posted in 2002. This edition updates all of the documents to contemporary Web standards (XHTML 1.0 Strict and CSS3), uses Unicode for text elements such as ellipses and dashes, improves formatting and navigation, and corrects a few typographical errors.

Posted at 20:20 Permalink

Sunday, June 18, 2017

HotBits: New Version with API Keys, Pseudorandom Generation

I have just posted a new version of the HotBits radioactive random number generator Web support software. There are no changes to the actual generation process or hardware, which remain as previously documented. All changes are to the proxy server, which obtains random data from the generators and delivers them to requesters over the Web.

API Keys

The first change is the phased introduction of API Keys, which requesters must use to obtain random data. Since the original introduction of HotBits in 1996, anybody has been able to request random data generated from radioactive decay over the Web, constrained only a quota limiting requests from an IP address to 12,208 bytes or 120 requests, whichever comes first, in any 24-hour period (the quota is applied by an aging algorithm measuring rate, and does not have a hard cutoff on day boundaries). The reason for the imposition of a quota is that the hardware generators produce only around 100 bytes per second, and it would be easy for a user to exhaust this capacity, either inadvertently or in order to wreck the service and deny it to others out of malice.

This policy worked well for more than twenty years, but with increasing blight in the Internet slum, more and more distributed denial of service attacks against HotBits have been mounted over recent months. These are conducted from a multitude of IP addresses, most of which make only one or a few requests, and thereby evade the quota. I do not know the motive for these attacks—probably it's just a nihilistic desire to wreck something provided for free to others; there's plenty of that around on the Internet—no good deed goes unpunished. In any case, this irresponsible behaviour of a few results, as it usually does, in making things inconvenient for the large majority of legitimate users.

Beginning on July 1st, 2017, requests for random data from HotBits will require an API Key, which is either entered in a box in the request page or via an “apikey=key” query field in a direct request URL. Requests without a valid API key will be rejected with an error message. HotBits users can apply for an API Key starting today, by using the:

HotBits API Key Request Form

API Keys are typically issued with two days of being requested. Once you receive your API Key, you can begin to use it immediately with the Request HotBits (API) test page. On July 1st, this will be come the standard request page and an API Key will be required for all requests.

Pseudorandom Data

When you visit the new request page, you'll notice a new option at the bottom: “Pseudorandom data?”. The most common application of genuine random data is to “seed” a pseudorandom number generator which can then produce a large volume of data which passes all of the statistical tests for randomness. HotBits now provides such data without the need for users to set up and validate their own generator. When you check the box, HotBits will return data from its own high quality internal pseudorandom number generator which is seeded from radioactively-generated data from the HotBIts hardware generator. Requests for pseudorandom data do not require an API key and are not subject to quota limitations. You can also request pseudorandom data by specifying “Pseudorandom” as an API Key. Pseudorandom data in the hexadecimal, C, password, and XML formats is identified as such in the result page returned.

The pseudorandom data returned by HotBits are generated with the Mersenne twister algorithm, using the MT19937-64 (64-bit) version. The generator is seeded with 2496 bytes of radioactively-generated random data from the HotBits generators. Because the Mersenne twister algorithm is not cryptographically secure, in that by observing a sufficiently large number of results it is possible to predict subsequent output, the pseudorandom data supplied by HotBits is produced by taking pairs of 64-bit results from Mersenne twister, comprising a 16 byte block, encrypting the block using the Advanced Encryption Standard (AES) with a 256 bit secret key also obtained from radioactively-generated HotBits data, then returning encrypted 16 byte blocks to fill the request. (Multiple blocks are generated if the request is more than 16 bytes, and if the request is not a multiple of 16 bytes, excess bytes from the last block are discarded.) A new AES encryption key is generated every 30 minutes, so even were a key to be disclosed, it would only enable decryption of data returned during the half hour window in which it was in use. Fourmilab makes no claim about the suitability of this pseudorandom data for cryptographic or any other use; that is up to you to determine based upon your own testing of the data and auditing of the algorithms and code used to generate it. Complete source code of the HotBits server, including the pseudorandom generator, will be posted when the new version enters production on July 1st, 2017. Statistical testing of the pseudorandom generator, including the downloadable data sets used in the tests, is currently available.

Posted at 11:45 Permalink

Tuesday, June 13, 2017

Cellular Automata Laboratory: Bootstrap Percolation

Here's another new rule for Cellular Automata Laboratory (CelLab): Bootperc. The rule illustrates the process of bootstrap percolation in statistical mechanics. The rule is started with a random pattern in which some fraction of cells are set to 1 with the others zero. On each generation, zero cells look at their neighbours (either 4 for the von Neumann neighbourhood or 8 for the Moore neighbourhood) and, if the number of nonzero neighbours exceeds a threshold (2 for the 4-neighbour case, 4 for 8 neighbours), become ones. A cell, once set to one, remains forever in that state.

When run, one of two things will happen: either the map will evolve into a number of isolated domains separated by gaps, or else it will percolate—end up with all cells set to 1. Whether this happens is highly sensitive to the initial density of one cells. Below a critical density, the map will almost never percolate, while above it the map will almost always end up all ones. Near the critical density, whether or not the map percolates depends upon details of its initial random configuration. The critical density depends upon the neighbourhood size, and is around 4.5% ones for the four neighbour case and 7.5% for eight neighbours.

Colour is used to trace the waves of percolation, but plays no part in the operation of the rule. Initially set cells are displayed in white and do not change. Newly set cells in each generation are in green, and cells age over a colour gradient from red to dark blue. You can see the percolation front proceeding from each nucleation site as a green wave leaving the rainbow behind it, with the oldest cells in dark blue. If the map completely percolates, the end state will be the white initially set cells on a background of dark blue.

When you run the rule, try stopping it after it has reached a steady state and then use the “Random” button in the Pattern section and its Density field to load patterns with different densities and explore how they behave. The rule is initially set for the eight cell Moore neighbourhood. You can change this by editing the rule program, changing the setting of the vonnN variable, then pressing “Generate” to update the rule.

Run the Bootperc rule in CelLab

Posted at 22:27 Permalink

Monday, June 12, 2017

Reading List: Kindling

Shute, Nevil. Kindling. New York: Vintage Books, [1938, 1951] 2010. ISBN 978-0-307-47417-9.
It is the depth of the great depression, and yet business is booming at Warren Sons and Mortimer, merchant bankers, in the City of London. Henry Warren, descendant of the founder of the bank in 1750 and managing director, has never been busier. Despite the general contraction in the economy, firms failing, unemployment hitting record after record, and a collapse in international trade, his bank, which specialises in floating securities in London for foreign governments, has more deals pending than he can handle as those governments seek to raise funds to bolster their tottering economies. A typical week might see him in Holland, Sweden, Finland, Estonia, Germany, Holland again, and back to England in time for a Friday entirely on the telephone and in conferences at his office. It is an exhausting routine and, truth be told, he was sufficiently wealthy not to have to work if he didn't wish to, but it was the Warren and Mortimer bank and he was this generation's Warren in charge, and that's what Warrens did.

But in the few moments he had to reflect upon his life, there was little joy in it. He worked so hard he rarely saw others outside work except for his wife Elise's social engagements, which he found tedious and her circle of friends annoying and superficial, but endured out of a sense of duty. He suspected Elise might be cheating on him with the suave but thoroughly distasteful Prince Ali Said, and he wasn't the only one: there were whispers and snickers behind his back in the City. He had no real friends; only business associates, and with no children, no legacy to work for other than the firm. Sleep came only with sleeping pills. He knew his health was declining from stress, sleep deprivation, and lack of exercise.

After confirming his wife's affair, he offers her an ultimatum: move away from London to a quiet life in the country or put an end to the marriage. Independently wealthy, she immediately opts for the latter and leaves him to work out the details. What is he now to do with his life? He informs the servants he is closing the house and offers them generous severance, tells the bank he is taking an indefinite leave to travel and recuperate, and tells his chauffeur to prepare for a long trip, details to come. They depart in the car, northbound. He vows to walk twenty miles a day, every day, until he recovers his health, mental equilibrium, and ability to sleep.

After a few days walking, eating and sleeping at inns and guest houses in the northlands, he collapses in excruciating pain by the side of the road. A passing lorry driver takes him to a small hospital in the town of Sharples. Barely conscious, a surgeon diagnoses him with an intestinal obstruction and says an operation will be necessary. He is wheeled to the operating theatre. The hospital staff speculates on who he might be: he has no wallet or other identification. “Probably one of the men on the road, seeking work in the South”, they guess.

As he begins his recovery in the hospital Warren decides not to complicate matters with regard to his identity: “He had no desire to be a merchant banker in a ward of labourers.” He confirmed their assumption, adding that he was a bank clerk recently returned from America where there was no work at all, in hopes of finding something in the home country. He recalls that Sharples had been known for the Barlow shipyard, once a prosperous enterprise, which closed five years ago, taking down the plate mill and other enterprises it and its workers supported. There was little work in Sharples, and most of the population was on relief. He begins to notice that patients in the ward seem to be dying at an inordinate rate, of maladies not normally thought life-threatening. He asks Miss McMahon, the hospital's Almoner, who tells him it's the poor nutrition affordable on relief, plus the lack of hope and sense of purpose in life due to long unemployment that's responsible. As he recovers and begins to take walks in the vicinity, he sees the boarded up stores, and the derelict shipyard and rolling mill. Curious, he arranges to tour them. When people speak to him of their hope the economy will recover and the yard re-open, he is grimly realistic and candid: with the equipment sold off or in ruins and the skilled workforce dispersed, how would it win an order even if there were any orders to be had?

As he is heading back to London to pick up his old life, feeling better mentally and physically than he had for years, ideas and numbers begin to swim in his mind.

It was impossible. Nobody, in this time of depression, could find an order for a single ship…—let alone a flock of them.

There was the staff. … He could probably get them together again at a twenty per cent rise in salary—if they were any good. But how was he to judge of that?

The whole thing was impossible, sheer madness to attempt. He must be sensible, and put it from his mind.

It would be damn good fun…

Three weeks later, acting through a solicitor to conceal his identity, Mr. Henry Warren, merchant banker of the City, became the owner of Barlows' Yard, purchasing it outright for the sum of £5500. Thus begins one of the most entertaining, realistic, and heartwarming tales of entrepreneurship (or perhaps “rentrepreneurship”) I have ever read. The fact that the author was himself founder and director of an aircraft manufacturing company during the depression, and well aware of the need to make payroll every week, get orders to keep the doors open even if they didn't make much business sense, and do whatever it takes so that the business can survive and meet its obligations to its customers, investors, employees, suppliers, and creditors, contributes to the authenticity of the tale. (See his autobiography, Slide Rule [July 2011], for details of his career.)

Back in his office at the bank, there is the matter of the oil deal in Laevatia. After defaulting on their last loan, the Balkan country is viewed as a laughingstock and pariah in the City, but Warren has an idea. If they are to develop oil in the country, they will need to ship it, and how better to ship it than in their own ships, built in Britain on advantageous terms? Before long, he's off to the Balkans to do a deal in the Balkan manner (involving bejewelled umbrellas, cases of Worcestershire sauce, losing to the Treasury minister in the local card game at a dive in the capital, and working out a deal where the dividends on the joint stock oil company will be secured by profits from the national railway. And, there's the matter of the ships, which will be contracted for by Warren's bank.

Then it's back to London to pitch the deal. Warren's reputation counts for a great deal in the City, and the preference shares are placed. That done, the Hawside Ship and Engineering Company Ltd. is registered with cut-out directors, and the process of awarding the contract for the tankers to it is undertaken. As Warren explains to Miss McMahon, who he has begun to see more frequently, once the order is in hand, it can be used to float shares in the company to fund the equipment and staff to build the ships. At least if the prospectus is sufficiently optimistic—perhaps too optimistic….

Order in hand, life begins to return to Sharples. First a few workers, then dozens, then hundreds. The welcome sound of riveting and welding begins to issue from the yard. A few boarded-up shops re-open, and then more. Then another order for a ship came in, thanks to arm-twisting by one of the yard's directors. With talk of Britain re-arming, there was the prospect of Admiralty business. There was still only one newspaper a week in Sharples, brought in from Newcastle and sold to readers interested in the football news. On one of his more frequent visits to the town, yard, and Miss McMahon, Warren sees the headline: “Revolution in Laevatia”. “This is a very bad one,” Warren says. “I don't know what this is going to mean.”

But, one suspects, he did. As anybody who has been in the senior management of a publicly-traded company is well aware, what happens next is well-scripted: the shareholder suit by a small investor, the press pile-on, the back-turning by the financial community, the securities investigation, the indictment, and, eventually, the slammer. Warren understands this, and works diligently to ensure the Yard survives. There is a deep mine of wisdom here for anybody facing a bad patch.

“You must make this first year's accounts as bad as they ever can be,” he said. “You've got a marvellous opportunity to do so now, one that you'll never have again. You must examine every contract that you've got, with Jennings, and Grierson must tell the auditors that every contract will be carried out at a loss. He'll probably be right, of course—but he must pile it on. You've got to make reserves this year against every possible contingency, probable or improbable.”

“Pile everything into this year's loss, including a lot that really ought not to be there. If you do that, next year you'll be bound to show a profit, and the year after, if you've done it properly this year. Then as soon as you're showing profits and a decent show of orders in hand, get rid of this year's losses by writing down your capital, pay a dividend, and make another issue to replace the capital.”

Sage advice—I've been there. We had cash in the till, so we were able to do a stock buy-back at the bottom, but the principle is the same.

Having been brought back to life by almost dying in small town hospital, Warren is rejuvenated by his time in gaol. In November 1937, he is released and returns to Sharples where, amidst evidence of prosperity everywhere he approaches the Yard, to see a plaque on the wall with his face in profile: “HENRY WARREN — 1934 — HE GAVE US WORK”. Then he was off to see Miss McMahon.

The only print edition currently available new is a very expensive hardcover. Used paperbacks are readily available: check under both Kindling and the original British title, Ruined City. I have linked to the Kindle edition above.

Posted at 00:35 Permalink

Sunday, June 11, 2017

Cellular Automata Laboratory: Forest Fire Model

I have just added a new sample rule to Cellular Automata Laboratory (CelLab): Forest, a model of forest fire propagation originally published by Drossel and Schwabl in 1992.

Cells in the map represent either a tree or open ground. Lightning strikes cells at random with a probability f (default 0.00002) on each generation. If lightning strikes open ground, nothing happens, but if it strikes a tree, on the next generation the tree will be on fire. A tree on fire becomes open ground in the next generation. A tree catches fire if any of its eight neighbours is on fire. New trees appear in open ground cells with a probability p (default 0.002).

When the density of trees is low, most lightning strikes empty ground or burns only one or a few trees. As the density of fuel grows over time, the forest becomes susceptible to cataclysmic wildfires which burn large regions. Eventually, you will see lots of small fires and a few very large conflagrations.

The behaviour of the model is highly sensitive to the ratio of the parameters f and p, which you can adjust by editing the top of the evaluator function. Counter-intuitively, reducing the number of lightning strikes increases the number of large fires because it allows fuel to build up which permits the rare fire, once started, to propagate widely. This phenomenon is observed in forestry and is managed by controlled burns.

An age counter is used to display trees in sixteen intensities of green based upon their age in generations, and to make flame fronts fade after they have passed. This is simply to make the display easier to understand; it plays no part in the behavior of the rule.

Run the Forest rule in CelLab

Posted at 13:48 Permalink

Thursday, June 8, 2017

The Time Machine by H. G. Wells: New Web Edition

I have just posted an updated version of the Web edition of H. G. Wells' classic 1895 novel, The Time Machine. This novel (actually, at around 33,000 words, it would be classed as a long novella by contemporary publishers) was originally posted at Fourmilab in 2002. The new edition updates the document to contemporary Web standards (XHTML 1.0 Strict and CSS 3), and uses Unicode text entities for typographic elements such as quotes, dashes, and ellipses.

As I note in the contents page, there were many editions of this work published between 1895 and the last version revised by Wells in 1935. I have based this edition upon the latter work. If you find any errors, please send feedback, but bear in mind that if it's a quibble with words on which the author signed off, I'll go with the latter. Please don't complain about the quote marks. The 1935 edition was published in Britain. British publishers use ‘single quotes’ for the outer level of quotations and “double quotes” for quotations nested within them, while U.S. publishers use exactly the opposite convention. In this edition, I have used quote marks as the author wrote them and his publisher printed them. Because of the story's unusual narrative structure, the main long quotation is carried over from chapter to chapter without a closing quote until the Time Traveller pauses his story in chapter 7 and concludes it in chapter 12: this is as it was in the original.

This is a fine yarn, easily read in one or two sittings, which has much to say about the consequences of eliminating risk and challenges from the lives of people in developed societies. It is much better than the two Hollywood movies loosely based upon it.

Posted at 23:46 Permalink

Tuesday, June 6, 2017

Cellular Automata Laboratory: WebCA Released

In the first major update since 1997, a completely new version of Cellular Automata Laboratory (CelLab) is now available. The cellular automata simulators which previously ran under MS-DOS and Microsoft Windows (and which have ceased to work on recent releases of Windows thanks to Microsoft's trademark strategic incompatibility) and been replaced by a new simulator, WebCA, which is written in JavaScript and runs entirely within the user's browser, using the HTML5 canvas element and associated JavaScript support to display the results of the simulation. Rules, which were previously defined by external programs in languages such as Java, Pascal, C, or Basic, are now defined in JavaScript and compiled directly by the simulator: no external programming environment is required. Custom evaluators, formerly written in assembly language or as a Windows DLL, are now also defined in JavaScript

Many new sample rules have been added, illustrating applications such as billiard ball computing, ecological modeling, emulation of Boolean logic elements, simulation of a spin Ising system, Margolus block rule evaluation, and computational fluid dynamics (the latter demonstrating a cellular automaton with continuous-valued cell state). Source code for all rules and evaluators and the pattern and colour palette files they use are available in a new CelLab Development Kit.

The ability to create self-running demos, or “shows” has been added, and used to build the CelLab Demo, which you can also watch (albeit at lower resolution) on YouTube. A number of other demos are included, which are available on a YouTube playlist.

The manual has been extensively revised, removing the information on the MS-DOS and Windows simulators and documenting WebCA and the new rules and evaluators. Instructions for writing rule definitions and custom evaluators in JavaScript are included. The manual has been updated to current Web standards and typography, and should be easier on the eye.

In order to run WebCA, you need a browser which supports HTML5 canvas and the JavaScript features it requires. Browsers differ substantially in the efficiency of their JavaScript implementations. I have found that the Chrome and Brave browsers provide the best performance, with Firefox and Safari substantially slower but sufficient to run all but the most complicated evaluators.

The links below provide access to the new release and its components.

Posted at 21:04 Permalink

Monday, June 5, 2017

New: Terranova Planet Maker

Since 1995, Terranova has been delivering a planet of the day to visitors on the Web. Now, users with a modern Web browser that supports HTML5 canvas and JavaScript can use Terranova Planet Maker to make their own planets, plus images of cloudy skies and star fields, any time they wish, right within the browser (you don't need to be connected to a server—all computation is done locally). The algorithm used to produce the images is identical to that used by Terranova and can either use randomly-selected parameters or be controlled at a fine-grained level by user settings. Images can be saved to your local machine through the right-click menu available on almost all browsers.

Yes. we're really doing a million-point two-dimensional inverse fast Fourier transform in JavaScript running inside the browser. Progress in JavaScript implementations has been such that on a fast machine and modern browser, you'll hardly notice the generation time.

Posted at 20:53 Permalink