Gedanken eines Informatikers, Mathematikers und Lehrers.

14.08.2006

Der WDR-Computerclub kehrt zurueck

Wie ich gerade einem Artikel bei Spiegel Online» entnehmen durfte, ist das hoelzerne Zweigestirn der Wolfgangs (Wolgang Back» und Wolfgang Rudolph») zurueckgekehrt. Bekannt aus dem guten alten ueber viele Jahre gesendeten WDR-Computerclub», macht man sich nun daran, in Form eines Podcastes» die Welt zurueck zu erobern. CC-Zwei» nennt sich das neue audiophile Projekt um die beiden knuddeligen Senioren, die mein Herz sofort hoeher schlagen lassen, wenn sie ueber 486er und Disketten reden.

Es war eine schoene Zeit! Damals als die digitale Welt noch weitaus analoger war. Ihr habt mich als Fan gewonnen.

26.07.2006

Das Schwein und die Kiste

Freie Lizenzen (z.B. in Form von creative commons») dienen Kreativen, ihre Werke der Menschheit frei zugaenglich zu machen, ohne zu starke und restriktive Forderungen an die Weiterverwendung und -verbreitung zu stellen.

Damit dies auch die kleinsten unserer Gesellschaft (die Kinder) schnell und verstaendlich lernen, ist ein Kinderbuch mit Namen "Das Schwein und die Kiste" entstanden, in dem ein Schwein eine Kiste entdeckt, mit der es in der Lage ist, Lebensmittel zu vervielfaeltigen, diese jedoch nicht mit anderen Tieren der Umgebung teilt, sondern fuer sich behaelt und dadurch schliesslich zum unbeliebten Waldbewohner wird. Natuerlich ist das Werk unter den u.a. links frei erhaeltlich.

Eine alternative Variante, das Thema fuer Erwachsene aufzubereiten, heisst "Bound by Law" und ist in Form eines Comics bei der Duke University of Law» erhaeltlich.

Pig an the Box (PDF, deutsch)
Pig an the Box (PDF, englisch)

via: golem.de

10.07.2006

Internet für alle – überall

Es geht daran, das Internet aus seinen hausischen Gefilden zu befreien und weltweit durch die Luft zu pusten. Dieses Ziel verfolgt fon.com». Getrieben durch kräftige Finanzspritzen von Skype, google, Ebay und diversen anderen Magnaten, werden subventionierte WLAN-Router für 5 EUR in alle Welt verschickt. Zu Hause angekommen, werden diese an den heimischen DSL-Anschluss geklemmt und jeder registrierte FONero darf darüber surfen. Wer den Anschluss des Routers einen Monat lang verpennt, muss 45 EUR Strafe latzen.

Er werden drei Arten von Nutzern unterschieden. Ein Linus ist ein Nutzer, der selbst einen Hotspot zur Verfügung stellt und im Gegenzug jederzeit kostenlos auf der ganzen Welt andere Hotspots nutzen darf. Ein Bill stellt ebenfalls seinen Zugang zur Verfügung, darf sich nicht kostenlos in der ganzen Welt einloggen (z.B. für Geschäftsinhaber interessant), wird dafür jedoch an den Einnahmen, die er mit seinem Hotspot erzielt, beteiligt. Solche Einnahmen werden von so genannten Aliens generiert, die nicht registriert sind und für 3 EUR/$ pro Tag den Zugang nutzen können.

Ein tolle Sache für alle, die sowieso noch einen WLAN-Router benötigen und sich mit einem solchen anarchistischen Gedanken anfreunden können.

Wo man in Dortmund schon überall einen solchen Zugang findet, zeigt eine Karte» auf der Seite. Zur Zeit verzeichnet Deutschland 2891 solcher öffentlichen Hotspots. Eine Zahl, die bis Ende 2007 weltweit auf 1.000.000 Hotspots ausgedehnt werden soll.

Also, auf geht's.

02.07.2006

BumpTop - der Desktop der Zukunft

Ein Video ueber BumpTop» zeigt den Desktop der Zukunft als einen virtuellen Schreibtisch, auf dem Dokumente in Stapeln verwaltet, in Groesse und Form veraendert und in vielerlei Hinsicht organisiert werden koennen. Das Video, das es zu sehen gibt, zeigt deutlich, wohin die Reise gehen soll.

via digg.com»

26.06.2006

Fira RoboWorld Cup

Vom 28. Juni bis zum 3. Juli finden in den Dortmunder Westfalenhallen wieder einmal Weltmeisterschaften fuer Fussballroboter statt. Die bereits in Bremen stattfandene WM wird nun um den 11. FIRA RoboWorld Cup» (FIRA = Federation of International Robot Soccer Association») ergaenzt. Wieder einmal gibt es diverse Ligen, die sich im wesentlichen durch die Groesse der Teilnehmer unterscheiden, in denen um den Titel gespielt wird. Der Eintritt ist frei und praesentiert wird das Ganze von der Uni Dortmund - wobei ich, bis auf einen Pappaufsteller, nicht viel davon mitbekommen habe.

Begleitet wird die gesamte Veranstaltung von einem Kongress», dessen Programm als PDF» verfuegbar ist. Es folgt ein kleiner Auszug, mit (zumindest fuer mich) interessanten Themen.

  • A General Robot Soccer Simulation Platform for FIRA?s Mirosot and Simuosot
  • Autonomous MiroSot - The Autonomous Way of Playing MiroSot
  • How Spiritual Machine Works
  • A Move-Controlling Model for Soccer Robot
  • Software Structure of a Control System for the Mirosot Soccer Game
Mich als Nicht-Ingenieur interessiert natuerlich der rein Software getriebene Aspekt der Veranstaltung, der sich in Simurosot» niederschlaegt. Einer Liga, die die Roboter lediglich auf dem Rechner simuliert und sich damit mehr um die Strategie und Teaminteraktion der Klienten kuemmern kann/muss.

24.06.2006

Dynamic Languages Day

Im Februar diesen Jahres fand in Bruessel der Dynamic Languages Day» statt. Vorgestellt wurden hierbei die Sprachen Scheme, Smalltalk, Self sowie Generic Functions und CLOS MOP (Common Lisp Object System - Meta Object Protocol). Von der Homepage koennen sowohl die Folien der einzelnen Praesentation», wie auch deren Videos» heruntergeladen werden.

Wer sich also mit objekt-orientierten Sprachen wie Java, C# und C++ auskennt, ist herzlich eingeladen, sein Wissen durch diese aeusserst interessanten Kandidaten zu vertiefen und zu erweitern.

18.06.2006

Krieg der Sprachen

Ein in American Scientist erschienener Artikel mit dem Titel The Semicolon Wars» beschreibt die Kriege, die seit jeher zwischen den Informatikern der Welt ausgetragen werden. Zwischen 2500 und 8000 verschiedene Programmiersprachen mit ihren jeweiligen ueberzeugten Juengern buhlen um die Gunst und Aufmerksamkeit. Oder ist doch irgendwie alles schon mal dagewesen und gar nicht so neu?

Besonders gut haben mir die folgenden Zeilen gefallen, die wieder einmal zeigen, wie gut in Java doch alles gemeint ist und wie schlecht es letztendlich dann doch werden kann.

Consider the Java expression Date(2006,1,1); what calendar date do you suppose that specifies?The answer is February 1, 3906. In Java we count months starting with 0, days starting with 1, and years starting with 1,900.

17.06.2006

Robocup WM 2006

Stell dir vor es ist WM, und keiner geht hin?! So kann es wohl dem ein oder anderen Wissenschaftler bei der diesjaehrigen WM fuer Roboterfussball» gehen, die in diesem Jahr erstmalig in Deutschland - genauer, in Bremen - stattfindet. Vorne mit dabei ist auch wieder ein Dortmunder Team. Das ZDF bietet auf einer Sonderseite» einen taeglichen Livestream, sowie die Highlights des jeweiligen Spieltages. Reinschauen lohnt sich also. Und irgendwie putzig sehen sie ja auch aus, wenn sie immer so schoen umfallen, noch bevor sie den Ball beruehrt haben.

Was dann jedoch noch der FIRA RoboWorld Cup», der demnaechst auch hier in Dortmund stattfinden soll, zu bedeuten hat, weiss ich leider auch nicht. Ist wahrscheinlich wie beim Boxen, wo es auch jede Menge Verbaende gibt und jeder seinen Weltmeister kuehrt.

Nachtrag
Auch Spiegel online berichtet heute ueber die WM. Als Geheimtipp fuer das heutige Wochenende» soll die Veranstaltung herhalten und alle Bremer in die Finalspiele locken. Schade, dass Bremen so weit weg ist.

12.06.2006

Buchtipp: Practical Common Lisp

Ein juengst von Peter Seibel geschriebenes Buch mit dem Titel Practical Common Lisp» konnte ich heute endlich zu Ende lesen. Es behandelt, wie der Name bereits vermuten laesst, Common Lisp, dem wohl weit verbreitesten LISP-Dialekt. Nach einer kurzen Einfuehrung in alle Sprachkonstrukte, inklusive CLOS (dem Common Lisp Object System), Conditions (einem den Java-Exceptions aehnlichen aber generellen Fehlerbehandlungsmechanismus) oder generischen Methoden (Funktionen, die auf unterschiedlichen Typen arbeiten) werden einige sehr ambitionierte reale Projekte, wie etwa ein Shoutcast-Streaming-Server, eine HTML-Template-Sprache oder eine ID3-Tag Bibliothek angegangen. Wenngleich ich den Projekten nicht sonderlich viel abgewinnen konnte, da sie nicht unbedingt in einer mich arg interessierenden Anwendungsdomaene liegen, so konnten mich der Rest des Buches und insbesondere Lisp dennoch ueberzeugen.

Jedem Programmierer, der einmal ueber den Tellerrand seiner Haus-und-Hof-Sprache hinausblicken moechte - und der Aufwand lohnt sich tatsaechlich - sei dieses Buch (und natuerlich der Klassiker Structure and Interpretation of Computer Programs) waermstens ans Herz gelegt.

Das Buch selbst ist in einer Onlinefassung», wie auch in einer PDF-Fassung (welche beim Verlag erst nach etwas Suchen unter einem etwas versteckten Link» zu finden ist) erhaeltlich.

28.05.2006

XP, Programmiersprachen und Dylan


Und wieder einmal konnte mich das Chaosradio des Chaos Computer Club mit einer Sendung ueber Programmiersprachen im Allgemeinen und Dylan im Besonderen» ueberzeugen. Man bekommt einen schoenen Ueberblick ueber die ganze bunte Welt der Programmiersprachen, die sich in den letzten Jahrzehnten angesammelt haben. Von imperativen Welten, wie C und Fortran, ueber funktionale Ansaetze, wie Haskell, bis zu Mischformen, wie Scheme und Lisp, wird das gesamte Spektrum einmal abgegrast und geschichtlich mit erstaunlich viel Hintergrundwissen untermauert. Wirklich eine wunderbare Sendung, die ich jeden Informatik-Interessierten nur ans Herz legen kann. Zwar verlangt der Podcast mit seinen fast zwei Stunden Sendezeit doch arg viel von der eigenen Freizeit, doch sind diese mit Sicherheit gut angelegt.

Eine ebenfalls spannende Sendung des Chaosradios drehte sich um Extreme Programming (kurz XP)». Was steckt eigentlich hinter diesem seit Ende der 90er Jahre kursierendem Schlagwort? Nicht nur ist die Zusammen- und Vorstellung der einzelnen Zutaten, die XP ausmachen und sich nicht nur auf das Pair-Programming und Unit-Testing versteift, ueberaus interessant, sondern auch vielmehr eine Quelle der Inspiration fuer das eigene Arbeiten. Ergo, reinhoeren und umsetzen.

23.05.2006

Die 10 besten SciFi-Filme

Der Guaradian» bringt eine von "Experten" abgesegnete Top10-Liste der besten Sci-Fi-Filme heraus, die ich natuerlich hier unbedingt kommentieren moechte (muss).

1. Blade Runner (1982) Dir: Ridley Scott
Ne, du auf den ersten Platz gehoert einfach 2001. Blade Runner ist aber tatsaechlich auch nicht schlecht. Aber es ist eben kein Kubrick. Da haben die guten Experten wohl einfach nur die beiden Plaetze vertauscht. Aber Schwamm drueber, kann jedem mal passieren.

2. 2001: A Space Odyssey (1968) Dir: Stanley Kubrick
Ich verneige mich schweigend und voller Ehrfurcht vor nicht nur dem wohl besten SciFi-Film, der es dem Genre erst und woh leider auch einmalig ermoeglichte, aus seinem wenig ernst zu nehmenden Image in eine beachtens- und diskutierenswerte Stellung zu erheben, sondern wohl auch der beste Film, der je von einem Menschen (oder zaehlt Kubrick schon als Halbgott?) gedreht wurde.

3. Star Wars (1977)/Empire Strikes Back (1980)
Stimmungsvolles Maerchen mit klaren Grenzen zwischen Gut und Boese fuer den junggebliebenen Erwachsenen. Dennoch ist es fraglich, ob ein Teil alleine hier bestehen kann. Sehr gute und stimmungsvolle Unterhaltung. Mehr jedoch definitiv nicht. Franzosen wuerden hier wohl klar die Grenze zwischen cinema und cinéma ziehen.

4. Alien (1979) Dir: Ridley Scott
Sehr schoene psychologische und stimmungsvolle Charakterstudie, die sinnhaft das uns umgebende Grauen tatsaechlich aus uns selbst gebaehrend manifestiert.

5. Solaris (1972) Dir: Andrei Tarkovsky
Der spaeteren Soderbergh-Verfilmgung konnte ich bei weitem mehr abgewinnen als Tarkovskys Variante. Dennoch ist dem leider erst kuerzlich verstorbenen Lem mit seiner literarischen Vorlage eine deutungstraechtige Studie zum Verhaeltnis zwischen Mensch und Geist gelungen.

6. Terminator (1984)/T2: Judgment day (1991) Dir: James Cameron
Ne du. Jetzt mal ganz schnell weg hier. SciFi ist nicht Effektschlacht oder "Der teuerste Film aller Zeiten"™.

7. The Day the Earth Stood Still (1951) Dir: Robert Wise
Klatu verata nectu. Wer den Ursprung dieses vielzitierten Satzes kennenlernen moechte, sollte sich genau diesen Film anschauen und staunen, wie wenig ein guter SciFi-Film doch mit Effekten zu tun haben kann.

8. War of the Worlds (1953) Dir: Byron Haskin
Leider kenne ich nur die eher maessige Spielbergverfilmung und lasse mich hier zu keinem Urteil hinreissen.

9. The Matrix (1999) Dir: Andy & Larry Wachowski
Auch dieser Film gerhoert hier eigentlich nicht rein. Ein bisschen Wuehlerei in der pseudopshilosophischen Krims-Krams-Kiste von LaPlace und coole Sonnebrillen mit maessigem schauspielerischen Engagement machen noch keinen guten Film. Schon keinen sehr guten.

10. Close Encounters of the Third Kind (1977) Dir: Steven Spielberg
Och menno. Muss denn wirklich immer etwas von Spielberg in solchen Listen rumkrebsen. Na, wenigstens war es nicht E.T. Aber auch diesem Familienfilmchen kann ich nichts abgewinnen.

via digg.com»

06.05.2006

Klassische Texte der Informatik

Eine ganze Reihe klassischer Texte der Informatik - insbesondere Paper (oder heisst es Papers?) - verspricht Classic Texts In Computer Science». Meine Highlights darunter waeren Ebenso interessant anhören tun sich jedoch auch die folgenden Kandidaten, die ich bisher jedoch noch nicht gelesen habe.

04.05.2006

Heute war ein besonderes Datum

Heute war ein wohl ganz besonderes Datum. Genau um 01:02:03 am 04.05.06 versprechen alle zahlenmystischen Versprechungen Wundersames.

Dies und noch viel mehr zu einigen ausgewählten Zahlen gibt es bei archimedes-lab.org».

via Mathematische Kleinigkeiten»

02.05.2006

Der 100. Geburtstag von Kurt Gödel

Unser aller Begründer der Unvllstndigkt hatte am 28. April sein 100 jähriges Jubiläum und ich habe es verpasst. Egal. Lieber zu spät als gar nicht gedenke ich hiermit feierlich einem der wohl größten mathematischen Verwirrer seiner Zeit: Kurt Gödel»:
Gödel proved fundamental results about axiomatic systems showing in any axiomatic mathematical system there are propositions that cannot be proved or disproved within the axioms of the system.

via Mathematische Kleinigkeiten»

29.04.2006

Was für ein Käse

Wenn ein Käse unendlich viele Löcher hat, jedes Loch jedoch unendlich klein ist, gibt es den Käse dann noch oder besteht der Käse dann nur noch aus einem Loch?

28.04.2006

TidlyWiki

Was ist eigentlich ein TidlyWiki»?
Eine besondere Form eines Wikis.

Was ist daran anders als bei herkoemmlichen® Wikis?
Die Seiten sind kleiner. Es gibt nur sogenannten MicoContent. Kleine Schnipsel zu den verschiedensten Themen. Somit lassen sich relevante Inhalte leichter finden und separieren.

Was ist das besondere an TidlyWiki?
Das komplette Wiki kommt aus einer Seite und benoetigt keinerlei Server im Hintergrund. Die Logik wird dabei vollstaendig in Javascript realisiert.

Gibt es auch so etwas wie Tags?
Ja, alle Eintraege koennen hierbei getaggt werden. Wie man es vielleicht auch schon bei Kategorien von herkoemmlichen Wikis kennt.

Und wieviel kostet das Ganze?
Natuerlich nichts. Es steht unter einer sehr freiherzigen BSD-Lizenz und kann von jedem, der dies mag, benutzt werden.

Was ist sonst noch anders?
Interessanterweise ist das Browsen eines TiddlyWikis vollstaendig anders, als man es fuer gewoehnlich kennt. Die Seiten werden sehr schnell und ohne grosse Verzoegerung aufgebaut, weil ja schon alles im Browsercache drinsteckt und nichts mehr nachgeladen werden muss. Auch hat der Surfer einen grossen Einfluss darauf, wie die verschiedenen Seiten aussehen, wie die Eintrage angeordnet werden, was man sieht, etc.

Irgendwie kann ich mir darunter nichts vorstellen?!
Macht nichts. Einfach mal unter tiddlywiki.com» vorbeischauen und ein wenig rumspielen, ausprobieren und staunen oder belaechelnd bei Seite legen.

26.04.2006

The Future of Programming: An Interview with Paul Graham

In einem Interview mit ACM» erzählt Paul Graham», der sich unter anderem für einige Lisp-Publikationen, den Yahoo! Store und die einfache bayesische Klassifikation von Spam verantworlich zeichnet, etwas über die Zukunft der Programmiersprachen der nächsten Generation. Die beiden ersten - und wohl interessantesten - Fragen und deren Antworten stehen bereits hier.
Where do you see programming as a discipline in five, ten, or twenty years?

I think in the future programmers will increasingly use dynamic languages. You already see this now: everyone seems to be migrating to Ruby, which is more or less Lisp minus macros. And Perl 6, from n what I've heard, seems to be even more Lisplike. It's even going to have continuations.

Another trend I expect to see a lot of is Web-based applications. Microsoft managed to keep a lid on these for a surprisingly long time, by controlling the browser and making sure it couldn't do much. But now the genie is out of the bottle, and it's not going back in.

I don't think even now Microsoft realizes the danger they're in. They're worrying about Google. And they should. But they should worry even more about thousands of twenty year old hackers writing Ajax applications. Desktop software is going to become increasingly irrelevant.

What has your experience developing a new programming language, Arc, been like?

Interrupted. I haven't spent much time on it lately. Part of the problem is that I decided on an overambitious way of doing it. I'm going back to McCarthy's original axiomatic approach. The defining feature of Lisp, in his 1960 paper, was that it could be written in itself. The language spec wasn't a bunch of words. It was code.

Of course as soon as his grad students got hold of this theoretical construct and turned it into an actual programming language, that plan came to a halt. It had to, with the hardware available then. But with the much faster hardware we have now, you could have working code as the entire language spec.

I hope to get back to work on Arc soon. One of the reasons Y Combinator operates in 3-month cycles is that it leaves me some time to work on other stuff. (The other is that it's actually the right way to do seed investing.)

via connotea.org»

Xerox als Brutstätte der Innovation

Ein Artikel» von Audibleblog verraet etwas über die Geschichte und Innovationskraft von Xerox – einem Unternehmen, das hauptächlich für Kopierer bekannt ist, sich unter anderem aber auch für Erfindungen wie den Laserdrucker, die Computermaus oder aber die graphische Benuzeroberfläche verantwortlich zeichnet. Der Bericht gibt einen schönen Einblick in eine Welt, die wirtschaftliche Interessen und innovative wissenschaftliche Arbeit gut zu vereinbaren scheint.

Ich sage nur mount everest. :)

[mp3]

25.04.2006

Java um eine Scriptsprache erweitern

Alles wird gut! Java scheint sich in Version 6 endlich recht modular und allgemein der Öffentlichkeit zu öffnen und Erweiterungsmöglichkeiten um eine Scriptsprache anzubieten. So zumindest der vielversprechende Artikel mit dem Titel Build your own scripting language for Java - An introduction to JSR 22»

In gerade diesem Artikel heißt vollmundig: The upcoming Java Standard Edition 6.0 release will include an implementation of Java Specification Request 223, Scripting for the Java Platform. This JSR is about programming languages and their integration with Java. This article demonstrates the power and potential of JSR 223 through the implementation of a simple Boolean language. Throughout the example, you will see how to program to the Scripting API (javax.script.*), how to package and deploy a language implementation in accordance with the script engine discovery mechanism, and how to make your script engine compilable as well as invocable the JSR 223 way.

28.02.2006

21.02.2006

Von Text zu Text

So ergab es sich am heutigen Tage, dass nach einiger Zeit der Probierens, es (ja was denn eigentlich?) mir nun endgültig gelang, ein mehr oder minder komplexes Dokument in LaTeX in ein mehr oder minder anderes komplexes Dokument in HTML zu konvertieren. Schier unendlich hohe Hürden mussten gemeistert werden, ehe das Dokument so stand, wie es nun steht.

Doch immer langsam mitte Pferde. Eigentlich dachten wir (Clemens» und ich), dass es doch eine tolle Sache wäre, wenn man die Dokumentation für ein Softwareprodukt» doch gerne nur einmal schreibt, gerade so, dass man sie auch ausdrucken kann, und dass man dann eine Version für die Veröffentlichung im Internet automatisch generieren lässt. Soweit so gut. Recht schnell war dann auch schließlich das LaTeX-Dokument fertig gestellt. Also *zack* wacker zu einem frickelig zusammengehackten Stück Software in Perl gegriffen (auch bekannt unter dem vielversprechenden Namen latex2html»). Irgendwie wollte das jedoch überhaupt nicht hinhauen. Nach einer kleinen Suche, tauchte dann noch ein kleines anderes Stück Software mit Namen tex2page» auf. In Scheme geschrieben, schnell installiert und es macht genau das, was man von ihm verlangt.

Danke für diese Eingebung. Ich werde niemals nie nimmer wieder auf frickelige Perl-Software ausweichen und stets dem λ-kalkülisierten Scheme treu bleiben. In tiefer Verbeugung und mit ewiger Dankbarkeit dem Entwickler von tex2page».

Wer die Ergebnisse einmal vergleichen möchte, findet unten die beiden Links, die jeweils einmal auf das ursprüngliche PDF, das aus dem LaTeX-Dokument erzeugt wurde, sowie die automatisch generierte HTML-Version davon verweisen.

17.02.2006

Funktionen und Mengen

Da habe ich mir doch mal wieder ein paar Gedanken zu den guten alten Konzepten der Mengen gemacht und bin zu der Überzeugung gekommen, dass Mengen nicht nur durch ihre Aufzählung allein genügend charakterisiert sind. Vielmehr sollte es doch auch eine implizite Möglichkeit geben, Mengen zu beschreiben. Dies passiert eben ganz einfach durch die Verwendung von Funktionen. So lässt sich etwa die Menge {1, 2, 3} mit den Element 1, 2 und 3 ja auch durch eine Prädikatsfunktion wie folgt beschreiben.
         / tt  falls x∈{1, 2, 3}
  f x = |
         \ ff  sonst
Zunächst scheint es, als hätten wir die Aufzählung nur einfach wegabstrahiert. Jedoch kann die Aussage x∈{1, 2, 3} ebenso in eine äquivalente Form x=1 ∨ x=2 &or x=3 gebracht werden.

Schauen wir nun, was bei Negation dieser impliziten Charakterisierung passiert. Welche Menge beschreibt etwa die Funktion g x = ¬(f x)? Schauen wir einmal, welche Elemente alle darin enthalten sind.

g 1 = ¬(f 1) = ¬tt = ff
g f = ¬(f f) = ¬ff = tt
g g = ¬(f g) = ¬ff = tt
Interessanterweise enthält g also nicht nur alle natürlichen Zahlen außer der 1, 2 oder 3, sondern enthält auch alle Funktionen, insbesondere also auch f und sich selbst. Wir haben also mit g eine Menge beschrieben, die sich selbst enthält - und sich insbesondere echt enthält, also eine echte Teilmenge von sich selbst ist. Ein Widerspruch?

Sollte die Verwirrung noch nicht ausreichend sein, versuchen wir nun einmal eine Menge zu konstruieren, die sich selbst beschreibt - die also nicht nur eine (echte) Teilmenge von sich selbst ist, sondern sich selbst ist. Wir benötigen also eine Funktion, die, wenn auf sich selbst angewendet, tt als Ergebnis liefert, und ansonsten eben ff. Versuchen wir es also mit der folgenden Definition.

       / tt  falls x = h
h x = |
       \ ff  sonst
Die Funktion scheint soweit zu funktionieren, erzeugt jedoch das neue Problem, etwas über die Vergleichbarkeit zweier Funktionen aussagen zu müssen. Im strengen Sinne sind zwei Funktionen genau dann gleich, wenn sie gleiche Urbild- und Bildmengen besitzen. Es spielt also keine Rolle, in welcher Art und Weise die Mengen zueinander erzeugt werden. Lediglich die Beschreibung des Verhältnisses der beiden Mengen ist entscheidend. Nicht jedoch die Berechnungsvorschrift. So sind inbesondere die folgenden Funktionen im Sinne dieses Verständnisses alle gleich:
m1 x = x + x
m2 x = 2 * x
m3 x = (x + x + x + x) / 4
Verträgt sich dies denn auch mit unserer Definition von h? Ich würde behaupten ja. Denn wenngleich ich eine scheinbar andere Funktion als Argument von h auf h anwenden würde, liefert h bei den entsprechenden Eingaben, das intendierte Verhalten. Insbesondere folgt damit aber auch, dass h bei syntaktisch unterschiedlichen Eingaben jeweils tt liefert, die Menge jedoch trotzdem nur eine Element (eben h) enthält.

Fazit: Wir haben es also geschafft, uns von einer expliziten Mengendarstellung hin zu einer impliziten Darstellung zu bewegen und können nun etwas beschreiben, dessen Beschreibung sich selbst enthält. Ob das nur gut geht?!

14.02.2006

Diplomarbeit angemeldet

Nach mittlerweile <censored> Semestern, durfte ich nun endlich zur Tat schreiten und meine Diplomarbeit anmelden. Der ruhmlose Titel lautet "Pläne und Spiele – eine Anwendung für spielbasiertes Model Checking". Was tatsächlich dahinter steckt, wird in spätestens sechs Monaten in jeder gut sortierten Bereichsbibliothek für Informatik in Dortmund zu lesen sein. Um es noch präziser jedem, der es nicht wissen will, vor die Stirn zu schmettern: Meine Abgabetermin wurde auf den 10.8.2006 festgesetzt. Das birgt nun natürlich den unschätzbaren Vorteil, für alles und jeden immer die geniale Ausrede parat zu haben, im Moment so wenig Zeit zu haben, weil man ja seine Diplomarbeit (die man unter uns Diplomanden auch mal ganz pfiffig mit 'DA' abkürzt) schreibt.

Also, auf geht's. Ich hab jetzt nämlich keine Zeit.

11.02.2006

Das Halteproblem

Das Halteproblem, beschreibt die Tatsache, dass es kein Programm geben kann, das für ein anderes Programm entscheiden kann, ob dieses hält oder nicht. Endlosschleifen lassen sich für den allgemeinen Fall also nicht durch einen einfachen (oder auch komplizierten) Algorithmus ausfindig machen. Dass noch nicht einmal Namen, die man für Aufrufe verfolgen könnte, notwendig für eine Endlosschleife sind, zeigt das folgende Beispiel.
    (λ () . (λ x. (x x)) (λ x. (x x)))
Einen anschaulichen Beweis für dieses Problem habe ich heute bei Structure & Interpretation of Computer Programs wiedergefunden, den ich kurz vorführen möchte.

Angenommen, es gäbe eine Funktion safe(f, a), die für eine Funktion f und ein Argument a, herausfindet, ob f(a) definiert ist oder nicht - ob ein die Funktion f berechnendes Programm also irgendwann zu einem Ergebnis kommt, oder ewig lange in einer Endlosschleife verharrt und damit kein Resultat liefert. Formal beschreiben wir die Funktion safe wie folgt.

              / tt    falls f(a)≠⊥
safe(f, a) = |
              \ ff    sonst
Die Annahme einer solchen Funktion führt jedoch zu einem Widerspruch, wenn wir folgende Funktion betrachten.
        / ⊥    falls safe(d, d)
d(x) = |
        \ 3    sonst
Doch wozu wertet nun d(d) aus? Dies hängt von safe und insbesondere von safe(d, d) ab. Wir schauen uns die beiden Fälle einfach mal an.

safe(d, d)=true
Dann gilt d(d)=⊥. safe würde jedoch nur true liefern, wenn d(d)≠⊥ gilt. Als kann nicht gelten safe(d, d)=true.

safe(d, d)=false
Dann jedoch gilt d(d)=3. safe kann jedoch nur false liefern, wenn gilt d(d)=⊥. Es kann also auch nicht gelten safe(d, d)=false.

In beiden Fällen haben wir einen Widerspruch produziert und können daher nur annehmen, dass eine gewünschte Funktion safe mit besagten Eigenschaften nicht existieren kann. Schade.

13.01.2006

Y f = f(Y f)

Heute mal etwas Theorie zum Thema λ-Kalkül. Hierbei handelt es sich um eine von Alonzo Church etablierte Theorie zur Ausführung von Funktionen. Hierbei nehmen wir Funktionen als anonyme Funktionen λ an und können die Identität (also die Funktion, die alle Argumente auf sich selbst abbildet) wie folgt darstellen:
    λx.x
Die anonyme Funktion λ bildet ihr einziges Argument x auf sich selbst ab. Wir trennen in diesem Falle die Argumente (also x) von ihrer Anwendung durch einen kleinen '.' ab.

Wenn wir eine Funktion nun auf ein Argument anwenden, schreiben wir es einfach rechts daneben und erhalten im obigen Sinne der Definition der Identität folgende Gleichung:

    (λx.x) 1 = 1
Diese erhalten wird, indem wir die Argumente für die an den λ-Operator gebundenen Variablen einsetzen; die Funktion also auf 1 anwenden.

Nun können Argumente aber nicht nur einfach elementare Werte sein, sondern selbst wiederum Funktionen. Wir könnten also die Identität auch auf sich selbst anwenden und erhielten

    (λx.x)(λx.x) = (λx.x)
Die Identität verändert sich selbst also nicht. Ebenso sehen wir, dass Ergebnisse von Funktionen ebenfalls wiederum Funktionen sein können.

Kommen wir nun zu einer etwas interessanteren Funktion

    Y = (λf.(λx. f(x x))(λx. f(x x)))
und nennen diese Y.

Was passiert nun, wenn wir Y auf f anwenden?

(*) Y f = (λx. f(x x))(λx. f(x x))
Y f ist also eine Funktion, die auf eine Funktion angewendet wird. Wollen wir diese Anwendung noch verfolgen und den rechten Teil der obigen Gleichung etwas vereinfachen, so erhalten wir
    Y f = f((λx. f(x x)) (λx. f(x x)))
nachdem wir (λx. f(x x)) für x in f(x x) eingesetzt haben.

Nun erkennen wir aber, dass wir f auf der rechten Seite der Gleichung gerade auf (*), also auf Y f, anwenden und somit zu der interessanten Gleichung

    Y f = f(Y f)
kommen. Y liefert uns also für eine gegebene Funktion f deren Fixpunkt.

Probieren wir diese Funktion nun einmal aus und versuchen den Fixpunkt der Eins-Funktion (λx.1) zu bestimmen

    Y (λx.1) =
    (λf.(λx. f(x x))(λx. f(x x)))(λx.1) =
    (λx. (λx.1)(x x))(λx. (λx.1)(x x)) =
    (λx. 1)(λx. 1) =
    1
Juhu, es hat geklappt. Der Fixpunkt der Eins-Funktion ist demnach 1.

Wer Spaß daran gefunden hat, möge einmal versuchen, den Fixpunkt unserer oben beschriebenen Identiät auf diese Weise zu berrechnen. Er wird sicherlich erstaunt ob des bestimmten Fixpunktes sein. :)

Das wollte ich eigentlich nur mal gesagt haben. :)

06.01.2006

Structure and Interpretation of Computer Programs

Lange ist es her seit meine letzte Nachricht an die Menschheit in dieses öffentliche Forum meiner Seite verkündet wurde. Nun bin ich aber wieder zurück und wünsche in guter höflicher Manier allen meinen Lesern - und ich weiß, dass es wenige sind - ein Frohes Neues Jahr.
Um diesen Eintrag noch weiter begründen zu können, möchte ich auf eine meiner tollsten Entdeckungen in der Informatiklandschaft hinweisen: Scheme. Hierbei handelt es sich um eine Programmiersprache (genauer: einen Lisp-Dialekt), der mich in seiner Eleganz und Mächtigkeit, Probleme und deren Lösung zu beschreiben, schlichtweg umgehauen hat.
Neben dem Buch Struktur und Interpretation von Compterprogrammen», das unabhängig von der verwendeten Sprache ein grandioses Standardwerk der Infoamtikausbildung am MIT» bildet, haben mich die Autoren selbst in einer sehr professionell gestalteten Vorlesung» auf Grundlage dieses Buches aus den 80er Jahren überzeugt. Neben Videos dieser Veranstaltung, ist auch eine Textversion des o.g. Buches auf dieser Seite zu finden, die sich "leider" zunehmender Beliebtheit zu erfreuen scheint und daher nicht immer so gut erreichbar ist, wie man es sich wünscht.
In diesem Sinne:
(define null
  (λ (f)
    (λ (x) x)))

(define 1+ n
  (λ (f)
    (λ (x) (f ((n f) x)))))

(Alonzo Church)