Learning From Ants

Jack Dikian

April 2011

Ants

We’ve all come across a line of ants seemingly marching to and from their nest and food. Some of us may have even owned an ant farm created between 2 panes of glass. Like all, besides the idea that we don’t want them in our house, we have probably also marveled at their ingenuity and keenness for social behavior in order to survive and thrive.

In fact one of the greatest advantages for ants is their social behaviour - working as a colony with specialized duties, they are more efficient than insects in getting necessary things done.

Communicating and Learning their way to food

Ants form and maintain a line to their food source by laying a trail of pheromone, i.e. a chemical to which other members of the same species are very sensitive. They deposit a certain amount of pheromone while walking, and each ant prefers to follow a direction rich in pheromone. This enables the ant colony to quickly find the shortest route. The first ants to return should normally be those on the shortest route, so this will be the first to be doubly marked by pheromone (once in each direction). Thus other ants will be more attracted to this route than to longer ones not yet doubly marked, which means it will become even more strongly marked with pheromone. Soon, therefore, nearly all the ants will choose this route. Here, ants are using the environment as a medium of communication.

Studying this uncanny skill has enabled researchers to create algorithms aimed to search optimal paths in graphs, and applied to applications such as rerouting traffic in busy communications network.

Us learning from ants

In computing research ant colony optimization algorithm (part of swarm intelligence methods) is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. Graphs are mathematical structures used to model pair-wise relations between objects in a collection.

Whilst the first algorithm was aiming to search for an optimal path in a graph based on the behavior of ants, this idea has since diversified to help solve a wider class of numerical problems.

Application

The use of the ant colony optimization algorithms has produced near-optimal solutions to the travelling salesman problem.

The travelling salesman problem is one of the most intensively studied problems in computational mathematics – that is finding the shortest route visiting each member of a collection of locations and returning to the start. Even rewards are offered in various forums encouraging solutions to this problem. For example,

In February 2009, Robert Bosch (Oberlin College) created a 100,000-city instance of the travelling salesman problem that provides a representation of Leonardo da Vinci's Mona Lisa as a continuous-line drawing. An optimal solution to the 100,000-city Mona Lisa instance would set a new world record for the travelling salesman problem – and $1000 prize.

Because ant colony optimization algorithm can be run continuously and adapt to changes in real time, this gives them an advantage over simulated information annealing (which all users of the system are permitted to change the system) and genetic algorithms. Network routing, urban transportation systems and resource-constrained project scheduling are areas with an interest in this type of algorithms.

Halting Problem - Turing's proof

Jack Dikian

January 2011

A few days ago, I started reading David Leavitt’s book “The Man Who Knew Too Much – Allan Turning and the invention of the computer – 2007” and almost by coincidence met up with an old Uni friend – recalling the countless hours we spent discussing esoteric problems in philosophy and mathematics. Turning machines was a big favorite – universal, and easy to code. Another was the halting problem. Easy enough to understand, and the proof for its insolvability was provided by Turing in 1936.

I wanted to revisit this problem and present it in a form that avoids the deeper symbolic language of set theory.

In computability theory, the halting problem is a decision problem, deciding, given a program and an input, whether the program will eventually halt when run with that input, or whether it will run forever.

In 1936 Alan Turing proved that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. It is said that the halting problem is un-decidable over Turing machines.

Formal Convention

The formal representation of decision problem(s) is the set of objects possessing the property in question. The halting set is represented by

K := { (i, x) | program i will eventually halt if run with input x

And this set is recursively enumerable. I.e, there is a computable function that lists all of the pairs (i, x) it contains.

In practice

Programs may contain loops which may be infinite or finite in length. The amount of work done in any program will depend on the input. Programs may also consist of various numbers of loops, nested or in sequence.

Trial solution

We can just run the program with the given input. If the program stops, we know the program stops. But what if the program doesn't stop in a reasonable amount of time, what are we to conclude. We are not able to conclude that it won't stop.

A look at the proof

Suppose you have a solution to the halting problem called H. 
 H takes two inputs:

1. a program P and

2. an input I for the program P.

H generates an output "halt" if H determines that P stops on input I or it outputs "loop" otherwise.

Fig, 1

Prog P ---------->

---------> “Loop” or “halt”

Input 1 --------->

So now H can be revised to take P as both inputs (the program and its input) and H should be able to determine if P will halt on P as its input. Let us construct a new, simple algorithm K that takes H's output as its input and does the following

1. if H outputs "loop" then K halts,

2. otherwise H's output of "halt" causes K to loop forever.

That is, K will do the opposite of H's output.

function K() {

if (H()=="loop"){

return;

} else {

while(true); //loop forever

}

}

Fig 2

----> True ------> Halt

P ------------ H ------> Loop ? ---> False ----- > Loop

----->

Since K is a program, let us use K as the input to K.

Fig 3

----> True ---------> Halt

K ----------- H ---> Loop ---> False --------> Loop

---->

If H says that K halts then K itself would loop (that's how we constructed it).
If H says that K loops then K will halt. In either case H gives the wrong answer for K. Thus H cannot work in all cases.

Computing the “Theory of everything” (Strings)

Jack Dikian

String theory was originally developed to describe the fundamental particles and forces that make up our universe. New research, led by a team from Imperial College London, describes the unexpected discovery that string theory also seems to predict the behavior of entangled quantum particles. As this prediction can be tested in the laboratory, researchers can now test string theory.

Before strings

String theory is the most recent attempt to reconcile quantum mechanics and general relativity. It's the first candidate for the theory of everything, a manner of describing the known fundamental forces and matter in a mathematically complete system.

We learned in school that matter is made of atoms, which are in turn made of just three basic components: electrons [spinning] around a nucleus composed of neutrons and protons. In chemistry, some of us also learned that generally, there are as many neutrons as are protons in any nucleus of an atom. There are however isotopes where their nucleus contains an uneven mix of protons and neutrons.

It was quite comfortable for us to think of the atom in this way – somewhat reminiscent of planets revolving around the sun. The students that had a special interest in physics went on to discover that the electron is a truly a fundamental particle (it is one of a family of particles known as leptons), but neutrons and protons are made of smaller particles, known as quarks. Quarks are, as far as we now know, also elementary particles.

The universe is made up of atoms and forces through which atoms interact.

Our current knowledge about the subatomic composition of the universe is summarized in what is known as the Standard Model of particle physics. It describes both the fundamental building blocks out of which the universe is made, and the forces through which these blocks interact. There are twelve basic building blocks:-

Six of these are quarks which go by the interesting names of up, down, charm, strange, bottom and top. A proton incidentally, is made of two up quarks and one down.

The other six are Leptons and include the electron and its two heavier siblings, the Muon and the Tauon, as well as three neutrinos.

There are four fundamental forces in the universe:

§ Gravity,
§ Electromagnetism,
§ the Weak and
§ Strong nuclear forces also known as the colour force.

Each of these is produced by fundamental particles that act as carriers of the force. The most familiar of these is the photon, a particle of light, which is the mediator of electromagnetic forces. (This means that, for instance, a magnet attracts a nail because both objects exchange photons.) The graviton is the particle associated with gravity. The strong force is carried by eight particles known as gluons. Finally, the weak force is transmitted by three particles, the W+, the W-, and the Z.

We all recognize 2 forces very well – gravity and electromagnetism. We feel the pull of gravity and we use the force of gravity in our day to day lives. Some of us have also played with magnets and appreciate their pull force. The behaviour of the week and strong nuclear forces isn’t one that we observe in every day life. These operate at the subatomic level and bind sub particles with varying degree of strength. The strength of the strong nuclear force, for example, is many magnitudes greater than that of gravity on Earth. If the pull of gravity on was that of the strong nuclear force – we would weigh many trillions more than our current weight.

We use what we call the Standard Model to describe the interaction of sub-particles and forces with great success. This is, however, with one notable exception - gravity. The gravitational force has proven very difficult to describe microscopically. This has been for many years one of the most important problems in theoretical physics. That is to formulate a single model that describes both the micro and macro elements of the universe. Einstein attempted to unify the general theory of relativity (macro) with electromagnetism using a single field, hoping to recover an approximation for quantum theory. A "theory of everything" is closely related to unified field theory, and also attempts to explain all physical constants of nature.

Strings

In the last 20 or so years string theory has emerged as a promising model in attempts to provide a complete, unified, and consistent description of the fundamental structure of our universe, another “Theory of Everything”.

The basic idea is that all of the components of the Standard Model are just different manifestations of one basic element - a string. One way to think about this is by imagining an electron to be a tiny loop of string rather than a single zero-dimensional point. The loop (string) can as well as moving, oscillate in different ways. It is the way strings oscillate that determine the type of subatomic building blocks we recognize. So one kind of oscillation may be an electron whilst another oscillation may be regarded as a photon. This means, if true

The entire universe is made of strings

In recent years many developments have taken place, radically improving our understanding of what the theory is. String theories also require the existence of several extra, unobservable, dimensions to the universe, in addition to the usual four space-time dimensions.

Five major string theories have been formulated with the main differences between them, being the number of dimensions in which the strings are developed within and their characteristics. In the mid 1990s a unification of all previous superstring theories, called M-theory, has been proposed, which asserted that strings are really 1-dimensional slices of a 2-dimensional membrane vibrating in 11-dimensional space.

The Rubik Cube and God's Algorithm

Jack Dikian

Sep 2006

Introduction

In 1974 Erno Rubik, an admirer of geometry and 3-D forms created the world's most perfect puzzle. More than 30 years later the Rubik's cube is still a best selling brainteaser. By the mid-eighties almost every child had the puzzle. Did I say “Child”? I certainly was playing with one when I was about 12 or 13 with little success in solving.

So you can imagine our astonishment when a whole first year pure mathematics class was asked to go out and purchase the puzzle from the university co-op bookshop. I think, like others, I had always suspected that there would a mathematical approach to solving the puzzle. After all, many real-world, albeit, obscure problems such as the four-color map(1) and The Seven Bridges of Konigsberg(2) inspired rigorous mathematical solutions. I, off course didn’t have the mathematical repertoire – instead the brute force method, not in the mathematical sense, was always adopted.

Background

The Rubik’s Cube has a straightforward basis. The faces of the cube are covered by nine stickers in six colours. The puzzle is solved, when each face is of one solid colour. When you start to rotate the rows and columns and see the different mix of colour rows/columns you begin to appreciate the difficulty involved. There is, in-fact, 43 million million possible pattern combinations - but just one right one.

it's been proven that you can solve a Rubik's cube in 26 moves. Computer science professor Gene Cooperman and graduate student Dan Kunkle of the Northeastern University in Boston used algebra and fast parallel computing to show that no matter how scrambled the cube is, it is possible to solve (generate a cube with solid colors on each face, or the home state) in 26 steps. There are however claims that it can be solved in 22 or even 20 steps (see later).

The Rubik's cube has served as a guinea pig for testing techniques to solve large-scale combinatorial problems. "The Rubik's cube has been a testing ground for problems of search and enumeration. Search and enumeration is a large research area encompassing many researchers working in different disciplines — from artificial intelligence to operations. The Rubik's cube allows researchers from different disciplines to compare their methods on a single, well-known problem.

Mathematically

There are many algorithms to solve scrambled Rubik's cubes. It is not known how many moves is the minimum required to solve any instance of the Rubik's cube, although the latest claims put this number at 22. This number is also known as the diameter of the Cayley graph of the Rubik's Cube group. An algorithm that solves a cube in the minimum number of moves is known as 'God's algorithm'. Most mathematicians think it may only takes 20 moves to solve any Rubik's cube – and it’s a question of proving this to be true.

Any state of the cube corresponds to a permutation of its facelets — a rule that assigns to each facelet in the home state a new location on the cube in the scrambled state. Not every permutation of facelets can be achieved by a sequence of moves — for example no move can shift the centre facelet of a face — so when trying to solve Rubik's cube you restrict your attention to a collection of legal permutations.

These form a self-contained system. If you follow one legal permutation by another, the end result is also a legal permutation. If you've done one legal permutation, you can always find another one — namely the reverse of what you've just done — that will get you back to the position you started with. Doing absolutely nothing to the cube is also a legal move and corresponds to the permutation that leaves every facelet where it is, known to mathematicians as the identity permutation.

The problem of solving Rubik's cube can be visualised using what is called the group's Cayley graph — a network whose nodes are the legal states of the cube (corresponding to legal permutations) and which has two nodes linked up if you can get from one to the other by a legal move, which, incidentally, is itself a permutation. The home state of the cube corresponds to one of the nodes (and the identity permutation) and solving the cube corresponds to finding a path from one of the nodes to the home state along a sequence of linked-up nodes.

A brute-force approach to showing that you can always solve the cube in N moves would be to show that no such path involves more than N steps. This sounds good in theory, but there is a huge problem as the Cayley graph of the group of legal permutations has 43,252,003,274,489,856,000 nodes, a number that challenges even the fastest of supercomputers.

The (3 x 3 x 3) Rubik's Cube has eight corners and twelve edges. There are 8! (40,320) ways to arrange the corner cubes. Seven can be oriented independently, and the orientation of the eighth depends on the preceding seven, giving 37 (2,187) possibilities.

There are 12!/2 (239,500,800) ways to arrange the edges, since an odd permutation of the corners implies an odd permutation of the edges as well. Eleven edges can be flipped independently, with the flip of the twelfth depending on the preceding ones, giving 211 (2,048) possibilities.

There are exactly 43,252,003,274,489,856,000 permutations. The full number is 519,024,039,293,878,272,000 or 519 quintillion possible arrangements of the pieces that make up the Cube, but only one in twelve of these are actually solvable. This is because there is no sequence of moves that will swap a single pair of pieces or rotate a single corner or edge cube.

(1) This problem is sometimes also called Guthrie's problem after F. Guthrie, who first conjectured the theorem in 1852. The was then communicated to de Morgan and thence into the general community. In 1878, Cayley wrote the first paper on the conjecture.

(2) One of these areas is the topology of networks, first developed by Leonhard Euler in 1735. His work in this field was inspired by the following problem: The Seven Bridges of Konigsberg.

Virtual Reality Technology and Alzheimer's Disease

The use of virtual reality technology in the assessment, study of, and possible assistance in the rehabilitation of memory deficits associated with patients with Alzheimer disease.

Background

Alzheimer's disease is the common cause of dementia, and is particularly common in older people. Because it is the most common cause of dementia, Alzheimer's disease is commonly equated with the general term dementia. However, there are many other causes of dementia. Alzheimer's disease is therefore a specific form of dementia having very specific microscopic brain abnormalities.

Alzheimer disease is not merely a problem of memory. Additional mental and behavioral problems often affect people who have the disease, and may influence quality of life, caregivers, and the need for institutionalization.

Depression for example affects 20–30% of people who have Alzheimer’s, and about 20% have anxiety. Psychosis (often delusions of persecution) and agitation/aggression also often accompany this disease. Common symptoms and comorbidities include:

• Mental deterioration of organic or functional origin

• Loss of cognitive ability in a previously-unimpaired person, beyond what might be expected from normal aging. Areas particularly affected include memory, attention, judgement, language and problem solving.

• Loss (usually gradual) of mental abilities such as thinking, remembering, and reasoning. It is not a disease, but a group of symptoms that may accompany some diseases or conditions affecting the brain.

• Deteriorated mental state due to a disease process and the result from many disorders of the nervous system.

• Cognitive deficit or memory impairment due to progressive brain injury.

Distinguishing Alzheimer's disease from other causes of dementia is not always as easy and straightforward as defining these terms. In practice, people and their disorders of behaviour, or behaviours of concern are far more complex than the simple definitions sometimes provided.

Establishing patient history, abilities, the natural course of disorder development such as that involving short-term memory, speech and language, personality, decision-making and judgment, and others is often needed in the diagnosis of the disease. Routine diagnostic steps therefore include a careful history, mental status screening, laboratory and imaging studies, and neuropsychologic testing.

Differential diagnosis of Alzheimer's disease

It is sometimes difficult to differentiate dementia caused by Alzheimer's from delirium and in addition several features distinguish dementia from depression, but the two can coexist and the distinction may be uncertain.

Whilst prominent motor signs such as Gait disturbance is a characteristic feature of patients with vascular dementia - In contrast, the NINCDS-ADRDA criteria for Alzheimer's disease state that: `gait disturbance at the onset or very early in the course of the illness' makes the diagnosis of probable Alzheimer's disease uncertain or unlikely. However, clinical studies suggest that gait disturbance is not restricted to the later stages of Alzheimer's disease. Also, studies have identified abnormalities of gait and balance in patients with early Alzheimer's disease(1).

It had been thought that Dementias without prominent motor signs included Alzheimer's disease, frontotemporal dementia, and Creutzfeld-Jakob, and others and the clinical pattern of gait disturbance in patients with early Alzheimer's disease has attracted less attention to date.

Diagnosis

Differential diagnosis between the types of dementia and treatments available for Alzheimer's - while limited in their effectiveness usually have best patient outcomes when begun early in the course of the disease. Diagnosis and/or diagnostic tools include:

Taking medical history.

Physical examination including evaluations of hearing and sight, as well as blood pressure and pulse readings, etc.

Standard laboratory tests including blood and urine tests designed to help eliminate other possible conditions.

Neuropsychological testing including assessing memory, problem-solving, attention, vision-motor coordination and abstract thinking, such as performing simple calculations.

Brain-imaging or structural brain scan such as CT or MRI to help rule out brain tumors or blood as the reason for symptoms and more recently

The use of virtual reality

The use of virtual reality technology in the assessment, study of, and possible assistance in the rehabilitation of memory deficits associated with patients with Alzheimer disease.

Using virtual reality to simulate real-word environments and test patient’s ability to navigate these environments. Work has been carried out to compare previously described real-world navigation tests with a virtual reality version simulating the same navigational environment (2). Authors of this research work conclude that virtual navigation testing reveals deficits in aging and Alzheimer disease that are associated with potentially grave risks to patients and the community.

In another study in the United Kingdom (3), researchers’ aimed to examine the feasibility of virtual reality technology for use by people with dementia (PWD). Data was obtained directly from six PWD regarding their experiences with a virtual environment of a large outdoor park. A user-centered method was developed to assess:

(a) presence;
(b) user inputs;
(c) display quality;
(d) simulation fidelity; and
(e) overall system usability.

The extent to which PWD could perform four functional activities in the virtual enviroment was also investigated (e.g., mailing a letter). In addition, physical and psychological well-being of PWD while interacting with the virtual environment was assessed objectively by recording heart rate during the virtual reality sessions and subjectively with discrete questionnaire items and real-time prompts.

(1) Gait disturbance in Alzheimer's disease: a clinical studyS.T. O'Keeffe, H. Kazeem, R.M. Philpott, J.R. Playfer, M. Gosney, M. Lye July, 1996

(2) NEUROLOGY 2008;71:888-895
Detecting navigational deficits in cognitive aging and Alzheimer disease using virtual reality
Laura A. Cushman, PhD, Karen Stein and Charles J. Duffy, MD, PhD
From the Departments of Neurology, Brain and Cognitive Sciences, Neurobiology and Anatomy, Ophthalmology, and Psychiatry (L.A.C.) and Center for Visual Science, The University of Rochester Medical Center, Rochester, NY.

(3) Flynn D, van Schaik P, Blackman T, Femcott C, Hobbs B, Calderon C.
School of Social Sciences and Law, The University of Teesside, Middlesbrough, United Kingdom

Quantum-connected computers overturn the uncertainty principle

Introduction

Back in the mid eighties when completing a pure mathematics degree and using the then state of the art mini-computers, the PDP11 family of processors (we couldn’t afford the services of the more, much more, brawny nitrogen-cooled Crays to solve sparse Hadamard matrices - I contributed an article in a UK computer journal discussing the future of computers, artificial intelligence, human interfaces and visualization – I guess you can call it a naive attempt to predict how systems will/MAY evolve. Of course this was through my own lens of experience. Watching processor speeds rapidly increasing and memory, disk and everything else growing almost exponentially.

Of course the implicit question was - If all that has happened in the first 50 years of computer history, what will happen in the next 50 or so years?

Moore's Law is an empirical formula describing the evolution of processors which is often cited to predict future progress in the field, as it's been proved quite accurate in the past: it states that the transistor count in an up-to-date processor will double each time every some period of time between 18 and 24 months, which roughly means that computational speed grows exponentially, doubling every 2 years. As processors become faster the science of computability, amongst other things describes a class called 'NP-hard problems' which are also sometimes referred to 'unacceptable', 'unsustainable' or 'binomially exploding' whose complexity and therefore computation grow exponentially with time.

An example of NP-hard algorithm is the one of finding the exit of a labyrinth: it doesn't require much effort if you only find one crossing, but it gets much more demanding in terms of resources when the crossings become so large that it becomes either impossible to compute because of limited resources, or computable, but requiring an unacceptable amount of time.

Many, if not all, of the Artificial Intelligence related algorithms are extremely demanding in terms of computational resources because they are either NP-hard or involve combinatorial calculus of growing complexity.

Not all developments in processing architecture stem from a single genesis. For example, recently, IBM researchers have made huge strides in mapping the architecture of the Macaque monkey brain. They have traced long-distance connections in the brain - the "interstate highways" which transmit information between distant areas of the brain. Their maps may help researchers grasp how and where the brain sends information better than ever before, and possibly develop processors that can keep up with our brain's immense computational power and navigate its complex architecture.

Artificial intelligence and cognitive modeling try to simulate some properties of neural networks. While similar in their techniques, the former has the aim of solving particular tasks, while the latter aims to build mathematical models of biological neural systems.

Another trajectory – that of Quantum Computers

The uncertainty principle is a key underpinning of quantum mechanics. A particle's position or its velocity can be measured but not both. Now, according to five physicists from Germany, Switzerland, and Canada, in a letter abstract published in Nature Physics(1) quantum computer memory could let us violate this principle

Paul Dirac who shared the 1933 Nobel Prize in physics with Erwin Schrödinger, "for the discovery of new productive forms of atomic theory” provided a concrete illustration of what the uncertainty principle means. He explained that one of the very, few ways to measure a particle's position is to hit it with a photon and then chart where the photon lands on a detector. That gives you the particle's position, yes, but it's also fundamentally changed its velocity, and the only way to learn that would consequently alter its position.

That's more or less been the status quo of quantum mechanics since Werner Heisenberg first published his theories in 1927, and no attempts to overturn it - including multiple by Albert Einstein himself - proved successful. But now the five physicists hope to succeed where Einstein failed. If they're successful, it will be because of something that wasn't even theorized until many years after Einstein's death: Quantum Computers.

Key to quantum computers are qubits, the individual units of quantum memory. A particle would need to be entangled with a quantum memory large enough to hold all its possible states and degrees of freedom. Then, the particle would be separated and one of its features measured. If, say, its position was measured, then the researcher would tell the keeper of the quantum memory to measure its velocity.

Because the uncertainty principle wouldn't extend from the particle to the memory, it wouldn't prevent the keeper from measuring this second figure, allowing for exact, or possibly, for obscure mathematical reasons, almost exact measurements of both figures.

It would take lots of qubits - far more than the dozen or so we've so far been able to generate at any one time - to entangle all that quantum information from a particle, and the task of entangling so many qubits together would be extremely fragile and tricky. Not impossibly tricky, but still way beyond what we can do now.


(1) Nature Physics
Published online: 25 July 2010 doi:10.1038/nphys1734
The uncertainty principle in the presence of quantum memory
Mario Berta, Matthias Christandl, Roger Colbeck, Joseph M. Renes & Renato Renner