Grenzen der Berechenbarkeit – Gödel | Seminar 19.12.2006

Lange Zeit hat man geglaubt, dass jedes mathematische Problem algorithmisch lösbar ist. Erst vor Kurzem erkannte man, dass nicht alle Probleme algorithmisch lösbar sind.

Was ist die Berechenbarkeit einer Funktion?

- Vorhandensein einer eindeutig definierten Herangehensweise
- zu jeder Eingabe, kann eine Ausgabe der Funktion berechnet werden
- es gibt mehrere Algorithmusbegriffe, wo bisher noch keine sinnvolle Erweiterung bezüglich des Berechenbarkeitsbegriffs gefunden werden konnte, z.B. die Turingmaschine

Die Gödel’sche Unvollständigkeit
Kurt Gödel, ein österreichischer Mathematiker, wies 1931 mit seinem Unvollständigkeitssatz nach, dass man in der Mathematik nicht alle Behauptungen formal beweisen oder widerlegen kann. Sein Unvollständigkeitssatz lautet wie folgt:

„Jedes hinreichend mächtige formale System ist entweder widersprüchlich oder unvollständig.“

(Gödel, http://de.wikipedia.org/wiki/G%C3%B6delscher_Unvollst%C3%A4ndigkeitssatz)

Quelle: http://de.wikipedia.org/wiki
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/spektrum.pdf

frameRate()

void setup() {
  frameRate(4);
}
int pos = 0;
void draw() {
  background(204);
  pos++;
  line(pos, 20, pos, 80);
  if(pos > width) {
    pos = 0;
  }
}

setup

void setup() {
  size(200, 200);
  background(0);
  noStroke();
  fill(102);
}

int a = 0;

void draw() {
  rect(a++%width, 10, 2, 80);
}

Alan Turing

Quelle: http://dept-info.labri.fr/~gavoille/img/turing.gif

Alan Mathison Turing (* 23. Juni 1912 in London; † 7. Juni 1954 in Wilmslow) war ein britischer Logiker und Mathematiker. Turing ist einer der einflussreichsten Theoretiker, der sich mit der frühen Informatik und auch Computerentwicklung beschäftigte.

Seinen hohen Bekanntheitsgrad erlangte er auch dadurch, dass er das Berechenbarkeitsmodel der Turingmaschine entwickelte. So wurde nach ihm der Turing-Preis benannt, wobei es sich um die bedeutendste Auszeichnung im Fach Informatik handelt und auch der Turing-Test, der zum Nachweis künstlicher Intelligenz eingesetzt wird, ist nach ihm benannt wurden. Im Zweiten Weltkrieges war er grötenteils an der Entzifferung der mit der Enigma verschlüsselten deutschen Funksprüche beteiligt.

Quelle: http://de.wikipedia.org/wiki/Alan_Turing

Turing – Berechenbarkeit | Seminar 12.12.2006

Die Turingmaschine ist von dem britischen Mathematiker Alan Turing 1936 entwickelt wurden. Hierbei handelt es sich um ein mathematisches Modell, welches dazu dient, eine Klasse von berechenbaren Funktionen bilden zu können.

Quelle: http://dept-info.labri.fr/~gavoille/img/turing.gif

Die Besonderheit der Turingmaschine ist, dass sie jegliche Probleme mit nur drei Rechenvorgängen, dem Lesen, Schreiben und und letztendlich mit dem Bewegen des Kopfes, lösen kann. So können bekannte mathematischen Grundfunktionen, wie beispielsweise die Addition oder auch die Multiplikation mit eben diesen drei Operationen simuliert werden.

Die Turingmaschine besteht aus einem Speicherband mit einzelnen Feldern, in welchem je ein Zeichen gespeichert werden kann. Des Weiteren existiert ein Lese- und Schreibkopf, der von einem Programm gesteuert wird, der sich auf dem eben erwähnten Speicherband feldweise bewegen und die darauf befindlichen Zeichen verändern kann.

- Vorgang innerhalb der Maschine:
Zustand jetzt -> gelesenes Zeichen -> Zustand neu -> Bewegung des Lese- und Schreibkopfes -> ausgegebenes Zeichen

Die Turingmaschine führt ihre Berechnungen schrittweise aus, indem sie eine Eingabe in eine Ausgabe umwandelt. So wird erst die Eingabe, dann die Zwischenergebnisse und zum Schluss die Ausgabe auf dem Band gespeichert.

Bildquelle: http://de.wikipedia.org/wiki/Bild:Turingmaschine.png

Mouse Interaction (Aufg. 7)

13.12.1006

(a) Nehmt Euch das Beispiel “MouseFunctions” aus der Processing-Sammlung vor.

(a1) Beschreibt zunächst, was der Gesamteffekt, die Wirkung von MouseFunctions ist.

Bei der diesem Beispiel ist eine kann man ein graues Quadrat auf schwarzem Hintergrund sehen, welches sich beim Aufruf der Funktion in der Mitte der Fläche des Programms befindet. Wenn man nun die Maus als Interaktionsmedium verwendet, kann man feststellen, dass bei einem „rollover“ der Maus sich der Rahmen des Quadrates weiß färbt. Drückt man noch auf das Quadrat, wird das gesamte Quadrat in weiß eingefärbt.
Bei anschließend festgehaltener Maustaste kann das Quadrat innerhalb der Programmfläche hin und her bewegt werden, abhängig von den Bewegungen der Maus verfolgt das Quadrat diese. Beim Loslassen der Maus, bleibt das Quadrat auf der Stelle bei diesen Koordinaten stehen und das Quadrat wird wieder grau, ausgenommen von dem Rahmen. Verlässt anschließend die Maus die Quadratfläche ändert sich die Rahmenfarbe ebenfalls zurück in den Ausgangszustand.
Dieser Vorgang mit der Maus-, Quadratinteraktion kann nachfolgend jederzeit wiederholt werden. Wobei dann das Quadrat nicht mehr am Ausgangspunkt, der Mitte steht, sondern da, wo die Maus es als letztes losgelassen hat.

(a2) Sagt nun, was setup bewirkt.

Die Funktion setup() ist die Einstiegsfunktion bei Processing und legt die Ausgangssituation für ein Programms fest.
Hier wird alles definiert, was zu Beginn des Programms zu sehen sein soll, ohne jegliche Interaktion. Diese Funktion wird auch nur einmal, zum Start des Programms durchlaufen, anschließend nicht mehr.
In diesem Beispiel, „mouse functions“, besteht die Funktion aus 4 Anweisungen.

Mouse Interaction (Aufg. 7)

Ada Loveless

- war 1843 die erste Programmiererin
- schrieb ein Programm, wie die „Analytical Engine“ programmiert werden könnte
- am 10. Dezember 1815 in Augusta Ada Byron geboren
- einzige Tochter vom Poet George Gordon Noel (Lord Byron) und Tochter von Annabella Milbanke

Quelle: http://homepages.rootsweb.com/~lovelace/adabyron.htm

Formale Sprachen | Seminar 05.12.2006

- Maler und Programmierer machen Kopfgeburten
- Ada Loveless war die erste Programmiererin, Erfindung der Programmiersprache Ada

- Programmieren:

• ist ein definierter, fester Begriff
• erwerben von Fertigkeiten durch eigenes Handeln

- Bilder:

• kann man nur deuten, offener Begriff, nur ein Annähern ist möglich
• erwerben von Begrifflichkeit

- Iteration:

• ist eine Abfolge von Schritten
• Abfolge => Folge
• Schritte => Anweisungen
• Eine Iteration ist die wiederholte Anwendung einer Operation auf einen Operanden. Operation und Operand können beliebig komplex sein.

- Index: darüber kann eine Variable nochmal variabel gemacht werden, z.B. Xi+1
Angabe einer endlichen Folge: i = i(1)n => eine Folge von 1 bis n in einer Schritten
Angabe einer unendlichen Folge: i=1,2,3,…
- Behandlung der Satzbildung durch festgelegte Regeln

Gedichte (Aufg.6)

Datum: 05.12.2006

a) Interpretiert eines der vorgegebenen Gedichte!

Ich habe mich für eine Interpretation des ersten Gedichtes entschieden, da dieses mich durch sein Wortspiel sehr angesprochen hat und für mich, durch die Art und Weise des Wortspiels, auch den Bezug zur Programmierung herstellt.
In dem nebenstehenden Gedicht wird in den ersten zwei Zeilen auf die gleiche Art und Weise der Begriff “wort” durch die Wörter “spiele” und “schatten” definiert, wobei aus der Definition wiederum der Begriff “wort” wird.
In den anschließenden Fersen werden beide Definitionen in einem Fers vereint, aber jeweils auf einer eigenen Zeile platziert. Im regelmäßigen Wechsel steht dann mal das Wort “schatten” in der ersten Zeile und dann wieder der Begriff “spiele”.
Letztendlich besteht das gesamte Gedicht nur aus fünf einzelnen Wörtern, die beliebig kombiniert werden können. Aus diesem Grund sehe ich ein solches Gedicht auch für die Programmierung als
geeignet. Wobei ich der Meinung bin, dass man nicht jedes beliebige Gedicht, wie es ein Autor schreiben würde, auch programmieren kann. Oftmals steht für jedes einzelne Wort etwas Tiefsinnigeres dahinter, was in diesem Gedicht nicht unbedingt der Fall ist.