Archive for the ‘Computer Science’ Category

Page 4 of 5

As we once thought

Published by peter on 2010-08-17 in AI, Computer Science, Computer technology, Computing-as-interaction, Forecasting, Logic and Mathematics. 0 Comments


The Internet, the World-Wide-Web and hypertext were all forecast by Vannevar Bush, in a July 1945 article for The Atlantic, entitled  As We May Think.  Perhaps this is not completely surprising since Bush had a strong influence on WW II and post-war military-industrial technology policy, as Director of the US Government Office of Scientific Research and Development.  Because of his influence, his forecasts may to some extent have been self-fulfilling.
However, his article also predicted automated machine reasoning using both logic programming, the computational use of formal logic, and computational argumentation, the formal representation and manipulation of arguments.  These areas are both now important domains of AI and computer science which developed first in Europe and which still much stronger there than in the USA.   An excerpt:

The scientist, however, is not the only person who manipulates data and examines the world about him by the use of logical processes, although he sometimes preserves this appearance by adopting into the fold anyone who becomes logical, much in the manner in which a British labor leader is elevated to knighthood. Whenever logical processes of thought are employed—that is, whenever thought for a time runs along an accepted groove—there is an opportunity for the machine. Formal logic used to be a keen instrument in the hands of the teacher in his trying of students’ souls. It is readily possible to construct a machine which will manipulate premises in accordance with formal logic, simply by the clever use of relay circuits. Put a set of premises into such a device and turn the crank, and it will readily pass out conclusion after conclusion, all in accordance with logical law, and with no more slips than would be expected of a keyboard adding machine.
Logic can become enormously difficult, and it would undoubtedly be well to produce more assurance in its use. The machines for higher analysis have usually been equation solvers. Ideas are beginning to appear for equation transformers, which will rearrange the relationship expressed by an equation in accordance with strict and rather advanced logic. Progress is inhibited by the exceedingly crude way in which mathematicians express their relationships. They employ a symbolism which grew like Topsy and has little consistency; a strange fact in that most logical field.
A new symbolism, probably positional, must apparently precede the reduction of mathematical transformations to machine processes. Then, on beyond the strict logic of the mathematician, lies the application of logic in everyday affairs. We may some day click off arguments on a machine with the same assurance that we now enter sales on a cash register. But the machine of logic will not look like a cash register, even of the streamlined model.”

Edinburgh sociologist, Donald MacKenzie, wrote a nice history and sociology of logic programming and the use of logic of computer science, Mechanizing Proof: Computing, Risk, and Trust.  The only flaw of this fascinating book is an apparent misunderstanding throughout that theorem-proving by machines  refers only to proving (or not) of theorems in mathematics.    Rather, theorem-proving in AI refers to proving claims in any domain of knowledge represented by a formal, logical language.    Medical expert systems, for example, may use theorem-proving techniques to infer the presence of a particular disease in a patient; the claims being proved (or not) are theorems of the formal language representing the domain, not necessarily mathematical theorems.
References:
Donald MacKenzie [2001]:  Mechanizing Proof: Computing, Risk, and Trust (2001).  Cambridge, MA, USA:  MIT Press.
Vannevar Bush[1945]:  As we may think.  The Atlantic, July 1945.

Those pesky addition symbols

Published by peter on 2010-08-15 in Computer Science and Computer technology. 0 Comments


On 28 March 1979, there was a partial core meltdown in a reactor at the Three Mile Island Nuclear Power Generating Station near Harrisburg, PA, USA.  The accident was soon headline news, at least throughout the western world.   An obscure computer programmer apparently hearing this news had a crisis of conscience and, in April 1979, phoned anonymously to the US Nuclear Regulatory Commission, telling them to examine particular program code used in the design of certain types of nuclear reactors.   The code in question was a subroutine intended to calculate the total stresses on pipes carrying coolant water, but instead of adding the different stresses, the routine subtracted them.  So the resulting coolant pipes were extra-thin instead of being extra-thick.

This story would not surprise anyone with any software development experience.   Few other people understand, I think, just how dependent modern society is on the correct placing of mundane arithmetic operators or the appropriate invocation of variable references in obscure lines of old program code.  No programmers, in my experience, took less than seriously, for example, the threat of the Millenium Bug, although lots of people who are not programmers still think it was a threat without substance, or even a scam.

Below I have re-typed the article where first I read about this, as I can find no reference elsewhere on the web.

Faulty software may close more nuclear plants
(from Australasian Computerworld, 18 May 1979, pages 1 and 15).

Washington, DC. – The Nuclear Regulatory Commission (NRC) in the US may soon order more shutdowns of nuclear plants if it finds the design of their piping relies on invalid computer algorithms.

The commission is completing a study [page-break] to determine whether earthquakes could rupture the computer-designed piping of active US nuclear plants as well as those under construction.  In March, the commission ordered five plants in the eastern US to cease operation after an error was discovered in their design software.

The study was initiated following an anonymous phone call last month from an individual who reportedly told the NRC that many other plants were designed or are being designed with similarly flawed routines.  As a result, the commission ordered all 70 licensed plants and the 92 granted construction permits to declare whether they rely on any of three algebraic summation methods.

The water to cool reactor cores in the five suspended plants ran through pipes with tolerances far below NRC standards because of an algebraic summation routine subtracted, rather than added, stress figures.
Nuclear energy experts consider reliable reactor piping a critical safety factor.  A reactor core overheats if not enough water circulates around its radioactive rods to carry heat away.  Pipe ruptures or pump failures would thus induce core overheating that, if unchecked by reserve cooling systems, might force the reactor to discharge dangerous radiation.
NRC inspectors may order more shutdowns if they find other plants in violation of piping tolerance requirements, a spokesman said.  Their decisions will be based on responses to a general bulletin to holders of licences and construction permits.

Need God be complex?

Published by peter on 2010-08-14 in Computer Science and Religion. 0 Comments


Philosopher Gary Gutting attacks the logic of the argument of Richard Dawkins for atheism, here.   Gutting formulates Dawkins’ main argument for atheism as the following chain of reasoning:

1. There is need for an explanation of the apparent design of the universe.
2. The universe is highly complex.
3. An intelligent designer of the universe would be even more highly complex.
4. A complex designer would itself require an explanation.
5. Therefore, an intelligent designer will not provide an explanation of the universe’s complexity.
6. On the other hand, the (individually) simple processes of natural selection can explain the apparent design of the universe.
7. Therefore, an intelligent designer (God) almost certainly does not exist.”

Gutting argues that Claim #7 does not following from Propositions #1 through #6.  But this stated chain of reasoning falls well before reaching claim #7.  Claim #3 does not follow from Claims #1 and #2.    Complex phenomena may emerge from simpler components, as is seen (for example) in the apparently-coordinated, but actually-uncoordinated, behaviours of insects and (simple-rule-following, non-communicating) swarm robots, or in the patterns that emerge in some cellular automata, as in John Conway’s Game of Life.  One could easily imagine a creator who established some simple ground-rules (eg, the laws of thermodynamics and the rules of biological evolution) and a starting position for the universe (eg, the Big Bang), and just let the process evolve or adapt over the course of time, without further divine intervention, subject only to the given rules.  Such a creator need not, Him-, Her- or It-self, be very complex at all, and certainly could be less complex than the universe that resulted in the fullness of time.
This phenomenon is known to most software engineers working on large systems, writing software that exhibits behaviours more complex than they are able to explain or understand subsequently, and even more complex than they intended to create.  The recent Flash Crash of stock prices on 6 May 2010 may be the result of such emergent complexity, unintended (and as yet unexplained) by the system designers, programmers and financial market regulators who operate the world’s stock markets.   Even common computer operating systems are beyond the ability of one person to entirely comprehend, let alone design:  Windows XP has an estimated 40 million source lines of code (SLOC), for example, while Debian 4.0 has an estimated 283 million SLOC.   These are among the most complex human artefacts yet created.  Indeed, the phenomenon is so prevalent in software development that the British Government sponsored research into the topic (see, for example, Bullock and Cliff  2004).
It also seems to me that Claim #4 needs some justification, since it is not obviously true.   Most scientists, for instance, seem perfectly happy accepting certain claims as not requiring any explanation or even any inquiry.  These claims differ from one discipline to another, and typically change over time.  Moreover, uncontested claims in one discipline often form the basis, when contested, of another discipline:  marketing, for example, starts from the contestation of  the foundational notions of commodities, of perfect competition, and of infinite consumer mental processing capabilities that remain uncontested (at least until recently) in mainstream economics; computer science, in another example, contests the assumption of the existence of non-constructive entities taken for granted in mainstream (non-intuitionistic) pure mathematics; parts of the study of uncertainty in artificial intelligence contest the Law of Excluded Middle taken for granted in probability theory and in mathematical statistics.
Gutting also criticises Dawkins for the lack of sophistication of his philosophical arguments:

Religious believers often accuse argumentative atheists such as Dawkins of being excessively rationalistic, demanding standards of logical and evidential rigor that aren’t appropriate in matters of faith. My criticism is just the opposite. Dawkins does not meet the standards of rationality that a topic as important as religion requires.
The basic problem is that meeting such standards requires coming to terms with the best available analyses and arguments. This need not mean being capable of contributing to the cutting-edge discussions of contemporary philosophers, but it does require following these discussions and applying them to one’s own intellectual problems. Dawkins simply does not do this. He rightly criticizes religious critics of evolution for not being adequately informed about the science they are calling into question. But the same criticism applies to his own treatment of philosophical issues.”

I am reminded of Terry Eagleton’s criticism that Dawkins had read insufficient theology, in this spirited review of Dawkins’ book.  Eagleton begins:

Imagine someone holding forth on biology whose only knowledge of the subject is the Book of British Birds, and you have a rough idea of what it feels like to read Richard Dawkins on theology.

Finally, Gutting repeats something mentioned before on this blog:

There are sensible people who report having had some kind of direct awareness of a divine being . . “

If we broadened this group of people to “sensible people who report some kind of direct awareness of non-material realms and divine entities”, then, inter alia, the majority of African, Indian and Chinese people and the first peoples of North America and Australia would fall in this category.
References:
Seth Bullock and Dave Cliff [2004]: Complexity and Emergent Behaviour in Information and Communications Systems.  Report for the UK Foresight Programme on Intelligent Infrastructure Systems, Office of Science and Technology, Government of the UK.  Available here.   Programme Information here.
Richard Dawkins [2006]: The God Delusion.  Bantam Press.
Terry Eagleton [2006]: Lunging, flailing, mispunching.   London Review of Books, 28 (20):  32-34.  2006-10-19.
Gary Gutting [2010]:  On Dawkins’s atheism:  a response.  New York Times, 2010-08-11.

 

Precision as the enemy of knowledge

Published by peter on 2010-08-09 in Africa, Computer Science, Economics and Mathematics. 0 Comments

I have posted previously about the different ways in which knowledge may be represented.  A key learning of the discipline of Artificial Intelligence in its short life thus far is that not all representations are equal.    Indeed, more precise representations may provide less information, as in this example from cartography (from a profile of economist Paul Krugman):

Again, as in his [Krugman’s] trade theory, it was not so much his idea [that regional ecomomic specializations were essentially due to historical accidents] that was significant as the translation of the idea into a mathematical language.  “I explained this basic idea” – of economic geography – “to a non-economist friend,” Krugman wrote, “who replied in some dismay, ‘Isn’t that pretty obvious?’  And of course it is.”  Yet, because it had not been well modelled, the idea had been disregarded by economists for years.  Krugman began to realize that in the previous few decades economic knowledge that had not been translated into [tractable analytical mathematical] models had been effectively lost, because economists didn’t know what to do with it.  His friend Craig Murphy, a political scientist at Wellesley, had a collection of antique maps of Africa, and he told Krugman that a similar thing had happened in cartography.  Sixteenth century maps of Africa were misleading in all kinds of ways, but they contained quite a bit of information about the continent’s interior – the River Niger, Timbuktu.  Two centuries later, mapmaking had become more accurate, but the interior of Africa had become a blank.  As standards for what counted as a mappable fact rose, knowledge that didn’t meet those standards – secondhand travellers’ reports, guesses hazarded without compasses or sextants – was discarded and lost.  Eventually, the higher standards paid off – by the nineteenth century the maps were filled in again – but for a while the sharpening of technique caused loss as well as gain. ” (page 45)

Reference:
Larissa MacFarquhar [2010]:  The deflationist:  How Paul Krugman found politics.  The New Yorker, 2010-03-01, pp. 38-49.

Crowd-sourcing for scientific research

Published by peter on 2010-08-06 in Computer Science, Computer technology, Computing-as-interaction, Human intelligence, Joint-Action Society, Science and Team working. 0 Comments

Computers are much better than most humans at some tasks (eg, remembering large amounts of information, tedious and routine processing of large amounts of data), but worse than many humans at others (eg, generating new ideas, spatial pattern matching, strategic thinking). Progress may come from combining both types of machine (humans, computers) in ways which make use of their specific skills.  The journal Nature yesterday carried a report of a good example of this:  video-game players are able to assist computer programs tasked with predicting protein structures.  The abstract:

People exert large amounts of problem-solving effort playing computer games. Simple image- and text-recognition tasks have been successfully ‘crowd-sourced’ through games, but it is not clear if more complex scientific problems can be solved with human-directed computing. Protein structure prediction is one such problem: locating the biologically relevant native conformation of a protein is a formidable computational challenge given the very large size of the search space. Here we describe Foldit, a multiplayer online game that engages non-scientists in solving hard prediction problems. Foldit players interact with protein structures using direct manipulation tools and user-friendly versions of algorithms from the Rosetta structure prediction methodology, while they compete and collaborate to optimize the computed energy. We show that top-ranked Foldit players excel at solving challenging structure refinement problems in which substantial backbone rearrangements are necessary to achieve the burial of hydrophobic residues. Players working collaboratively develop a rich assortment of new strategies and algorithms; unlike computational approaches, they explore not only the conformational space but also the space of possible search strategies. The integration of human visual problem-solving and strategy development capabilities with traditional computational algorithms through interactive multiplayer games is a powerful new approach to solving computationally-limited scientific problems.”

References:
Seth Cooper et al. [2010]: Predicting protein structures with a multiplayer online game.  Nature, 466:  756–760.  Published:  2010-08-05.
Eric Hand [2010]:  Citizen science:  people power.  Nature 466, 685-687. Published 2010-08-04.
The Foldit game is here.

By their voice ye shall know them

Published by peter on 2010-07-28 in Computer Science, Computer technology and Computing-as-interaction. 0 Comments

Effective strategies are often counter-intuitive.  If you are speaking to a large group, some of whom are speaking to each other, your natural tendency will be to try to speak over them, to speak more loudly.  But doing this just encourages the talkers in the audience to increase their levels of speech, and so an arms race results.   Better for you to speak more softly, which means that audience talkers can hear themselves more clearly over you, and so typically, and unthinkingly, drop the levels of their own speech.
A recent issue of ACM Transactions on Computer Systems (ACM TOCS) carries a paper with a wonderful example of this principle.  Faced with a denial-of-service attack, they propose that a server ask all its clients to increase their messages to the server.  Most likely, attackers among the clients are already transmitting at their local full capacity, and so are unable to do this, which means that messages from attackers will form a decreasing proportion of all messages received by the server.   The paper abstract is:

This article presents the design, implementation, analysis, and experimental evaluation of speak-up, a defense against application-level distributed denial-of-service (DDoS), in which attackers cripple a server by sending legitimate-looking requests that consume computational resources (e.g., CPU cycles, disk). With speak-up, a victimized server encourages all clients, resources permitting, to automatically send higher volumes of traffic. We suppose that attackers are already using most of their upload bandwidth so cannot react to the encouragement. Good clients, however, have spare upload bandwidth so can react to the encouragement with drastically higher volumes of traffic. The intended outcome of this traffic inflation is that the good clients crowd out the bad ones, thereby capturing a much larger fraction of the server’s resources than before. We experiment under various conditions and find that speak-up causes the server to spend resources on a group of clients in rough proportion to their aggregate upload bandwidths, which is the intended result.

Reference:
Michael Walfish, Mythili Vukurutu, Hari Balakrishnan, David Karger and Scott Shenker [2010]:  DDoS defense by offense.  ACM Transactions on Computer Systems, 28 (1), article 3.

Informatics

Published by peter on 2010-07-16 in Computer Science and Computer technology. Closed

A recent issue of the Communications of the ACM has an interesting article about degrees in Informatics, by Dennis Groth and Jeffrey Mackie-Mason.  They present a nice definition of the subject in this para:

The vision for informatics follows from the natural evolution of computing. The success of computing is in the resolution of problems, found in areas that are predominately outside of computing. Advances in computing—and computing education—require greater understanding of the problems where they are found: in business, science, and the arts and humanities. Students must still learn computing, but they must learn it in contextualized ways. This, then, provides a definition for informatics: informatics is a discipline that solves problems through the application of computing or computation, in the context of the domain of the problem. Broadening computer science through attention to informatics not only offers insights that will drive advances in computing, but also more options and areas of inquiry for students, which will draw increasing numbers of them to study computation.

Sadly, these views are not uncontroversial, as the online experiences which motivated my parody here illustrate.  The interesting experience of Georgia Tech, where the School of Computing is split into three parts  — Computer Science; Interactive Computing; and Computational Science and Engineering, — is described here.
Reference:
Dennis P. Groth and Jeffrey K. MacKie-Mason [2010]: Why an Informatics degree?  Isn’t computer science enough? Communications of the ACM, 53 (2):  26-28.  Available here.

This Much I Know (about CS and AI)

Published by peter on 2010-05-05 in Computer Science, Computing-as-interaction, Economics and Mathematics. 0 Comments

Inspired by The Guardian column of the same name, I decided to list here my key learnings of the last several years regarding Computer Science and Artificial Intelligence (AI). Few of these are my own insights, and I welcome comments and responses. From arguments I have had, I know that some of these statements are controversial; this fact surprises me, since most of them seem obvious to me. Statements are listed, approximately, from the more general to the more specific.

Vale: Robin Milner

Published by peter on 2010-03-31 in Computer Science, Computing-as-interaction, Matherati and Obituaries. 0 Comments

The death has just occurred of Robin Milner (1934-2010), one of the founders of theoretical computer science.   Milner was an ACM Turing Award winner and his main contributions were a formal theory of concurrent communicating processes and, more recently, a category-theoretic account of hyperlinks and embeddings, his so-called theory of bigraphs.   As we move into an era where the dominant metaphor for computation is computing-as-interaction, the idea of concurrency has become increasingly important; however, understanding, modeling and managing it have proven to be among the most difficult conceptual problems in modern computer science.  Alan Turing gave the world a simple mathematical model of computation as the sequential writing or erasing of characters on a linear tape under a read/write head, like a single strip of movie film passing back and forth through a projector.  Despite the prevalence of the Internet and of ambient, ever-on, and ubiquitous computing, we still await a similar mathematical model of interaction and interacting processes.  Milner’s work is a major contribution to developing such a model. In his bigraphs model, for example, one graph represents the links between entities while the other represents geographic proximity or organizational hierarchy.

Robin was an incredibly warm, generous and unprepossessing man. About seven years ago, without knowing him at all, I wrote to him inviting him to give an academic seminar; even though famous and retired, he responded positively, and was soon giving a very entertaining talk on bigraphs (a representation of which is on the blackboard behind him in the photo). He joined us for drinks in the pub afterwards, buying his round like everyone else, and chatting amicably with all, talking both about the war in Iraq and the problems of mathematical models based on pre-categories with a visitor from PennState. He always responded immediately to any of my occasional emails subsequently.

The London Times has an obituary here, and the Guardian here (from which the photo is borrowed).

References:
Robin Milner [1989]: Communication and Concurrency. Prentice Hall.
Robin Milner [1999]: Communicating and Mobile Systems: the Pi-Calculus. Cambridge University Press.
Robin Milner [2009]: The Space and Motion of Communicating Agents. Cambridge University Press.

Doing a PhD

Published by peter on 2010-02-17 in AI, Computer Science, Decision theory, Science and Writing. 0 Comments

These are some notes on deciding to do a PhD, notes I wrote some years ago after completing my own PhD.
Choosing a PhD program is one of the hardest decisions we can make. For a start, most of us only make this decision once in our lives, and so we have no prior personal experience to go on.
Second, the success or otherwise of a PhD depends a great deal on factors about which we have little advanced knowledge or control, including, for example:
Continue reading ‘Doing a PhD’