2009.01.26 | Marianne Dammand Iversen

Making it pervasive: computing, healthcare anduser innovation
by Morten Kyng

Computing is undergoingfundamental changes as computation literally moves out of the box and begins to pervade our environment. Visions of (almost) almighty, intelligent agents taking care of our needs even before we know we have them are abundant. But current reality is somewhat different and just figuring out howto print or synchronize data on a mobile phone is often a problem. We will look at some of the challenges in developing useful applications, services and systems based on pervasive computing and illustrate these with examples from thehealthcare area. What about physical/digital integration? What happens with interaction styles? What happens when systems cross organizational borders and integrate work and daily life? How may we organize innovative development processes? Answers are only beginning to emerge, but they point to a future where computing pervade our environment in useful, learnable and enjoyable ways.

Deciding the Undecidable
by Michael Schwartzbach

A fundamental intellectualachievement in Computer Science, dating back to the 1930s, is the observation that that there is a universal notionof computability and that some problems are actually uncomputable. This is not merely a philosophical curiosity, buta concrete problem for the design and implementation of programming languages, since it turns out that every interesting question about the behavior of programs is undecidablein the sense of its answers being uncomputable. This includes questions about the correctness of programs, their running times, their resource consumptions, and the applicability of most optimizations. Fortunately, for practical purposes it is often sufficient to obtain conservative and approximate answers to these questions. The efficient computation of useful answers is the challenge that has given riseto the research area of static program analysis, which has an established mathematical basis but also a strong engineering flavor for real-life languages and questions. We present the foundations of static analysis and give examples of recent projects that use these techniques to combat undecidability.

Names in Boxes and Dante in Purgatory
by Peter Bro Miltersen

We investigate two puzzles with a "recreational mathematics" flavour.

The first one ("Names In Boxes") originates in joint work with Anna Gal from 2003.The second one ("Dante in Purgatory") originates in very recent joint work with Kristoffer Arnsfelt Hansen and MichalKoucky. We solve the puzzles and explain their connection to deep unresolved problems of mathematical computer science.

Names in Boxes:

The names of one hundred prisoners are placed in one hundred wooden boxes, one name to each box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; they may look into up to fifty of the boxes to try to find their own name but must leave the room exactly as it was. They are permitted no further communication after leaving the room. Theprisoners have a chance to plot a strategy in advance and they are going to need it, because unless they all find their own names they will all be executed. There is a strategy that has a probability of success exceeding thirty percent - find it.

Dante in Purgatory:

There are seven terraces in Purgatory, indexed one to seven. Dante enters Purgatory at terrace one.

Each day, if Dante finds himself at some terrace i, he must play a game of matching pennies against Lucifer:

Lucifer hides a penny, and Dante must try to guess if it is heads up or tails up. If Dante guesses correctly, he proceeds to terrace i + 1 the next morning - if i + 1 is eight, he enters Paradise and the game ends. If, on the other hand, Dante guesses incorrectly, there are two cases. If he incorrectly guesses “heads”, he goes back to terrace one the next morning. If he incorrectly guesses “tails” the game ends and Dante forever loses the opportunity of visiting Paradise.

How can Dante ensure ending up in Paradise with probability at least 75 percent? How long should he expect to stay in Purgatory before the game ends in order to achieve this?