imported>Trustable: Redundanzbaustein entfernt

2019-03-05T16:44:40Z

Redundanzbaustein entfernt

Neue Seite

Unter '''Verfeinerung''' versteht man in der [[Informatik]] ein Verfahren, bei dem aus einer abstrakten Beschreibung (z. B. [[Registermaschine]], [[formale Spezifikation]] mittels [[Z-Notation]]) eine konkretere Beschreibung abgeleitet wird. Eine Verfeinerung erhält dabei in der konkreten Beschreibung (bestimmte) Eigenschaften der abstrakten Beschreibung.

== Verfeinerung bei Registermaschinen ==

Unter der '''Verfeinerung''' versteht man in der [[theoretische Informatik|theoretischen Informatik]] ein Verfahren, aus verallgemeinerten [[Registermaschine]]n korrekte, einfache Registermaschinen zu konstruieren.

=== Einfache Registermaschine ===

Die einfache Registermaschine kennt nur die Befehle

:<math>\mbox{Register}_k := \mbox{Register}_k + 1</math>,

:<math>\mbox{Register}_k := \mbox{Register}_k \dot - 1</math>

und den Test

:<math>\mbox{Register}_k = 0 ?</math>,

wobei
:<math>x \dot - 1 = \begin{cases} x - 1, & \mbox{wenn}\, x > 0\ \\ 0, & \mbox{sonst}\end{cases}</math>
die arithmetische Differenz ist.

Durch diese Definition der Subtraktion erreicht man, dass man innerhalb der [[natürliche Zahl|natürlichen Zahlen]] bleibt.

=== Registermaschinen für weitere Funktionen ===

Hat man nun eine Registermaschine geschrieben, die in der Lage ist, beispielsweise zwei Zahlen a und b zu addieren, dann kann man künftig in jeder Registermaschine unmittelbar zwei Register addieren: Man könnte an stelle dieser unmittelbaren Addition auch die Registermaschine für die Addition zweier Zahlen a und b einsetzen.

Diesen Schritt nennt man Verfeinerung.

Eine Registermaschine, die noch verfeinert werden muss, nennt man verallgemeinerte Registermaschine.

=== Bedeutung ===

Durch die Verfeinerung wird es einfacher, zu einer Funktion eine übersichtliche, lesbare und kurze Registermaschine anzugeben. Ein Beispiel zeigt der Beweis der Berechenbarkeit der [[Cantorsche Paarungsfunktion|Cantorschen Paarungsfunktion]].

== Literatur ==

* Klaus Weihrauch: ''Computability''. Springer, Berlin u. a. 1987, ISBN 3-540-13721-1, (''EATCS monographs on theoretical computer science'' 9).
* Katrin Erk, Lutz Priese: ''Theoretische Informatik. Eine umfassende Einführung''. 2. erweiterte Auflage. Springer, Berlin u. a. 2002, ISBN 3-540-42624-8, (''Springer-Lehrbuch'').
* [[Uwe Schöning]]: ''Theoretische Informatik – kurzgefasst'', 4. Auflage. Korrigierter Nachdruck. Spektrum, Heidelberg u. a. 2003, ISBN 3-8274-1099-1, (''Hochschultaschenbuch'').

[[Kategorie:Theoretische Informatik]]

Verfeinerung (Informatik) - Versionsgeschichte

imported>Trustable: Redundanzbaustein entfernt