Grundlagen der praktischen Programmierung von Dr. Erhard Henkes Stand: 07.05.2004

Was ist eigentlich Programmierung? Es ist - einfach ausgedrückt - die Erstellung von Software für einen Rechner (Computer).
Was ist ein Computer? Computer sind Rechenanlagen, die Daten verarbeiten.

Diese Antworten sind nur begrenzt hilfreich. Man möchte die Zusammenhänge praktisch erfassen. Um die Grundlagen der Programmierung zu verstehen, werden wir uns zunächst mit zwei Beispielen beschäftigen: Turingmaschine und „DNS-Computer“. Die Turingmaschine stammt aus den dreißiger Jahren des letzten Jahrhunderts (1936) und wird bereits als theoretische Grundlage für Informatiker an der Hochschule gelehrt, während der "DNS-Computer" in den ersten Jahren des aktuellen Jahrhunderts durch die Arbeitsgruppe von Ehud Shapiro zur Blüte geführt wurde, aber immer noch in den Kinderschuhen steckt. Wir werden sehen, dass es hierbei um das Wechselspiel von vier Elementen geht: Input - Output und Software - Hardware

Turingmaschine

Alan M. Turing hat bereits 1936 die Lösung mathematischer Probleme durch eine Maschine für möglich gehalten, die nur drei Bestandteile enthält: Einen Schreib- Lese-Kopf, ein Schaltwerk und ein unendlich langes Speicherband. Das Speicherband muss in der Lage sein, pro Feld genau ein Zeichen des verwendeten Alphabetes oder ein Leerzeichen (Blank) zu speichern. Da ich davon ausgehe, dass Sie an einem modernen PC sitzen, werden wir eine Simulation einer Turingmaschine einsetzen. Beziehen Sie diese bitte von folgender Stelle:

http://www.gregor-buchholz.de/index.html?html/turing.shtml (unten finden Sie die Version vom Mai 2004)

Anmerkung (29.10.2006):

neuer Link für die Simulation der Touringmaschine: http://www.joefox.de/index.php?key=turing (Version 2.2 von 2006)

Die Turingmaschine hat ein „Band“, an dem man linear entlang wandern kann. Hierbei gibt es einen kombinierten „Schreib-Lese-Kopf“. Diese Hardware ist hier als Software simuliert. Nachdem Sie sich mit dem prinzipiellen Aufbau der Maschine (unsere Hardware) vertraut gemacht haben, wollen Sie sicher etwas programmieren, also Software erstellen. Wir werden zunächst etwas sehr Einfaches programmieren, nämlich ein Programm, das zwei Zeichen sequentiell liest und dabei gegeneinander vertauscht. Wenn wir also ABBA eingeben (unser Input), soll BAAB resultieren (unser Output). Nun wie geht dies hier?

Wir definieren zunächst unser Alphabet: {A,B} (zulässige Menge der Zeichen)

Man gibt einfach A,B im Eingabefeld Alphabet ein.

Unter Eingabewort geben wir ABBA ein.

Sie sehen, dass sich die Matrix aus Zeichen (aus unserem Alfabet plus das Blank #) und „Zuständen“ erweitert hat. Dort müssen wir unser Programm eingeben (Feld anklicken und Return drücken). Der Anfangszustand ist Z01, das Ende ist erreicht, wenn im Zustand Z01 das Zeichen # (steht für Blank) gelesen wird. Gehen wir schrittweise vor: Wenn das gelesene Zeichen ein A ist, soll ein B geschrieben werden bzw. umgekehrt. Zusätzlich bewegen wir den Schreib-Lese-Kopf eine Position weiter. Das wird wie folgt codiert:

Nach vier Schritten ist die Endkonfiguration Z01,# erreicht und unser String bezüglich A und B vertauscht:

In diesem Beispiel haben wir nur einen Zustand verwendet. Anders sieht es bei dem im Download mitgelieferten Beispiel zur Addition zweier Binärzahlen aus. Hier verwendet man 12 Zustände und vier Zeichen.

Um eins und eins zu addieren, benötigt man in diesem Programm 16 Schritte:

„Alles was überhaupt berechenbar ist, ist schon mit der Turingmaschine berechenbar!“ (Church)

Eine interessante Hypothese. Wenn Sie mehr über die Turingmaschine erfahren möchten, lesen Sie z.B. hier weiter:

http://www.matheprisma.uni-wuppertal.de/Module/Turing/

Unsere aktuellen PC’s sind um vieles komplexer als die Turingmaschine. Dennoch ist es eine gute Übung, diese Maschine für einfache Aufgaben einzusetzen, denn gerade jetzt wird diese grundlegende „Maschine“ mittels DNS nachgebaut.

DNS-Computer

Dies ist ein faszinierendes neues Gebiet. Spätere Generationen werden darauf bestimmt mit gleichem Grundlageninteresse schauen wie auf die Turingmaschine.

Auch hier gibt es Zustände und Zeichen in Form von Nukleotid-Code. Input (Daten) und Software werden hier von DNS gebildet, während die Hardware ein Enzym ist. Die Software-DNS verarbeitet Input-DNS, in dem sie ein Enzym namens Fok-I an sich bindet und damit die Input-DNS zerschneidet. Je nach „sticky end“ (freie DNS-Stränge, hier vier Basen) finden sich die richtigen Partner-Moleküle, um durch chemische Umwandlung von einem Zustand in den nächsten überzugehen. Das Enzym Fok-I stellt auch die Energieversorgung des „DNS-Computers“ sicher. Wird die DNS aufgetrennt, lösen sich Bindungen. Darin gespeicherte Energie wird als Wärme freigesetzt. Dadurch kommt der Rechner ohne den biochemischen Brennstoff ATP oder andere externe Energiequellen aus.

http://www.keren-hayessod.de/israel-nachrichten/news/computer.htm

http://nano.ivcon.org/modules.php?name=News&file=article&sid=759

http://www.heise.de/newsticker/meldung/print/46956

http://www.wisdom.weizmann.ac.il/~kobi/

Der Schlüssel-Mechanismus des „DNS-Rechners“ ist in folgender Darstellung von Shapiro und Benenson gut zu erfassen:

aus: DNA molecule provides a computing machine with both data and fuel

Yaakov Benenson, Rivka Adar, Tamar Paz-Elizur, Zvi Livneh, and Ehud Shapiro

Departments of Computer Science and Applied Mathematics and Biological Chemistry, Weizmann Institute of Science, Rehovot 76100, Israel

Edited by Peter B. Dervan, California Institute of Technology, Pasadena, CA, and approved January 13, 2003 (received for review September 17, 2002)

In Bildteil E sieht man die wesentlichen Schritte: Ein Hardware-Software-Komplex muss bezüglich der “sticky ends” zusammen finden. Dann schlägt die Nuklease Fok-I zu und spaltet einen Teil des Input-Moleküls ab. Damit erhält man ein neues Molekül. Dies entspricht bei der Turingmaschine einem Schritt, der den Übergang von einer Zustand-/Zeichen-Kombination zur anderen umfasst. Zuletzt verbleibt ein Output-Molekül, das sozusagen das Resultat der „Berechnung“ darstellt. Der Vorteil des DNS-Rechners ist seine einfach zu realisierende Parallelität, der Nachteil seine niedrige Geschwindigkeit im Einzelschritt (z.Z. bei 20 Sekunden).

(Darstellung ebenfalls aus obiger Quelle)

Ein der Turingmaschine analoger Ablauf ist oben dargestellt.

Damit haben Shapiro, Benenson et. al. den kleinsten biologischen Rechner hergestellt:

Neben Hardware - Software, Input - Output findet sich noch ein weiteres wichtiges Element, nämlich die Speicherung von Informationen, bei der Turingmaschine das nach beiden Seiten „unendliche“ Band, bei dem DNS-Rechner die DNS-Moleküle, die bei passender Software-DNS als Input-DNS bzw. bei nicht-passender Software-DNS als Output-DNS dienen.

Zur Zeit zielt man darauf ab, die Output-DNS als „maskiertes“ Medikament z.B. gegen Krebszellen einzusetzen.

Ist es nicht faszinierend, wie unterschiedlich die Ausprägungen von „Rechenmaschinen“ sein können?