« »

Zusammenfassung vom Unterkapitel Automatentheorien und -simulationen

13. Mai 2009 Roland

Dieser Artikel ist Teil 10 von 12 der Artikelserie Handbuch für Fachinformatiker

Handbuch für Fachinformatiker

Ein Unterkapitel der Mathematischen und technische Grundlagen sind Automatentheorien und -simulationen.
Um die Funktionsweise von Computern nachvollziehen zu können, wurden im Lauf ihrer Entwicklungsgeschichte zahlreiche mathematisch-theoretische Modelle entworfen, die die grundlegenden Arbeitsschritte einer solchen Maschine verdeutlichen sollen.
Automatentheorien beschreiben nicht die elektrotechnischen Details von Computern, sondern die mathematischen Aspekte ihrer Funktionsweise. Somit sind Automatentheorien Algorithmentheorien, welche auf vielen verschiedenen Rechnern angewendet werden können.
Nehmen wir uns also vorerst mal den endlichen Automat nach Turing vor.

Die Turing Maschine

Zuerst einmal erhielt die Turing Maschine ihren Namen von ihrem Entwickler. Alan Turing. Dieser Herr kam während des zweiten Weltkriegs zu sehr viel Ruhm, da er eine Schlüsselfigur war bei der Entschlüsselung der deutschen Chiffriermaschine Enigma.
Einer der ersten von Turing erstellten Algorithmen wurde eingesetzt um ein Gespräch zu simulieren. Dabei wurden eingegebene Texte in Rückfragen umgewandelt. Hier ein Auszug:

Der User gibt ein: I am afraid of computers.
Das Programm Antwortet: You have your mind on computers, it seems.
User: Yes.
Programm: I see...  Well, why do you say this is so?
User: Because computers make me nervous.
Programm: Is it because computers make you nervous that you came to me?
...usw.

Das Aussehen der Maschine wird ähnlich einer “Schreibmaschine” beschrieben. Doch man tut sich denke ich einfacher, wenn man sich die Turing-Maschine nicht als Maschine sondern eher als eine Methode mathematischen Denkens vorstellt.

Was macht diese Maschine

Je nach gelesenem Zeichen und je nach bisherigem Zustand wird die Maschine in verschiedene definierte Zustände versetzt. Die Zustände bestehen beispielsweise in der Bewegung des Bandes in eine der beiden Richtungen, das Lesen des jeweils nächsten Zeichens, das Schreiben eines Zeichens und so weiter. Ein spezielles Zeichen muss die Maschine jeweils in den Zustand “Programmende” schalten.
Die Tatsache, dass es endlich viele verschiedene Zustände gibt, in denen sich eine solche Maschine befinden kann, begründet die Bezeichnung “endlicher Automat”.
Dieser Automat nimmt also Eingaben entgegen und liefert festgelegte Werte zurück, bis schließlich das Ende des Programms erreicht wurde.

Wozu braucht man einen Turing Test

Turing-Maschinen sind in der Lage, jedes beliebige berechenbare Problem zu lösen. Deshalb ist ein wichtiges Kriterium für die Funktionalität einer Programmiersprache die Frage, ob sie Turing-vollständig ist, das heißt alle Probleme lösen kann, mit denen auch die Turing-Maschine zurechtkommt.

Warum wird diese Maschine erwähnt und was bringt sie mir

Vielleicht ja so.
Ich hinterlege in meiner Maschine folgendes.

Du erhälst als Eingabe Und dafür erhalte ich als Ausgabe
Q H
K A
P L
Z O

somit kann sich hinter einer nicht sinnvollen Zeichenkette wie “QKPPZ” doch etwas sinnvolles, wie “HALLO” verbergen.
Was kann man noch? Ich möchte Telefonnummern kopieren. Also soll meine Maschine die Nummern einlesen und genauso auch wieder ausgeben. Da ich in meiner Tabelle das auch so hinterlegt habe ist das kein Problem.
Somit ist festzustellen, dass man prinzipiell in jedem Rechner eine Turing-Maschine findet. Der Rechner nimmt also eine Eingabe entgegen und verarbeitet diese nach festgelegtem Ablauf und schreibt dann etwas zurück.
Dadurch ergibt sich die Möglichkeit die Tabellen so zu erweitern, das ich die Kopierfunktion zum Multiplizieren nutzen kann. Kopiere die eingegebene Zahl n-mal und ich kann somit ein passendes Ergebnis erhalten.
Man kann also erkennen, dass sich hinter komplizierten Vorgängen meist nur einfache Logiken verbergen. Und setzt man mehrere einfache Logiken zusammen kann man evtl. eine anfangs schwierig erscheinende Anforderung doch lösen. Oder aber andersherum, indem man ein nicht zu verstehendes Problem in mehrere kleinere, verständliche “Probleme” auseinander nimmt.

Merken und weiterempfehlen Diese Icons verlinken auf Bookmark Dienste bei denen Nutzer neue Inhalte finden und mit anderen teilen können.
  • Technorati
  • Wikio DE
  • Webnews
  • MisterWong
  • Y!GG
  • Digg
  • del.icio.us

Der Beitrag wurde am Mittwoch, den 13. Mai 2009 um 18:48 Uhr veröffentlicht und wurde unter Azubi-Ecke, Handbuch für Fachinformatiker abgelegt.
Kurzlink: http://www.baldenhofer.eu/blog/?p=1027

Dir gefiel der Artikel? Dann abonniere doch den RSS Feedrss

Du kannst die Kommentare zu diesem Eintrag durch den RSS 2.0 Feed verfolgen. Du kannst einen Kommentar schreiben, oder einen Trackback auf deiner Seite einrichten.

2 Reaktionen zu “Zusammenfassung vom Unterkapitel Automatentheorien und -simulationen”

  1. roland sagt:
    13. Mai 2009 um 19:20

    Wau dicker Text!
    Du hast sehr schön die Touring Maschinen beschrieben. Die Dinger sind nicht sehr einfach zu verstehen. Doch du hast es wohl geblickt!
    Ich würde diesen Artikel jedoch nicht Zusammenfassung nennen. Das ist wohl eher eine Jozo Interpretation oder?
    Weiter so!

  2. roland sagt:
    17. Mai 2009 um 22:02

    Schade, auch hier sind ganze Sätze direkt kopiert.
    Jozo, dass macht man nicht. Das ist nicht mal schlechter Stil.
    Die Prinzen haben zwar gesungen “Das ist alles nur geklaut, dass ist alles gar nicht meines” und landeten damit einen Hit.
    Aber die haben es selbst erfunden und ich habe sie zitiert.
    Alles klar?
    Also, auch diesen Text überarbeiten.
    Schreib was du verstanden hast und klau nicht irgendwas aus dem Fachbuch oder sonst wo zusammen.
    Das haben wir nicht nötig.

Schreibe mir

zum Seitenanfang