You are currently browsing the tag archive for the ‘Computer Science’ tag.
The Hacker and the Ants is a work of science fiction by Rudy Rucker published in 1994 by Avon Books. It was written while Rucker was working as a programmer at Autodesk, Inc., of Sausalito, California from 1988 to 1992. The main character is a transrealist interpretation of Rucker’s life in the 1970s (Rucker taught mathematics at the State University College at Geneseo, New York from 1972 to 1978. from Wikipedia). The plot follows:
(…) Jerzy Rugby is trying to create truly intelligent robots. While his actual life crumbles, Rugby toils in his virtual office, testing the robots online. Then, something goes wrong and zillions of computer virus ants invade the net. Rugby is the man wanted for the crime. He’s been set up to take a fall for a giant cyberconspiracy and he needs to figure out who — or what — is sabotaging the system in order to clear his name. Plunging deep into the virtual worlds of Antland of Fnoor to find some answers, Rugby confronts both electronic and all-too-real perils, facing death itself in a battle for his freedom. (…)
Figure – Attractor basins (fig.2 pp.6 on Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011.)
Mária Ercsey-Ravasz and Zoltán Toroczkai have proposed a way of mapping satisfiability problems to differential equations and a deterministic algorithm that solves them in polynomial continuous time at the expense of exponential energy functions (so the discrete approximation of the algorithm does not run in polynomial time, and an analogue system would need exponential resources).
The map assigns a phase space to a problem; the algorithm chooses random initial conditions from within that phase space. In the graphs above and below, they pick a 2-d subspace of the phase space and for each initial point in that space they illustrate 1) the particular solution the algorithm finds, 2) the corresponding “solution cluster”, an equivalence class of solutions that identifies two solutions if they differ in exactly one variable assignment, and 3) the time it takes to solve the problem. Each row adds another clause to satisfy.
The especially interesting part of the paper is the notion of an escape rate, the proportion of the trajectories still searching for a solution after a time t. In a companion paper, they show that the escape rate for Sudoku combinatorial instances (The Chaos Within Sudoku, Nature, August 2012) correlates strongly with human judgements of hardness. This escape rate is similar to the Kolmogorov complexity in that it gives a notion of hardness to individual problem instances rather than to classes of problems. Full paper could be retrieved from arXiv: Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011. (at arXiv on August 2012).
Figure – Attractor basins for 3-XORSAT (fig.8 pp.18 on Mária Ercsey-Ravasz and Zoltán Toroczkai, “Optimization hardness as transient chaos in an analog approach to constraint satisfaction“, Nature Physics, vol. 7, p. 966-970, 2011.)
Figure (click to enlarge) – Orders of common functions (via Wikipedia): A list of classes of functions that are commonly encountered when analyzing the running time of an algorithm. In each case, c is a constant and n increases without bound. The slower-growing functions are generally listed first. For each case, several examples are given.
Fig. – First Difference Engine. This impression from a woodcut was printed in 1853 showing a portion of the Difference Engine that was built in 1833 by Charles Babbage, an English mathematician, philosopher, inventor, and mechanical engineer who originated the concept of a programmable computer.
“If all you have is a hammer, everything looks like to you as a nail” ~ Abraham Maslow, in “The Psychology of Science“, 1966.
“Propose to an Englishman any principle, or any instrument, however admirable, and you will observe that the whole effort of the English mind is directed to find a difficulty, a defect, or an impossibility in it. If you speak to him of a machine for peeling a potato, he will pronounce it impossible: if you peel a potato with it before his eyes, he will declare it useless, because it will not slice a pineapple. […] Impart the same principle or show the same machine to an American or to one of our Colonists, and you will observe that the whole effort of his mind is to find some new application of the principle, some new use for the instrument“. ~ Charles Babbage quoted in Richard H. Babbage (1948), “The Work of Charles Babbage“, Annals of the Computation Laboratory of Harvard University, vol. 16.
At the beginning of the 1820’s, Babbage worked on a prototype of his first difference engine. Some parts of this prototype still survive in the Museum of the history of science in Oxford. This prototype evolved into the “first difference engine.” It remained unfinished and the completed fragment is located at the Museum of Science in London. This first difference engine would have been composed of around 25.000 parts, weighed around fourteen tons (13.600 kg), being 2.4 meters tall. Although it was never completed. He later designed an improved version, “Difference Engine No. 2”, which was not constructed until 1989–91, using Babbage‘s plans and 19th century manufacturing tolerances. It performed its first calculation at the London Science Museum returning results to 31 digits, far more than the average modern pocket calculator. (check Charles Babbage Wikipedia entry for more).
Soon after the attempt at making the difference engine crumbled, Babbage started designing a different, more complex machine called the Analytical Engine (fig. above). The engine is not a single physical machine but a succession of designs that he tinkered with until his death in 1871. The main difference between the two engines is that the Analytical Engine could be programmed using punched cards. He realized that programs could be put on these cards so the person had only to create the program initially, and then put the cards in the machine and let it run. It wasn’t until 100 years later that computers came into existence, with Babbage‘s work lying mostly ignored. In the late 1930s and 1940s, starting with Alan Turing‘s 1936 paper “On Computable Numbers, with an Application to the Entscheidungsproblem” (image below) teams in the US and UK began to build workable computers by, essentially, rediscovering what Babbage had seen a century before. Babbage had anticipated the impact of his Engine when he wrote in his memoirs: “As soon as an Analytical Engine exists, it will necessarily guide the future course of science.“
Video – “Intel Star” TV ad – Who’s your rock star? – Rather than focusing on a new product, the 2009 “Sponsors of Tomorrow” ad campaign celebrates what makes Intel different culture, personality, heroes – and ways Intel has helped change the world for over 40 years. Featuring Ajay Bhatt co-inventor of USB !