Month: April 2013

Researchers at the Universidad Carlos III de Madrid (UC3M) and the Universidad Complutense de Madrid (UCM) have discovered a phase shift between chaotic states that can appear in herds of animals and, in particular, in swarms of insects. This advance may help to better understand their behaviour or be applied to the study of the movement of cells or tumors.

A phase shift occurs when the conditions of a system change drastically, for example, when water changes from a liquid to a solid statewhen it freezes. In this research, recently published in the journal Physical Review E, this group of mathematicians has found such a phenomenon in swarms. Related research is also available on the arXiv preprint server.

“The insects in the swarm stay in a limited volume, even if they’re in a park or an open space. To explain this, we assume that there is a harmonic potential, a kind of recuperative force that confines them (like that of a spring that tries to return to its resting position when we stretch or contract it),” explains one of the study’s authors, Luis L. Bonilla, director of UC3M’s Gregorio Millán Barbany Institute.

This confinement of the insects responds to a constant of proportionality between force and displacement. Researchers have found that for low confinement values, the movement of the insects in the swarm is chaotic (their movements change a lot if the initial conditions are changed). In this context, the phase shift occurs when the swarm splits into several swarms that are, however, closely related to each other, because there are insects moving from one to another.

At the critical line between phases of this shift, the distance between two insects in the swarm that are influenced by each other is proportional to the size of the swarm, even if the number of insects in the swarm grows indefinitely. This is called “scale-free chaos” and hasn’t been discovered until now, according to the researchers.

“As the number of insects increases, the critical line moves towards zero confinement. What happens is that the maximum distance between two insects that still feel each other’s influence is proportional to the size of the swarm. It doesn’t matter how many insects we put in it. And that represents an absolute novelty that we have discovered,” explains Bonilla.

Specifically, what these mathematicians predict through numerical simulations is that certain swarms of insects (specifically a class of small flies) have scale-free chaotic behaviour, which translates into certain power laws with exponents similar to those measured in nature. They have also found a simplified mean-field theory that corroborates the scale-free chaos phase shift. “It would be good to look for and find the phase shift between chaotic phases that we predict, either in observations in nature or in controlled laboratory studies,” says another of the authors of the research, UCM mathematician Rafael González Albaladejo, who is also linked to UC3M’s Gregorio Millán Barbany Institute.

The formation of herds is one of the manifestations of so-called “active matter,” made up of something like self-propelled individuals that form a whole, the researchers explain. It can be a swarm of insects, a flock of sheep, a flock of birds, a school of fish, but also bacteria in motion, melanocytes (the cells that distribute pigments in the skin) or artificial systems such as periodically shaken irregular grains or seeds. “Herd formation mechanisms play a role in some of these systems, so the results we have obtained can be linked to biology, to the study of cells, and beyond that, to the study of tumors and other diseases,” adds Albaladejo.

How do so many animals move in unison? These researchers explain that each individual only senses its neighbours and moves accordingly, even though it has no perspective on the movement of the whole herd. And depending on whether they use sight, hearing or the vibrations of the fluid in which they are immersed, the concept of neighbour can change quite a bit.

Sheep moving together see and sense those around them, while birds in a flock see their nearest neighbours, even if they are quite far apart. “Moving accordingly may mean that they move in the same direction as their neighbours (the norm) or they may adopt different strategies depending on the situation. For example, if a crowd is trying to get out of a crowded pen with more than one gate, there are times when not following neighbours is advantageous,” they explain.

It has taken the mathematicians about two years to carry out this research work. Initially, they set out to explain experiments by studying the conventional phase shift between a crowd of insects that fill a space with constant density and become ordered when passing a critical value of the control parameter (e.g., by decreasing the noise). But then they decided to add a harmonic potential to confine the swarm and explore what happens when the attractive force between individuals decreases.

“We discovered many periodic, quasi-periodic and finally chaotic states for a fixed number of insects that we increased. The surprising thing is the transition between chaotic states that we didn’t know or assume existed, and we were able to find the correct arguments and tests to support their existence,” says another of the study’s authors, Ana Carpio, from UCM’s Department of Mathematical Analysis and Applied Mathematics, who points out that there is still a lot to be done based on this work.

“From experimentally seeking confirmation of our predictions and better adapting the model to experimental observations, to carrying out theoretical and mathematical research that goes beyond our numerical simulations,” she concludes.

For more such insights, log into our website https://international-maths-challenge.com

Credit of the article given to Carlos III University of Madrid

Momentum is gathering behind calls to pardon the father of computer science. BinaryApe

You may have read the British Government is being petitioned to grant a posthumous pardon to one of the world’s greatest mathematicians and most successful codebreakers, Alan Turing. You may also have read that Turing was was convicted of gross indecency in 1952 and died tragically two years later.

But who, exactly, was he?

Born in London in 1912, Turing helped lay the foundations of the “information age” we live in.

He did his first degree at King’s College, Cambridge, and then became a Fellow there. His first big contribution was his development of a mathematical model of computation in 1936. This became known as the Turing Machine.

It was not the first time a computer had been envisaged: that distinction belonged to Charles Babbage, a 19th century mathematician who designed a computer based on mechanical technology and built parts of it (some of which may be seen at the Science Museum in London or Powerhouse Museum in Sydney, for example).

But Babbage’s design was necessarily complicated, as he aimed for a working device using specific technology. Turing’s design was independent of any particular technology, and was not intended to be built.

The now iconic shot of Alan Turing.

It was very simple, and would be very inefficient and impractical as a device for doing real computations. But its simplicity meant it could be used to do mathematical reasoning about computation.

Turing used his abstract machines to investigate what kinds of things could be computed. He found some tasks which, although perfectly well defined and mathematically precise, are uncomputable. The first of these is known as the halting problem, which asks, for any given computation, whether it will ever stop. Turing showed that this was uncomputable: there is no systematic method that always gives the right answer.

So, if you have ever wanted a program that can run on your laptop and test all your other software to determine which of them might cause your laptop to “hang” or get stuck in a never-ending loop, the bad news is such a comprehensive testing program cannot be written.

Uncomputability is not confined to questions about the behaviour of computer programs. Since Turing’s work, many problems in mainstream mathematics have been found to be uncomputable. For example, the Russian mathematician and computer scientist, Yuri Matiyasevich, showed in 1970 that determining if a polynomial equation with several variables has a solution consisting only of whole numbers is also an uncomputable problem.

Turing machines have been used to define measures of the efficiency of computations. They underpin formal statements of the P vs NP problem, one of the Millennium Prize problems.

Another important feature of Turing’s model is its capacity to treat programs as data. This means the programs that tell computers what to do can themselves, after being represented in symbolic form, be given as input to other programs. Turing Machines that can take any program as input, and run that program on some input data, are called Universal Turing Machines.

These are really conceptual precursors of today’s computers, which are stored-program computers, in that they can treat programs as data in this sense. The oldest surviving intact computer in the world, in this most complete sense of the term, is CSIRAC at Melbourne Museum.

 

CSIRAC was Australia’s first digital computer, and the fourth “stored program” computer in the world. Melbourne Museum

It seems a mathematical model of computation was an idea whose time had come. In 1936, the year of Turing’s result, another model of computation was published by Alonzo Church of Princeton University. Although Turing and Church took quite different routes, they ended up at the same place, in that the two models give exactly the same notion of computability.

In other words, the classification of tasks into computable and uncomputable is independent of which of these two models is used.

Other models of computation have been proposed, but mostly they seem to lead to the same view of what is and is not computable. The Church-Turing Thesis states that this class of computable functions does indeed capture exactly those things which can be computed in principle (say by a human with unlimited time, paper and ink, who works methodically and makes no mistakes).

It implies Turing Machines give a faithful mathematical model of computation. This is not a formal mathematical result, but rather a working assumption which is now widely accepted.

Turing went to Princeton and completed his PhD under Church, returning to Britain in 1938.

Early in the Second World War, Turing joined the British codebreaking operation at Bletchley Park, north-west of London. He became one of its most valuable assets. He was known by the nickname “Prof” and was described by colleague Jack Good as “a deep rather than a fast thinker”.

One of the famous Enigma machines decrypted at Bletchley Park. Keir David

At the time, Germany was using an encryption device known as Enigma for much of its communications. This was widely regarded as completely secure. The British had already obtained an Enigma machine, from the Poles, and building on their work, Turing and colleague Gordon Welchman worked out how the Enigma-encrypted messages collected by the British could be decrypted.

Turing designed a machine called the Bombe, named after a Polish ice cream, which worked by testing large numbers of combinations of Enigma machine configurations, in order to help decrypt secret messages. These messages yielded information of incalculable value to the British. Winston Churchill described the Bletchley Park codebreakers as “geese that laid the golden eggs but never cackled”.

In 1945, after the war, Turing joined the National Physical Laboratory (NPL), where he wrote a report on how to construct an electronic computer, this time a general-purpose one unlike the machines dedicated to cryptanalysis which he helped to design at Bletchley Park.

This report led to the construction of an early computer (Pilot ACE) at NPL in 1950. By then, Turing had already moved on to Manchester University, where he worked on the first general-purpose stored-program computer in the world, the Manchester “Baby”.

The remade Bombe machine at Bletchley Park, England, features miles of circuitry. Keir David

In their early days, computers were often called “electronic brains”. Turing began to consider whether a computer could be programmed to simulate human intelligence, which remains a major research challenge today and helped to initiate the field of artificial intelligence.

A fundamental issue in such research is: how do you know if you have succeeded? What test can you apply to a program to determine if it has intelligence? Turing proposed that a program be deemed intelligent if, in its interaction with a human, the human is unable to detect whether he or she is communicating with another human or a computer program. (The test requires a controlled setting, for example where all communication with the human tester is by typed text.)

His paper on this topic – Computing Machinery and Intelligence – was published in 1950. The artificial intelligence community holds regular competitions to see how good researchers’ programs are at the Turing test.

The honours Turing received during his lifetime included an OBE in 1945 and becoming a Fellow of the Royal Society in 1951.

His wartime contributions remained secret throughout his life and for many years afterwards.

In 1952 he was arrested for homosexuality, which was illegal in Britain at the time. Turing was found guilty and required to undergo “treatment” with drugs. This conviction also meant he lost his security clearance.

In 1954 he ingested some cyanide, probably via an apple, and died. An inquest classified his death as suicide, and this is generally accepted today. But some at the time, including his mother, contended his death was an accidental consequence of poor handling of chemicals during some experiments he was conducting at home in his spare time.

Dino Gravalo.

The irony of Turing losing his security clearance – after the advantage his work had given Britain in the war, in extraordinary secrecy – is clear.

The magnitude of what was done to him has become increasingly plain over time, helped by greater availability of information about the work at Bletchley Park and changing social attitudes to homosexuality.

Next year, 2012, will be the centenary of Turing’s birth – with events planned globally to celebrate the man and his contribution. As this year approached, a movement developed to recognise Turing’s contribution and atone for what was done to him. In 2009, British Prime Minister, Gordon Brown, responding to a petition, issued a formal apology on behalf of the British government for the way Turing was treated.

For more such insights, log into www.international-maths-challenge.com.

*Credit for article given to Graham Farr*