Auswahl Aktion im Forum Suche Kontakt Für Mitglieder Mathematisch für Anfänger Wer ist Online | |
| Autor |
  Vergleich verschiedener computationaler Modelle |
|
Mych
Aktiv 
Dabei seit: 09.07.2009
Mitteilungen: 295
Aus: Zürich
 |      Themenstart: 2012-07-19 23:26
|
Hi
Wir sollen im Rahmen einer Prüfung in der theoretischen Informatik unter anderem versch. Berechenbarkeitsmodelle miteinander vergleichen. Wir haben dabei u.a. die folgenden Modelle behandelt: Turingmaschinen, Lambda-Kalkül, Cellular Automata, Boolean Circuits, Tilings, Finite State Machines...
Ich finde die Frage zum Vergleich der Modelle persönlich bereits interessant. Obwohl ich zB gelesen habe, dass man Turingmaschinen als konkrete Angabe eines Berechenbarkeitsvorganges und beispielweise das Lambda-Kalkül als eine abstraktere Form auffassen kann, war ich von dieser Unterscheidung nicht wirklich überzeugt.
Meiner Meinung nach ist zB auch der Beschrieb der Ausgestaltung einer Turingmaschine nichts anderes als die Definition der Syntax. Zudem stimmen die beiden Modelle in Bezug auf ihre "Extension" überein, da sie offensichtlich die gleiche Klasse an Funktionen berechnen.
Später ist mir aber das Beispiel aus der Mathematik eingefallen, die eulersche Zahl auf verschiedene Arten zu definieren - die je nach Definition (über Grenzwert einer Folge oder in Zusammenhang mit Primzahlen) eben doch einen neuen Erkenntnisgewinn mit sich bringt..
Was denkt ihr - welche sind die sinnvollen Arten, solche Modelle zu unterscheiden, mal von den "offensichtlichen" Unterschiede bzgl. Komplexität abgesehen?
Danke und Lg
|
 Profil
 Quote
 Link |
Bilbo
Senior 
Dabei seit: 03.01.2005
Mitteilungen: 1749
Aus:
 | Beitrag No.1, eingetragen 2012-07-20 00:45
|
Hallo Mych,
ich würde sagen, ein wichtiges Kriterium für die Unterscheidung dieser Modelle ist, was man mit ihnen "praktisch" besonders gut machen kann. Obwohl die Berechnungsstärke des Lambda-Kalküls und der Turingmaschinen theoretisch gleich groß ist, gibt es doch Unterschiede in der Lesbarkeit und "Eleganz" der Darstellung von Funktionen in den beiden Modellen. Die Addition zum Beispiel mag im Lambda-Kalkül verständlicher ausgedrückt werden als mit einem Turingmaschinenprogramm. Wenn man sich Wortfunktionen anschaut, etwa die Funktion, die aus einem Binärwort w alle Nullen löscht, so ist ein Turingmschinenprogramm dafür recht schnell geschrieben; um diese Funktion im Lambda-Kalkül auszudrücken, muss man mit den Kodierungen von Binärwörtern durch Zahlen arbeiten, was die Sache sehr undurchsichtig macht.
Eleganz und Lesbarkeit sind ja nicht umsonst Kriterien, die auch bei der Entscheidung für eine bestimmte Programmiersprache in der Praxis eine wichtige Rolle spielen.
Ich hoffe, diese Antwort zielt in etwa auf das ab, was du wissen wolltest.
Viele Grüße,
Thorsten
-----------------
Heilmagier der Drachengilde
Wohlordner des Universums
Rechner des Unberechenbaren
Navigator Irrlichts im Ozean der Rätsel
|
Profil
Quote
Link |
Mych
Aktiv
Dabei seit: 09.07.2009
Mitteilungen: 295
Aus: Zürich
| Beitrag No.2, vom Themenstarter, eingetragen 2012-07-20 09:50
|
Ciao Thorsten,
Vielen Dank für den Input.
Das sind sicher gute Kritierien, da hast du recht.
Mich hat aber auch insbesondere interessiert, ob es neben den pragmatischen Unterscheidungen auch theoretische gibt, insofern als das verschiedene Modelle neue Erkenntnisse hinsichtlich der Berechenbarkeitstheorie oder den berechneten Funktionen bringen könnten? (Ich hab selbst den Eindruck, dass dem nicht so ist, bzw wüsste ich nichts davon..).
Viele Grüsse,
-M
[ Nachricht wurde editiert von Mych am 20.07.2012 09:51:17 ]
|
Profil
Quote
Link |
|
Wie unterstütze ich den Matheplaneten mit Geld?
[Neues Thema]