Satisfiability Problems Online Game

There's an article in the IEEE Spectrum regarding Crowdsourcing the Complexities of Electronic Design Automation, which talks about a game called FunSAT that could benefit chip makers in improving their designs. Humans can help at this stage because these kind of problems are difficult for computers to solve. The game simulates satisfiability problems (SATs), and presents the user with a set of buttons and bubbles, where the buttons can have a value of true, false, or unassigned, and the bubbles, which represent clauses, can be satisfied, unsatisfied, or undetermined. The goal is to turn all bubbles green. For a bubble to turn green, at least one of the literals in the corresponding clause must be true. If all of the literals are false, the bubble will turn red; otherwise, it will be gray.

Why are satisfiability problems important? Because they aid in the design verification stage of chip design. "For example, they are used to find out what input combinations result in exposing a potential bug in the design. If no such combination exists, then the designers don’t have to worry about that particular bug."

"Modern satisfiability solvers tend to prioritize and limit their searches to a few paths that look promising. By using this method, however, they don’t always find the best configuration. What humans lack in brute-force speed, they tend to make up for with pattern recognition and intuition—the ability to know a good move without being able to explain why it’s good. And, most important, they like to play games."

What will change everything?

The Edge annual question for 2009, "what will change everything?", is being posed by John Brockman to a community of thinkers. More precisely, "what game-changing scientific ideas and developments do you expect to live to see?". Below are part of some answers that I particularly found interesting (although you should read all of them!):

Kevin Kelly, Editor-At-Large, Wired: "It is hard to imagine anything that would "change everything" as much as a cheap, powerful, ubiquitous artificial intelligence—the kind of synthetic mind that learns and improves itself."

Ed Regis, Science Writer: "The idea was that scientists and engineers would construct vast fleets of "assemblers," molecular-scale, programmable devices that would build objects of practically any arbitrary size and complexity, from the molecules up. Program the assemblers to put together an SUV, a sailboat, or a spacecraft, and they'd do it—automatically, and without human aid or intervention. Further, they'd do it using cheap, readily-available feedstock molecules as raw materials."

Marc D. Hauser, Psychologist and Biologist, Harvard University: "Science fiction writers traffic in a world that tries on possible worlds. What if, as in the Hollywood blockbuster Minority Report, we could read people's intentions before they act and thus preempt violence? An intentionality detector would be a terrific device to have, but talk about ethical nightmares. " This is something that I also thought about when thinking about the question posed.

Marcelo Gleiser, Appleton Professor of Natural Philosophy, Dartmouth College, talks about mastering death through. "I can think of two ways in which mortality can be tamed. One at the cellular level and the other through an integration of body with genetic, cognitive sciences, and cyber technology."

Freeman Dyson, Physicist, Institute of Advanced Studies: "I expect that genetics and molecular biology will be dominant for the next fifty years, and after that neurology will have its turn. Neurology will change the game of human life drastically, as soon as we develop the tools to observe and direct the activities of a human brain in detail from the outside". In a nutshell: direct communication between brain and brain.

Lawrence Krauss, Physicist, Director, Origins Initiative, Arizona State University: "The Use Of Nuclear Weapons Against A Civilian Population." To be honest, I doubt this will happen. Its implications are far too deep and serious.

Gregory Benford, Novelist, Co-founder & Chairman: "Live To 150." I second that!

Richard Foreman, Founder Director, Ontological-Hysteric Theater; Playwright: "Nothing Will Change Everything." Pretty straight forward, isn't it?

... and many many more. Definitely worth reading!

Images of the Sun

The Boston Globe has a series of amazing images of the Sun. Enjoy!

Why is self-healing in computer systems important?

Reading about the malfunction that rendered the Hubble Space Telescope silent, I realized indeed how important is for systems to have the property of self-healing that our human body has, and in the broader sense, be autonomic. This would imply for the system to know itself in such a way as to poses detail knowledge of its components, status, and internal and external connections. If a system does not have information about a specific component, it cannot control it, hence the importance of knowing itself.

Furthermore, reconfiguring itself based on the environment is also a desired property. Most importantly, such a system would need to heal itself without the interference of human experts. Why do we need such a self-healing characteristic in computer systems? The Hubble Space Telescope mentioned above is one example. The failure in the telescope came from a unit that collects data and transmits it to earth. Solving this problem means to remotely send commands to the telescope to switch its operations to a backup unit. Why hasn't this been achieved automatically? Because Hubble was not designed with self-healing in mind. Would have been that complicated to discover the problem on its own and find an alternative resource that it could use to continue its normal operation? Self-healing really means just making use of redundant or underutilized components to take over the task of the malfunctioned element. This is similar to how the brain works when parts of it are damaged. The problem is that because Hubble is not 'aware' of its backup unit, that specific unit has not been utilized since 1990, making it subject to "harmful rays of the sun, extreme temperature changes during orbits and 18 years of cosmic debris".

If you are interested in Autonomic Computing, IBM has a whole research project devoted to this subject. You can find out more about this here.