Home About us Products Services Contact us Bookmark
:: wikimiki.org ::
Berechenbarkeit

Berechenbarkeit

Unter Berechenbarkeit versteht man in der Berechenbarkeitstheorie eine Eigenschaft einer Funktion mittels einer abstrakten und mechanischen Vorgehensweise zu gegebenen Eingaben ihre Ausgabe zu berechnen. Die Vorgehensweise wird als Algorithmus bezeichnet und muss exakt definiert sein, da davon abhängt, welche Funktionen berechenbar ist und welche nicht. Es gibt eine ganze Reihe von Algorithmusbegriffen, die gleichmächtig sind und für die bisher noch keine sinnvolle Erweiterung im Sinne des Berechenbarkeitsbegriffs gefunden werden konnte. Ein Beispiel dafür ist die Turingmaschine. Die Church-Turing-These erklärt diese zu einem rechnenden Menschen gleichwertig. Es gibt auch schwächere Algorithmusbegriffe als Turingmaschinen. Dazu gehören zum Beispiel die Loop-Programme. Diese können zum Beispiel die turing-berechenbare Ackermann-Funktion nicht berechnen. Berechenbarkeit ist nicht mit Entscheidbarkeit zu verwechseln. Bei der Entscheidbarkeit ist gefragt, ob es zu einer Funktion einen Algorithmus gibt, der stets nach endlicher Bearbeitungszeit die Ausgabe der Funktion liefert. Bei einer partiellen Funktion können Ausgabewerte zu bestimmten Eingaben auch nicht definiert sein (vergleiche div-Funktion weiter unten). Der Algorithmus terminiert in solchen Fällen nicht. Dennoch ist die Funktion berechenbar, da das unendliche Weiterrechnen des Algorithmus einer nicht definierten Funktionsausgabe entspricht. Das Halteproblem zum Beispiel, ist daher zwar nicht entscheidbar, aber durchaus berechenbar.

Formale Definition

Eine Funktion f : \mathbb^k \rightarrow \mathbb heißt berechenbar, wenn es einen Algorithmus gibt, der bei Eingabe von \left( n_1, ..., n_k \right) \in \mathbb^k nach endlicher Zahl von Schritten f \left( n_1,... , n_k \right) berechnet, sofern f \left( n_1,... , n_k \right) definiert ist und andernfalls nicht terminiert.

Zahlenfunktionen

Definition berechenbarer Funktionen mit Registermaschinen

Eine Funktion f : \mathbb^k \rightarrow \mathbb ist berechenbar genau dann, wenn es eine k-stellige Registermaschine M gibt, deren Maschinenfunktion mit f übereinstimmt, also f = f_M gilt. Z.B. ist die Funktion :f(x) = \mbox (die für kein Argument terminiert) berechenbar, da es eine entsprechende Registermaschine gibt.

Definition mit WHILE Programmen

Eine Funktion f (wie oben) ist berechenbar genau dann, wenn es ein WHILE-Programm P gibt, mit : f = AC \circ \tau(P) \circ EC. Dabei ist EC die Eingabecodierung, AC die Ausgabecodierung und \tau(P) die von P über die Semantik realisierte Maschinenfunktion.

Definition durch Rekursion

Seien \mu, Sub und Prk die Operationen der \mu-Rekursion, der Substitution und primitiven Rekursion. Funktionen, die sich aus der Menge der primitiv-rekursiven Grundfunktionen durch wiederholtes Anwenden dieser Operatoren erzeugen lassen, heißen µ-rekursiv. Die Menge der \mu-rekursiven Funktionen ist genau die Menge der berechenbaren Funktionen.

Übergang von einstelligen zu mehrstelligen Funktionen

Über die cantorsche Paarungsfunktion führt man den Begriff der Berechenbarkeit einer k-stelligen Funktion auf den der Berechenbarkeit von einstelligen Funktionen zurück. Insbesondere kann man damit in natürlicher Weise definieren, welche Funktionen auf den rationalen Zahlen berechenbar sind.

Wortfunktionen

Die Berechenbarkeit von Wortfunktionen lässt sich entweder mit Hilfe von Turingmaschinen oder Bandmaschinen zeigen. Alternativ führt man eine Standardnummerierung über die Wörter über \Sigma^
- ein und zeigt, dass die so erzeugten Zahlenfunktionen berechenbar sind. Zudem lassen sich geeignete Wörter definieren, die eine schnell konvergierende Approximation von reellen Zahlen darstellen. Über solche Wörter lässt sich der Berechenbarkeitsbegriff auf die Menge der reellen Zahlen ergänzen.

Spezielle Probleme

Eine Kuriosität ist, dass ein spezielles, also ein Problem mit nur einer Instanz, immer berechenbar ist. Man könnte auch sagen, dass es für jede Funktion die keine Parameter hat, einen Algorithmus gibt, der diese Funktion berechnet. Das klingt verwirrend, ist aber trivial. Angenommen, die Frage lautet "gibt es Gott", und die Definition von "Gott" sei in irgendeiner Form vorgegeben. Diese Frage repräsentieren wir durch die (parameterlose) Funktion g(). Die Antwort muss nun entweder ja oder nein lauten – und für beide Antworten lässt sich leicht ein Algorithmus konstruieren, der die korrekte Antwort ausgibt. Es gibt also immer einen solchen Algorithmus, wir wissen nur nicht, welcher es ist. Würden wir das gleiche Problem allgemein stellen, so dass die Definition von Gott (nennen wir sie d) als Eingabe des Algorithmus verlangt ist (also ein Parameter der Funktion g wäre), so wäre die resultierende Aussage g(d) nicht berechenbar. Das gleiche gilt natürlich auch für Fragestellungen aus weniger esoterischen Bereichen.

Siehe auch


- These von Church
- Berechenbarkeitstheorie
- Halteproblem
- Entscheidungsproblem
- Gödelscher Unvollständigkeitssatz
- Semi-entscheidbare Menge
- Berechenbare Funktion
- Berechenbare Folge
- Berechenbare Zahlen Kategorie:Rekursionstheorie Kategorie:Theoretische Informatik

Berechenbarkeitstheorie

Die Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik, der sich mit dem Begriff der Berechenbarkeit befasst, insbesondere welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modelles einer Maschine) lösbar sind. Sie ist eng verwandt mit der formalen Semantik, richtet aber die Aufmerksamkeit mehr auf die Terminiertheit von Programmen und Algorithmen. Auch verwendet sie als Ausgangspunkt die verschiedenen Modelle von Maschinen, und nicht die abstrakteren Spezifikationssprachen.

Hauptfragen


- Wie kann man den Begriff der Berechenbarkeit formalisieren?
- Welche Art Aufgaben kann welche Klasse von Maschinen lösen? Insbesondere werden deterministische und nichtdeterministische Varianten folgender Modelle untersucht:
  - endlicher Automat
  - Kellerautomat
  - Linear beschränkte Turingmaschine (LBA)
  - Turingmaschine
  - Registermaschine
- Welche Art Probleme würden leistungsfähigere Maschinen benötigen?

Welche Art Aufgaben kann eine Turingmaschine lösen?

Nicht alle Aufgaben können gelöst werden. Ein unentscheidbares Problem ist eines, das nicht durch einen Algorithmus gelöst werden kann, auch wenn unbeschränkt Zeit und Geld zur Verfügung steht. Man kennt viele unentscheidbare Aufgaben. Z. B. kann das spezielle Entscheidungsproblem nicht gelöst werden: Gegeben ist eine Aussage der Prädikatenlogik erster Ordnung. Aufgabe ist es zu entscheiden, ob die Aussage allgemein gültig ist. Church und Turing haben unabhängig nachgewiesen, dass diese Aufgabe nicht gelöst werden kann. Ein weiteres Problem ist das Halteproblem, siehe dort.

Andere Modelle für Berechenbarkeit mit gleicher Leistungsfähigkeit


- Turingmaschine mit mehreren Bändern
- Turingmaschinen mit einem zweidimensionalen "Band"
- Registermaschinen
- Erweitereter Kellerautomat mit zwei Kellerspeichern
- Endlicher Automat mit zwei Zählern
- Typ-0-Grammatiken
- Lambda-Kalkül
- rekursive Funktionen
- Erweiterte Petri-Netze mit Sperrkanten
- Markow-Algorithmen
- die meisten modernen Programmiersprachen

Welche Aufgaben können durch weniger leistungsfähige Maschinen gelöst werden?

Die Chomsky-Hierarchie beschreibt diejenigen formalen Sprachen, die durch vier Klassen von Algorithmen erkannt werden können. Sie alle setzten einen nichtdeterministischen endlichen Automaten voraus mit einem Speicher. Wenn der Speicher unendlich groß ist, dann entspricht die Situation der Turingmaschine. Wenn der Speicher proportional zur Größe der Eingabezeichenkette ist, dann können kontext-abhängige Sprachen erkannt werden. Wenn der Speicher nur einen Stapel umfasst, dann können kontextfreie Sprachen erkannt werden. Wenn die Maschine nur einen endlichen Speicher hat, dann können nur Sprachen, die durch reguläre Ausdrücke definiert sind, erkannt werden.

Zusammenhang mit der Physik

Dem Physiker Richard Feynman fiel auf, dass Computer ziemlich schlecht sind, Problemstellungen aus der Quantenmechanik zu berechnen. Ein wichtiger Vortrag von ihm hierzu aus dem Jahre 1981 hatte den Titel :Can (quantum) physics be (efficiently) simulated by (classical) computers? Offenbar kann die Natur den Ausgang eines quantenmechanischen Experimentes schneller ausrechnen, als wir dies mit einem Computer können. Daher schlug er vor, einen besonderen Computer zu bauen, einen Quantenprozessor. Dessen Rechenwerk sollte quantenmechanische Prozesse nutzen, um Ergebnisse für quantenmechanische Probleme effizienter zu berechnen. Dabei wurde dann irgendwann klar, dass die einfachen mathematischen Modelle der theoretischen Informatik eigentlich nur mit einer Teilklasse der realen Computer korrespondieren können, weil man nicht alle physikalischen Möglichkeiten ausgeschöpft hatte. Diese neue Klasse von Computern wird als Quantencomputer bezeichnet.

Literatur

Tony Hey: Richard Feynman and Computation, Contemporary Physics, 1999, Volume 40, number 4, p. 257-265,

Andere Namen

Der früher verwendete Begriff Rekursionstheorie meint heute das gleiche, wie Berechenbarkeitstheorie, da die rekursiven Funktionen gerade die berechenbaren Funktionen sind. Einige Autoren verwenden den Begriff Rekursion, um nur die Funktionen mit explizitem Selbstbezug zu kennzeichnen. Kategorie:Theoretische Informatik ja:計算可能性理論 th:ทฤษฎีการคำนวณได้

Input

Unter Input (engl. für Eingabe, Einspeisung) versteht man
- Im Berufsleben die Arbeit oder geistige Energie, die man in die Firma, Abteilung etc. einbringt,
- in der Wirtschaft die Produktionsfaktoren (wie z.B. Arbeit und Kapital), die zur Herstellung eines Produktes (Output) verwendet werden,
- in der EDV die Eingabe von Daten oder anderen Werten (manuell mittels Tastatur, von Dateien und Datenträgern, mit Maus usw.), bzw. auch von Programmen,
- in der Mathematik die einzuführenden Werte der Parameter. Das Gegenteil von Input ist Output.

Algorithmus

Unter einem Algorithmus versteht man allgemein eine genau definierte Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen. Im täglichen Leben lassen sich leicht Beispiele für Algorithmen finden: Zum Beispiel ist ein Kochrezept ein Algorithmus – zumindest dann, wenn alle Angaben genau genug sind und es für alle Teilaufgaben, wie Braten, Rühren, etc., ebenfalls Algorithmen gibt. Auch Reparatur- und Bedienungsanleitungen oder Hilfen zum Ausfüllen von Formularen sind in der Regel Algorithmen. Ein weiteres, etwas präziseres Beispiel sind Waschmaschinenprogramme. Algorithmen können in Programmablaufplänen nach DIN 66001 oder ISO 5807 grafisch gezeichnet werden.

Geschichte

Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens von Muhammad ibn Musa al-Chwarizmi (
- ca. 783, † ca. 850), dem Autor des Buchs Hisab al-dschabr wa-l-muqabala (825, Regeln zur Wiederherstellung und Reduktion), durch das die Algebra im Westen verbreitet wurde. Die lateinische Fassung beginnt mit „Dixit Algorithmi...“ (Algorithmus sprach...), womit der Autor gemeint war. Das Wort Algebra stammt ebenfalls (al-Jabr – „Einrenkung“) aus dem Titel des Buches. Ursprünglich stand das Wort Algorism nur für die Regeln zur Arithmetik mit arabischen Ziffern. Heute steht es für alle geregelten Prozeduren, mit denen Probleme aller Art gelöst werden können.

Informatik und Mathematik

Vor allem aber sind Algorithmen eines der zentralen Themen der Informatik und Mathematik. Sie sind Gegenstand einiger Spezialgebiete der Theoretischen Informatik, wie der Algorithmentheorie, der Komplexitätstheorie und der Berechenbarkeitstheorie. In Form von Computerprogrammen und elektronischen Schaltkreisen steuern sie Computer und andere Maschinen.

Algorithmus und Programm

Für Algorithmen gibt es unterschiedliche formale Repräsentationen. Diese reichen vom Algorithmus als abstraktes Gegenstück zum konkret auf eine Maschine zugeschnittenen Programm (d. h., die Abstraktion erfolgt hier im Weglassen der Details der realen Maschine, das Programm ist eine konkrete Form des Algorithmus, angepasst an die Notwendigkeiten und Möglichkeiten der realen Maschine) bis zur Ansicht, Algorithmen seien gerade die Maschinenprogramme von Turingmaschinen (wobei hier die Abstraktion in der Verwendung der Turingmaschine an sich erfolgt, d. h., einer idealen mathematischen Maschine).

Erster Computeralgorithmus

Der erste für einen Computer gedachte Algorithmus wurde 1842 von Ada Lovelace, in ihren Notizen zu Charles Babbages Analytical Engine, festgehalten. Sie gilt deshalb als die erste Programmiererin. Weil Charles Babbage seine Analytical Engine nicht vollenden konnte, wurde Ada Lovelaces Algorithmus nie darauf implementiert.

Formale Definition

Die mangelnde mathematische Genauigkeit des Begriffs Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts. Insbesondere steht die natürliche Sprache mit ihren Unschärfen und Widersprüchlichkeiten der Forderung nach Eindeutigkeit und Widerspruchsfreiheit im Wege.

Turingmaschinen und Algorithmusbegriff

In der ersten Hälfte des 20. Jahrhunderts wurden eine ganze Reihe von Ansätzen entwickelt, um zu einer genauen Definition zu kommen. Formalisierungen des Berechenbarkeitsbegriffs sind die Turing-Maschine (Alan Turing), der Lambda-Kalkül (Alonzo Church), rekursive Funktionen, Chomsky-Grammatiken und Markow-Algorithmen. Es wurde – unter maßgeblicher Beteiligung von Alan Turing selbst – gezeigt, dass all diese Methoden ebenso leistungsfähig (gleich mächtig) sind. Sie können durch eine Turing-Maschine emuliert werden, und sie können umgekehrt eine Turing-Maschine emulieren. Mit Hilfe des Begriffs der Turing-Maschine kann folgende formale Definition des Begriffs formuliert werden: Eine Berechnungsvorschrift zur Lösung eines Problems heißt genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt. Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar: # Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit). # Jeder Schritt des Verfahrens muss auch tatsächlich ausführbar sein (Ausführbarkeit). # Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit, siehe Platzkomplexität). # Das Verfahren darf nur endlich viele Schritte benötigen (Terminierung, siehe auch Zeitkomplexität). Darüber hinaus wird der Begriff Algorithmus in praktischen Bereichen oft auf die folgenden Eigenschaften eingeschränkt: # Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit). # Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).

Church-Turing-These

Die Church-Turing-These lautet: „Jedes intuitiv berechenbare Problem kann durch eine Turingmaschine gelöst werden.“ Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen zu einer Turing-Maschine äquivalenten Formalismus heran, insbesondere die Implementierbarkeit in einer Programmiersprache – die von Church verlangte Terminiertheit ist dadurch allerdings noch nicht gegeben. Der Begriff der Berechenbarkeit ist dadurch dann so definiert, dass ein Problem genau dann berechenbar ist, wenn es einen (terminierenden) Algorithmus zu dem Problem gibt, d. h. wenn eine entsprechend programmierte Turing-Maschine das Problem in endlicher Zeit lösen könnte.

Abstract State Machines

Turingmaschinen harmonieren sehr gut mit den ebenfalls abstrakt-mathematischen berechenbaren Funktionen, reale Probleme sind jedoch ungleich komplexer, daher wurden andere Maschinen vorgeschlagen. Diese Maschinen weichen z. B. in der Mächtigkeit der Befehle ab; anstatt den einfachen Operationen der Turingmaschine können sie z. T. sehr mächtige Operationen, wie z. B. Fouriertransformationen, in einem Rechenschritt ausführen. Oder sie beschränken sich nicht auf eine Operation pro Rechenschritt, sondern ermöglichen sehr parallele Operationen, wie z. B. die Addition zweier Vektoren in einem Schritt. Ein Modell einer realeren Maschine ist die [http://www.eecs.umich.edu/gasm/papers/seqthesis.html Sequential Abstract State Machine (seq. ASM)] mit folgenden Eigenschaften: Ein Algorithmus einer seq. ASM soll
- durch einen endlichen Programmtext spezifiziert werden können
- schrittweise ausgeführt werden können
- für bestimmte Zustände terminieren, muss aber nicht immer terminieren (sinnvolle Gegenbeispiele für die Forderung, dass immer terminiert werden muss, wären z.B. ein Programm das fortgesetzt Primzahlen findet, oder ein Betriebssystem)
- nur begrenzt viele Zustände pro Schritt ändern können (Begrenzung der Parallelität)
- nur begrenzt viele Zustände pro Schritt inspizieren können (Begrenzung der Exploration)

Ein Beispiel: der Euklidische Algorithmus

Der Euklidische Algorithmus, der bereits um 300 v. Chr. beschrieben wurde, dient zur Ermittlung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen A und B: # Sei A die Größere der beiden Zahlen A und B (entsprechend vertauschen, falls dies nicht bereits so ist) # Setze A = A – B # Wenn A und B ungleich sind, dann fahre fort mit Schritt 1, wenn sie gleich sind, dann beende den Algorithmus: Diese Zahl ist der größte gemeinsame Teiler. Beispiel: Es soll der größte gemeinsame Teiler der Zahlen 14 und 8 berechnet werden. Hierzu wird der euklidische Algorithmus verwendet: Das Ergebnis ist also 2.

Eigenschaften

Nichtdeterministische Algorithmen finden vor allem in der Theoretischen Informatik Anwendung, so dass in anderen Bereichen oft vorausgesetzt wird, dass es sich um einen deterministischen Algorithmus handelt. Eine Ausnahme bilden so genannte stochastische, randomisierte oder probabilistische Algorithmen, in die absichtlich ein Zufallsfaktor eingebaut wurde. Solche Algorithmen sind demnach nicht deterministisch und auch nicht determiniert. Stochastische Algorithmen dagegen sind im Allgemeinen deterministisch, orientieren sich aber an Erfahrungswerten. Die verschiedenen formalen Eigenschaften in Kürze:

Determiniertheit

Kurz: Bei jeder Ausführung mit gleichen Startwerten muss das gleiche Ergebnis berechnet werden. Algorithmen sind determiniert, wenn sie bei gleichen Parametern und Startwert stets das gleiche Resultat liefern. Das trifft zum Beispiel nicht für randomisierte Algorithmen zu, bei denen das Ergebnis zu einem gewissen Grad auf Zufall beruht.

Determinismus

Kurz: Es darf immer nur eine Möglichkeit vorhanden sein Deterministisch heißen alle Algorithmen, bei denen zu jedem Zeitpunkt der Ausführung maximal eine Möglichkeit der Programmfortsetzung besteht. Gibt es mehrere Möglichkeiten der Programmfortsetzung und lassen sich diesen Wahrscheinlichkeiten zuweisen, so spricht man von stochastischen, randomisierten oder probabilistischen Algorithmen. In der theoretischen Informatik gibt es neben dem Determinismus auch den Nichtdeterminismus, der aber in der Praxis kaum Verwendung findet. Zusätzliche Bedeutung bekommen solche nichtdeterministische Algorithmen allerdings durch den Einsatz von Quantencomputern, welche auch solche Algorithmen erfolgreich ausführen. Es gilt übrigens: Jeder deterministische Algorithmus ist auch determiniert. Nicht jeder determinierte Algorithmus ist jedoch deterministisch.

Finitheit

Statische Finitheit

Kurz: Die Beschreibung ist endlich. Die Beschreibung eines Algorithmus darf nicht unendlich groß sein. Als statische Finitheit wird die Endlichkeit des Quelltextes bezeichnet. Der Quelltext darf nur eine begrenzte Anzahl, wenn auch bei Bedarf sehr viele Regeln enthalten.

Dynamische Finitheit

Kurz: Fülle an Datenstrukturen und Zwischenspeicherungen sind zu jeder Zeit endlich. Zu jedem Zeitpunkt der Ausführung darf der von einem Algorithmus benötigte Speicherbedarf nicht unendlich groß sein. Andernfalls wäre der Algorithmus nicht ausführbar. Dies wird als dynamische Finitheit bezeichnet.

Terminiertheit

Kurz: Bricht nach endlicher Zeit kontrolliert ab. Algorithmen sind terminierend, wenn sie für jede mögliche Eingabe nach einer endlichen Zahl von Schritten zu einem Ergebnis kommen. Die tatsächliche Zahl der Schritte kann dabei beliebig groß sein. Steuerungssysteme und Betriebssysteme und auch viele Programme, die auf Interaktion mit dem Benutzer aufbauen, erfüllen diese Eigenschaft nicht: Wenn der Benutzer keinen Befehl zum Beenden gibt, läuft das Programm endlos weiter. Donald Knuth schlägt in diesem Zusammenhang vor, nicht terminierende Algorithmen als rechnergestützte Methoden ("Computational Methods") zu bezeichnen. Es ist übrigens im Allgemeinen nicht für jeden beliebigen Algorithmus möglich zu bestimmen, ob er terminiert oder nicht - siehe Halteproblem.

Algorithmenanalyse

Die Erforschung und Analyse von Algorithmen ist Hauptaufgabe der Informatik, und wird meist theoretisch (ohne konkrete Umsetzung in eine Programmiersprache) durchgeführt. Sie ähnelt somit dem Vorgehen in anderen mathematischen Gebieten, in denen die Analyse eher auf die zugrunde liegenden Konzepte als auf konkrete Umsetzungen ausgerichtet ist. Algorithmen werden zur Analyse in eine stark formalisierte Form gebracht und mit den Mitteln der formalen Semantik untersucht. Die Analyse unterteilt sich in verschiedene Teilgebiete. Beispielsweise wird das Verhalten von Algorithmen bezüglich Ressourcenbedarf wie Rechenzeit und Speicherbedarf in der Komplexitätstheorie behandelt, die Ergebnisse werden als asymptotische Laufzeiten angegeben. Der Ressourcenbedarf wird dabei in Abhängigkeit von der Länge der Eingabe ermittelt, d. h. die angegebene Komplexität hängt davon ab, wie groß die Zahlen sind, deren größter gemeinsamer Teiler gesucht wird, oder wie viele Elemente sortiert werden müssen etc. Das Verhalten bezüglich der Terminierung, d. h. ob der Algorithmus überhaupt jemals erfolgreich beendet werden kann, behandelt die Berechenbarkeitstheorie.

Beispiele

Algorithmen in der Wikipedia

In einzelnen Wikipedia-Artikeln gibt es zahlreiche Algorithmen-Beschreibungen, etwa den euklidischen Algorithmus und Quicksort. Eine Übersicht gibt die Liste von Algorithmen und die Kategorie Algorithmus.

Algorithmen im Alltag

Auch im Alltag begegnen uns Algorithmen in Form von Handlungsanweisungen oder Rezepten:

Siehe auch


- Liste von Algorithmen
- Ameisenalgorithmus
- Approximationsalgorithmus
- Datenstruktur
- Determinierter Algorithmus
- Deterministischer Algorithmus
- Entscheidungsproblem
- Evolutionärer Algorithmus
- Greedy Algorithmus
- Heuristik
- Komplexitätsklassen
- MMIX (virtuelle Maschine von Donald E. Knuth zur Darstellung von Algorithmen)
- Online-Algorithmus
- Optimierungsproblem
- Paralleler Algorithmus
- Probabilistischer Algorithmus
- Prozedur (Programmierung)
- Randomisierter Algorithmus
- Sortierverfahren
- Stochastischer Algorithmus
- Suchverfahren

Literatur


- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium. 2002. ISBN 3-8273-7020-5.
- Donald E. Knuth: The Art of Computer Programming, Vol 1–3, Addison Wesley 1998. (Das ist der Standard in dem Bereich; Übersetzung existiert nicht – Juli 2000), ISBN 0201485419
- Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2nd edition 2001, ISBN 0262531968
- Deutsche Übersetzung: Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - Eine Einführung, Oldenbourg Wissenschaftsverlag, 2004, ISBN 3-486-27515-1

Weblinks


- [http://www.grundstudium.info/algorithmen/ Algorithmen in der Informatik]
- [http://www.uni-flensburg.de/mathe/zero/veranst/algorithmen/algo_abschn11/algo_abschn11.html Was ist ein Algorithmus?]
- [http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures] des NIST (englisch)
- [http://www.bullhost.de/a/algorithmus.html Definition] Kategorie:Datenstruktur ja:アルゴリズム ko:알고리즘 th:อัลกอริทึม

Church-Turing-These

Die Church-Turing-These (auch Church'sche These, benannt nach Alonzo Church und Alan Turing) trifft Aussagen über die Fähigkeiten einer Rechenmaschine. Sie lautet: :Die Klasse der Turing-berechenbaren Funktionen ist genau die Klasse der intuitiv berechenbaren Funktionen. Diese These ist nicht beweisbar, da der Begriff intuitiv berechenbare Funktion nicht exakt formalisiert werden kann. Man versteht darunter alle Funktionen, die prinzipiell auch von einem Menschen ausgerechnet werden könnten. Damit setzt man insbesondere keine gewisse Vorstellung voraus, welche Funktionen auf den natürlichen Zahlen berechenbar sind. Es wird in der Informatik üblicherweise angenommen, dass die These stimmt. Dadurch kann es ermöglicht werden, von einer Funktion nachzuweisen, dass sie nicht berechenbar ist.

Entstehung

Turing empfand die Gedankenprozesse eines Menschen beim Zahlenrechnen durch die von ihm entwickelte Turingmaschine nach (in der Funktionsweise ähnlich den heutigen Computern) und analysierte deren Fähigkeiten [1]. Er stellte fest, dass viele Funktionen, die von einem Menschen ausgedacht werden können, erst gar nicht durch die Turingmaschine berechenbar sind, wie z. B. die Funktion des Halteproblems. Zum anderen zeigte sich, dass auch andere Herangehensweisen, die menschliche Denkweise beim Rechnen zu formalisieren, nicht erfolgreicher waren: So wurde von Turing historisch zuerst die Äquivalenz von Churchs Lambdakalkül zur Turingmaschine bewiesen. Es folgten darauf viele weitere vorgeschlagene Algorithmenbegriffe (Rechenmodelle), die alle in ihrer Berechnungsfähigkeit nicht mehr leisteten als die Turingmaschine. Man bezeichnet diese Algorithmenbegriffe demzufolge als Turing-vollständig. Dies ließ vermuten, dass es keinen mächtigeren Formalismus als den der Turingmaschine hinsichtlich der Berechenbarkeit gebe und der Mensch – ebenfalls algorithmisch arbeitend – auch nicht mehr Funktionen ausrechnen könne. Damit entstand die Church-Turing-These.

Implikationen

Falls die These wahr ist, kann es kein Rechenmodell geben, das mehr als die bisherigen Modelle berechnen kann. Insbesondere ist ein Computer ein solches Rechenmodell, somit kann auf ihm theoretisch jeder Algorithmus ausgeführt werden, vorausgesetzt genügend Speicherplatz ist vorhanden. Es ist dann nicht möglich eine Rechenmaschine zu bauen, die mehr berechnen kann als ein Computer bereits kann. Da viele Programmiersprachen ebenfalls turing-vollständig sind, kann man jeglichen Algorithmus mittels eines Quelltexts dieser Sprachen ausdrücken. Insbesondere können sich verschiedene Rechenmodelle gegenseitig simulieren. Bei der erweiterten Church'schen These geht man noch einen Schritt weiter, indem man davon ausgeht das: :Für je zwei Rechenmodelle R_1 und R_2 gibt es ein Polynom p, so dass t Rechenschritte auf R_1 durch p(t) Rechenschritten auf Modell R_2 simuliert werden können. Falls die These falsch ist, gelten die genannten Implikationen nicht. Eine Widerlegung der These wäre mit der Konstruktion eines Hypercomputers möglich, der Berechnungen ausführen kann, die auf einer Turingmaschine nicht möglich sind.

Weitere Algorithmenbegriffe


- partiell-rekursive Funktion
- Registermaschine
- Markow-Algorithmus
- GOTO-Programm
- LOOP-Programm (nicht Turing-vollständig)
- WHILE-Programm

Referenzen und Literatur


- [1] Turing, A.M.: [http://www.abelard.org/turpap2/tp2-ie.asp "On Computable Numbers, with an Application to the Entscheidungsproblem"], 1936.
- Hofstadter, Douglas R.: Gödel, Escher, Bach: ein Endloses Geflochtenes Band, Kapitel 17. Siehe auch: Gödelscher Unvollständigkeitssatz, Philosophie des Geistes Kategorie:Theoretische Informatik Kategorie:Rekursionstheorie ko:처치-튜링 명제

Ackermann-Funktion

Die Ackermannfunktion ist eine 1926 von Wilhelm Ackermann gefundene, extrem schnell wachsende mathematische Funktion, mit deren Hilfe in der theoretischen Informatik Grenzen von Computer- und Berechnungsmodellen aufgezeigt werden können. Heute gibt es eine ganze Reihe von Funktionen, die als Ackermannfunktion bezeichnet werden. Diese weisen alle ein ähnliches Bildungsgesetz wie die ursprüngliche Ackermannfunktion auf und haben auch ein ähnliches Wachstumsverhalten.

Entstehungsgeschichte

1926 vermutete David Hilbert, dass jede berechenbare Funktion primitiv-rekursiv sei. Vereinfacht bedeutet dies, dass sich jede durch einen Computer berechenbare Funktion aus einigen wenigen, sehr einfachen Regeln zusammensetzen lässt und dass sich die Dauer der Berechnung im Voraus abschätzen lässt. Dies trifft auf nahezu alle in der Praxis vorkommenden Funktionen zu. Ebenfalls 1926 konstruierte Ackermann eine Funktion, die diese Vermutung widerlegt, und veröffentlichte sie 1928. Diese Funktion wird heute, ihm zu Ehren, Ackermannfunktion, genannt. Die Ackermannfunktion kann also von einem Computer in endlicher Zeit ausgewertet werden, ist aber nicht primitiv-rekursiv. 1955 konstruierte Rózsa Péter eine vereinfachte Version, die die gleichen Eigenschaften besitzt. Diese Funktion, gelegentlich auch als Ackermann-Péter-Funktion bezeichnet, wird heute vorwiegend benutzt.

Idee

Man betrachtet die Folge a+b, a\cdot b, a^b, \ldots Hierbei wird bei jedem Folgeglied die Operation des vorigen Folgeglieds b mal auf a angewandt, also a\cdot b ist gerade a+a+\ldots +a, wobei die Variable a b-mal vorkommt und so weiter. Die Idee hinter der Ackermannfunktion ist es, diese Folge als Funktion aufzufassen. :Beispiel: Setzt man in obiger Folge a=2 und b=4, so erhält man die Folge: 6, 8, 16, 65536, 2^ (mit 65536 Zweien), ..., die man auch die Ackermannfunktion zu a=2 und b=4 nennt. Die letzte aufgeführte Zahl ist bereits wesentlich größer als die geschätzte Anzahl der Atome im gesamten Weltall. Die Ackermannfunktion, notiert als \phi, ist also eine Funktion, die die folgenden Gleichungen erfüllt: :\phi(ab0) = a+b\, :\phi(ab1) = a \cdot b :\phi(ab2) = a^b\, :\ldots Ab der vierten Zeile können die Funktionswerte nicht mehr mit herkömmlichen Operatoren formuliert werden; man braucht erweiterte Notationen, wie beispielsweise den Hyper-Operator.

Definition und Varianten

Die Ackermannfunktion definiert man üblicherweise rekursiv, d.h., man macht für einige Anfangswerte explizite Angaben und gibt eine Anleitung (das Rekursionsschema), wie man weitere Funktionswerte aus den bereits berechneten erhält.

Definition von Ackermann

Ackermann selbst definierte die Funktion auf recht umständliche Weise, gab aber kurz darauf die folgende äquivalente Definition an. :\phi(ab0)=a+b\, :\phi(a0n+1)=\psi(an)\, :\phi(ab+1n+1)=\phi(a\phi(abn+1),n)\, Dabei ist \psi(an) eine weitere Funktion, die Ackermann nicht weiter beschrieb. (Sie liefert die Startwerte a+0, a\cdot 0, a^0, \ldots.) :Beispiele:
- Möchte man \phi(430) berechnen, so kann man die erste Zeile der Definition anwenden und erhält direkt: \phi(430)=4+3=7.
- Möchte man \phi(402) berechnen, so kann man die zweite Zeile der Definition anwenden und erhält ebenfalls direkt: \phi(402)=\psi(41)=4^0=1. Man beachte, dass in diesem Fall n den Wert 1 hat, da auf der linken Seite der Definition n+1 steht.
- Komplizierter wird es, wenn weder das zweite, noch das dritte Argument 0 ist. Beispielsweise möchte man \phi(412) berechnen. Da sich die ersten beiden Zeilen der Definition nicht anwenden lassen, muss man die dritte verwenden. Damit erhält man: \phi(412)=\phi(4\phi(402)1). \phi(402) wurde aber gerade im vorigen Beispiel berechnet. Setzt man dies ein, so erhält man \phi(412)=\phi(411). Jetzt kann man wieder die dritte Zeile anwenden, dann nochmal die zweite und zuletzt die erste Zeile der Definition. Alles zusammen ergibt in diesem Fall: :: Wenn man vom Wachstum der Ackermannfunktion spricht, meint man oftmals die Funktion f(n) := \phi(nnn).

Definition von Péter

Rózsa Péter definierte 1955 eine einfachere Version der Ackermannfunktion, die nur zwei Parameter besitzt und zudem ohne die Hilfsfunktion \psi auskommt: :\textrm(0m) = m+1\, :\textrm(n+10) = \textrm(n1)\, :\textrm(n+1m+1) = \textrm(n\textrm(n+1m))\, Auch hier meint man im Zusammenhang mit Wachstumsuntersuchungen oftmals die Funktion f(n) := \textrm(nn), wenn man von der Ackermannfunktion spricht. Aus dieser Definition ist nicht sofort ersichtlich, dass die Funktion für alle n und m definiert ist. Das ergibt sich jedoch daraus, dass in jedem Schritt, entweder m verringert oder aber m erhöht und n verringert wird. Jedesmal, wenn m Null erreicht, wird n erniedrigt, also muss auch n irgendwann Null erreichen, und dann liefert die erste Zeile der Definition den Funktionswert. Zu beachten ist allerdings, dass es bei einer Verringerung von m keine obere Schranke für das Wachstum von n in den folgenden Funktionsaufrufen gibt.

Bedeutung in der theoretischen Informatik

Wie eingangs schon erwähnt, erfand Ackermann diese Funktion als Beispiel einer Funktion, die nicht primitiv-rekursiv ist, aber berechenbar. Dies ist auch heute noch das wichtigste Anwendungsgebiet der Ackermannfunktion. Auf der Suche nach den Grenzen von Computern stößt man sehr schnell auf den Begriff der berechenbaren Funktionen. Das sind all die Funktionen, für deren Auswertung man einen Algorithmus angeben kann, also alle Funktionen, die ein Computer berechnen kann. Diese Definition stellt einen sehr schnell vor ein Problem, wenn man von einer konkreten Funktion entscheiden möchte, ob sie berechenbar ist. Findet man einen Algorithmus, der die Funktion berechnet, so ist sie offensichtlich berechenbar. Andernfalls ist ungewiss, ob die Funktion wirklich nicht berechenbar ist oder ob es zwar einen Algorithmus gibt, man ihn aber nicht gefunden hat. Aus diesem Grund sucht man nach alternativen Definitionen, mit denen man einen solchen Nachweis einfacher führen kann. Ein erster Ansatz hierfür waren die primitiv-rekursiven Funktionen. Dies sind Funktionen, die sich durch einige wenige Regeln aus sehr einfachen Funktionen zusammensetzen lassen. Einige Zeit vermutete man, dass alle berechenbaren Funktionen primitiv-rekursiv sind, mit den primitiv-rekursiven Funktionen also ein Werkzeug zur Lösung des oben geschilderten Problems gefunden sei. Diese Hoffnung zerstörte jedoch die Ackermannfunktion, von der man nachweisen kann, dass sie berechenbar, aber nicht primitiv-rekursiv ist. (Siehe nachfolgenden Expertenabschnitt.) Anmerkung: Inzwischen weiß man, dass man aus den primitiv-rekursiven Funktionen die berechenbaren erhält, wenn man noch eine weitere Konstruktionsregel, die sogenannte µ-Rekursion, zulässt.

Beweis

Der Beweis, dass die Ackermannfunktion berechenbar ist, aber nicht primitiv-rekursiv, nutzt im Wesentlichen aus, dass die Ackermannfunktion stärker wächst als jede primitiv-rekursive Funktion.

Anwendungen

Für die Ackermannfunktion gibt es nur sehr wenige Anwendungen. Die zwei wichtigsten sind Benchmarktests für rekursive Aufrufe in Programmiersprachen und Laufzeitabschätzungen der gewichteten Vereinigung und Pfadkompression bei der Union-Find-Struktur.

Benchmark für rekursive Aufrufe

Bei der Einführung von neuen Programmiersprachen, Compilern und Computern möchte man deren Leistungsfähigkeit untersuchen. Dazu werden u.a. mittels Benchmarking durch spezielle Programme festgelegte Eigenschaften überprüft. In diesem Zusammenhang wird die Ackermannfunktion gerne als Benchmark zur Überprüfung von rekursiven Prozedur-Aufrufen benutzt, da ein Programm zur Berechnung der Ackermannfunktion im Wesentlichen nur aus solchen Prozeduraufrufen besteht. In der Definition von Péter wird ja nur a(0m) direkt berechnet. Die Schwierigkeit, bei der Berechnung der Funktionswerte, sind also nicht allein deren Größe, sondern die tiefe Verschachtelung der Funktionsaufrufe, die leicht zu einem Stack Overflow führt, also dazu, dass dem System der Speicher ausgeht. Diese Idee geht zurück auf Yngve Sundblad, der 1971 die Funktion f(n):=a(3n) benutzte, um diverse Programmiersprachen zu vergleichen. Um a(3n) zu berechnen, werden a(3n)+12^n-2 Aufrufe getätigt. Sundblad testete unter anderem, wie groß n gewählt werden kann, damit der Computer noch in der Lage ist, diese Zahl zu berechnen. Damals erreichte er n=1. Zum Vergleich hierzu: Mit Java 1.4.2, mit den Standardspeichereinstellungen, erreicht man heutzutage n=13. Im Laufe der Berechnung werden viele identische Aufrufe mehrfach ausgerechnet. Ein intelligenter Compiler kann dies ausnutzen und die Ergebnisse zwischenspeichern, um solche Aufrufe nur einmal durchführen zu müssen. Damit waren schon 1971 Aufrufe bis n=20 durchführbar. Einen bedeutenden Zeitvorteil erhält man auch, wenn man a(1,n) direkt berechnet, statt es rekursiv zu a(1a(1a(1\dots a(10)\dots))) zu expandieren. Die direkte Berechnung von a(1n) erfordert lineare Zeit in n. Die Berechnung von a(2n) erfordert quadratische Zeit, denn sie führt zu O(n) (also c\cdot n für eine Konstante c) verschachtelten Aufrufen von a(1i) für verschiedene i. Die Berechnung von a(3n) erfordert schließlich eine zu 4^ proportionale Zeit (O(4^); zur Erklärung der Groß-O-Notation siehe Landau-Symbole).

Laufzeitabschätzungen mit der Umkehrfunktion

Da die Funktion f(n): = a(nn) sehr schnell wächst, wächst ihre Umkehrfunktion f^ sehr langsam. Sie ist für jede praktisch vorstellbare Eingabegröße kleiner als 5, weil der Funktionswert f(4)=a(44) größer als die Anzahl der Atome im Universum ist, wie die Berechnung von a(43) weiter unten zeigt. In der praktischen Analyse von Algorithmen kann sie also als konstant betrachtet werden. Diese Umkehrfunktion taucht in der Laufzeitanalyse bestimmter Algorithmen auf, zum Beispiel beim Union-Find-Problem und in Chazelles Algorithmus für minimale Spannbäume. In diesem und anderen Zusammenhängen wird die ursprüngliche Ackermannfunktion oft durch Weglassen additiver Konstanten, oder anderer Modifikationen, leicht umdefiniert zu einer Funktion mit ähnlichem asymptotischen Verhalten. Diese modifizierten Funktionen sind nicht äquivalent zur Ackermannfunktion, aber nach den Maßstäben der Laufzeitanalyse können sie als äquivalent betrachtet werden.

Implementierung

Die rekursive Implementierung der Ackermannfunktion (hier im Pseudo-Code) entspricht direkt der Definition: function ack(m, n) if m = 0 return n + 1 else if n = 0 return ack(m - 1, 1) else return ack(m - 1, ack(m, n - 1)) Etwas effizienter ist die folgende, teilweise iterative Implementierung: function ack(m, n) while m ≠ 0 if n = 0 n := 1 else n := ack(m, n - 1) m := m - 1 return n + 1 Noch effizientere Implementierungen verwenden Arrays zur Zwischenspeicherung bereits berechneter Werte, siehe auch Dynamische Programmierung.

Wertetabelle

Die folgende Tabelle zeigt einige Funktionswerte für kleine Werte von n und m. Die nicht vollständig ausgerechneten Werte sind zu groß, um sie dezimal darzustellen. ¹eine Zahl mit 19729 Dezimalstellen Trotz der unvorstellbar großen Zahlen, die schon in dieser Tabelle auftauchen, wurden rekursive Verfahren definiert, die noch schneller wachsende Werte liefern, so zum Beispiel Grahams Zahl.

Genauere Betrachtung

Anhand der Wertetabelle lässt sich ein Schema zur Berechnung der Funktionswerte herleiten, das leichter zu verstehen ist als die formale rekursive Definition. Intuitiv ist die erste Zeile der Wertetabelle (genauer: die Werte von a(0y)) einfach eine Liste aller natürlichen Zahlen, und die auf das Argument y angewandte mathematische Operation ist die Addition einer 1 zu y. Alle folgenden Zeilen enthalten einfach Anweisungen, in dieser Zeile einen Wert zu suchen. Im Falle der Zeile x=1 vereinfacht sich diese Anweisung dazu, den Wert a(0y+1) in der Zeile x=0 zu suchen, aber diese Vereinfachung ist schon etwas schwieriger herzuleiten – zum Beispiel: a(1, 2) = a(0, a(1,1)) = a(0, a(0, a(1,0))) = a(0, a(0, 2)) = a(0, 3) = 4 Wir betrachten nun einen komplexeren Fall, nämlich a(43), den ersten Funktionswert, der so groß ist, dass er praktisch nicht dezimal aufgeschrieben werden kann. a(4, 3) = a(3, a(4, 2)) = a(3, a(3, a(4, 1))) = a(3, a(3, a(3, a(4, 0)))) = a(3, a(3, a(3, a(3, 1)))) = a(3, a(3, a(3, a(2, a(3, 0))))) = a(3, a(3, a(3, a(2, a(2, 1))))) = a(3, a(3, a(3, a(2, a(1, a(2, 0)))))) = a(3, a(3, a(3, a(2, a(1, a(1, 1)))))) = a(3, a(3, a(3, a(2, a(1, a(0, a(1, 0))))))) = a(3, a(3, a(3, a(2, a(1, a(0, a(0, 1))))))) = a(3, a(3, a(3, a(2, a(1, a(0, 2)))))) = a(3, a(3, a(3, a(2, a(1, 3))))) = a(3, a(3, a(3, a(2, a(0, a(1, 2)))))) = a(3, a(3, a(3, a(2, a(0, a(0, a(1, 1))))))) = a(3, a(3, a(3, a(2, a(0, a(0, a(0, a(1, 0)))))))) = a(3, a(3, a(3, a(2, a(0, a(0, a(0, a(0, 1)))))))) = a(3, a(3, a(3, a(2, a(0, a(0, a(0, 2)))))) = a(3, a(3, a(3, a(2, a(0, a(0, 3))))) = a(3, a(3, a(3, a(2, a(0, 4))))) = a(3, a(3, a(3, a(2, 5)))) = ... Das ist für einige Zeit der einfachste Fall einer solchen Expansion, und es ist an Hand der Tabelle offensichtlich, warum Funktionswerte wie dieser selten direkt berechnet werden. Es ist auch interessant festzustellen, wie viele Schritte nötig sind, um schon sehr einfach aussehende Ackermann-Ausdrücke zu vereinfachen. Jede Zeile im vorigen Beispiel ist eine einzige Anwendung eines der drei Teile der Definition der Ackermannfunktion. ... = a(3, a(3, a(3, 13))) = ... = a(3, a(3, 65533)) Wenn wir an dieser Stelle mehrere logische Schritte überspringen, könnten wir a(25) zu 13 auswerten, und dann versuchen, a(313) auszuwerten – das ist 65533. Der nächste Funktionsaufruf, a(365533), liefert eine Zahl, die der Zahl der Atome im Universum entspricht, einige Dutzend mal mit sich selbst multipliziert. Diese Zahl n wird schließlich in die Berechnung a(3n) eingesetzt, die irgendwann zu einem Ausdruck der Form a(2a(2a(2\dots a(20)\dots))) ausgeschrieben würde, die aber mit unseren Mitteln nicht mehr aufgeschrieben werden kann. Der wirklich faszinierende Aspekt der Ackermann-Funktion ist, dass die einzige Berechnung, die neben den rekursiven Aufrufen tatsächlich auftaucht, die Berechnung von a(0n) ist, die einfach n um 1 erhöht.

Sonstiges

Funktionswert a(4,2)

Des Öfteren wird vor allem im Internet der Funktionswert a(4,2) in Form einer 19727-stelligen Dezimalzahl angegeben. Dieser kann wahrscheinlich noch nicht mit Hilfe der rekursiven Definition der Ackermannfunktion praktisch berechnet werden, weil zum Abspeichern der Zwischenergebnisse bei weitem zu viel Speicherplatz benötigt werden würde.

Die Funktion Fleißiger Biber

1962 gab Tibor Radó mit der Funktion Fleißiger Biber (busy beaver) eine noch stärker wachsende Funktion als die Ackermannfunktion an, die allerdings nicht mehr berechenbar ist.

Literatur


- Wilhelm Ackermann: Zum Hilbertschen Aufbau der reellen Zahlen, Math. Annalen 99 (1928), 118-133
- Yngve Sundblad: The Ackermann Function. A Theoretical, Computational, and Formula Manipulative Study. BIT 11 (1971), 107-119
- Uwe Schöning: Theoretische Informatik – kurzgefasst; Spektrum Akademischer Verlag, ISBN 3-8274-1099-1
- Dexter C. Kozen: The Design and Analysis of Algorithms; Springer 1992

Weblinks


- [http://www.informatik.uni-freiburg.de/~zeisberg/ackermann/ Einige Werte der Ackermannfunktion] (Die Angaben für die Anzahl der Iterationen sind allerdings Unsinn)
- [http://www.xgc.com/benchmarks/benchmarks.htm Beispielanwendung der Ackermannfunktion als Benchmark]. Beachten Sie die große Zahl der Funktionsaufrufe schon bei der Berechnung kleiner Werte (Englisch)
- [http://www.kosara.net/thoughts/ackermann42.html Dezimaler Wert von ack(4,2)]
- [http://shootout.alioth.debian.org/benchmark.php?test=ackermann Benchmarks von verschiedenen Computersprachen mit der Ackermannfunktion] Kategorie:Theoretische Informatik ja:アッカーマン関数

Partielle Funktion

Eine partielle Funktion von der Menge X in die Menge Y ist eine Relation, in der jedes Element in der Menge X mit höchstens einem Element in der Menge Y in Relation steht. Das bedeutet, dass man eine partielle Funktion damit als eine "Funktion" von einer Teilmenge von X nach Y auffassen kann. Die Bezeichnung partielle Funktion ist leicht irreführend, da eine partielle Funktion keine Funktion im Sinne der Mathematik ist. Der Begriff hat sich jedoch in der Informatik und verwandten Gebieten eingebürgert. Anders formuliert ist eine partielle Funktion an einigen Stellen bewusst undefiniert, in vielen Anwendungen sind dies endlich viele Stellen oder zumindest auf die Definitionsmenge eine Nullmenge. Eine partielle Funktion lässt sich zu einer echten mathematischen Funktion machen, indem man die Definitionsmenge auf die Menge der Elemente in X einschränkt, die einem Y-Wert zugeordnet werden.

Beispiele


- Die Funktion f: \mathbb \to \mathbb, \quad f(x) := \frac ist an der Stelle x = 0 undefiniert, weil die Division durch 0 undefiniert ist.
- partiell rekursive Funktionen
- ein unbeschränkter linearer Operator

Bemerkungen

Man schreibt die Definition partieller Funktionen in der theoretischen Informatik oft als f : \subseteq A \to B. Ist f an einer Stelle x undefiniert, so schreibt man zuweilen kurz f(x) = \mbox. Eine Registermaschine, deren Maschinenfunktion f ist, terminiert für ein solches Argument x nicht, z.B. weil sie eine Endlosschleife durchläuft. Siehe auch: totale Funktion Kategorie:Theoretische Informatik

Algorithmus

Unter einem Algorithmus versteht man allgemein eine genau definierte Handlungsvorschrift zur Lösung eines Problems oder einer bestimmten Art von Problemen. Im täglichen Leben lassen sich leicht Beispiele für Algorithmen finden: Zum Beispiel ist ein Kochrezept ein Algorithmus – zumindest dann, wenn alle Angaben genau genug sind und es für alle Teilaufgaben, wie Braten, Rühren, etc., ebenfalls Algorithmen gibt. Auch Reparatur- und Bedienungsanleitungen oder Hilfen zum Ausfüllen von Formularen sind in der Regel Algorithmen. Ein weiteres, etwas präziseres Beispiel sind Waschmaschinenprogramme. Algorithmen können in Programmablaufplänen nach DIN 66001 oder ISO 5807 grafisch gezeichnet werden.

Geschichte

Das Wort Algorithmus ist eine Abwandlung oder Verballhornung des Namens von Muhammad ibn Musa al-Chwarizmi (
- ca. 783, † ca. 850), dem Autor des Buchs Hisab al-dschabr wa-l-muqabala (825, Regeln zur Wiederherstellung und Reduktion), durch das die Algebra im Westen verbreitet wurde. Die lateinische Fassung beginnt mit „Dixit Algorithmi...“ (Algorithmus sprach...), womit der Autor gemeint war. Das Wort Algebra stammt ebenfalls (al-Jabr – „Einrenkung“) aus dem Titel des Buches. Ursprünglich stand das Wort Algorism nur für die Regeln zur Arithmetik mit arabischen Ziffern. Heute steht es für alle geregelten Prozeduren, mit denen Probleme aller Art gelöst werden können.

Informatik und Mathematik

Vor allem aber sind Algorithmen eines der zentralen Themen der Informatik und Mathematik. Sie sind Gegenstand einiger Spezialgebiete der Theoretischen Informatik, wie der Algorithmentheorie, der Komplexitätstheorie und der Berechenbarkeitstheorie. In Form von Computerprogrammen und elektronischen Schaltkreisen steuern sie Computer und andere Maschinen.

Algorithmus und Programm

Für Algorithmen gibt es unterschiedliche formale Repräsentationen. Diese reichen vom Algorithmus als abstraktes Gegenstück zum konkret auf eine Maschine zugeschnittenen Programm (d. h., die Abstraktion erfolgt hier im Weglassen der Details der realen Maschine, das Programm ist eine konkrete Form des Algorithmus, angepasst an die Notwendigkeiten und Möglichkeiten der realen Maschine) bis zur Ansicht, Algorithmen seien gerade die Maschinenprogramme von Turingmaschinen (wobei hier die Abstraktion in der Verwendung der Turingmaschine an sich erfolgt, d. h., einer idealen mathematischen Maschine).

Erster Computeralgorithmus

Der erste für einen Computer gedachte Algorithmus wurde 1842 von Ada Lovelace, in ihren Notizen zu Charles Babbages Analytical Engine, festgehalten. Sie gilt deshalb als die erste Programmiererin. Weil Charles Babbage seine Analytical Engine nicht vollenden konnte, wurde Ada Lovelaces Algorithmus nie darauf implementiert.

Formale Definition

Die mangelnde mathematische Genauigkeit des Begriffs Algorithmus störte viele Mathematiker und Logiker des 19. und 20. Jahrhunderts. Insbesondere steht die natürliche Sprache mit ihren Unschärfen und Widersprüchlichkeiten der Forderung nach Eindeutigkeit und Widerspruchsfreiheit im Wege.

Turingmaschinen und Algorithmusbegriff

In der ersten Hälfte des 20. Jahrhunderts wurden eine ganze Reihe von Ansätzen entwickelt, um zu einer genauen Definition zu kommen. Formalisierungen des Berechenbarkeitsbegriffs sind die Turing-Maschine (Alan Turing), der Lambda-Kalkül (Alonzo Church), rekursive Funktionen, Chomsky-Grammatiken und Markow-Algorithmen. Es wurde – unter maßgeblicher Beteiligung von Alan Turing selbst – gezeigt, dass all diese Methoden ebenso leistungsfähig (gleich mächtig) sind. Sie können durch eine Turing-Maschine emuliert werden, und sie können umgekehrt eine Turing-Maschine emulieren. Mit Hilfe des Begriffs der Turing-Maschine kann folgende formale Definition des Begriffs formuliert werden: Eine Berechnungsvorschrift zur Lösung eines Problems heißt genau dann Algorithmus, wenn eine zu dieser Berechnungsvorschrift äquivalente Turingmaschine existiert, die für jede Eingabe, die eine Lösung besitzt, stoppt. Aus dieser Definition sind folgende Eigenschaften eines Algorithmus ableitbar: # Das Verfahren muss in einem endlichen Text eindeutig beschreibbar sein (Finitheit). # Jeder Schritt des Verfahrens muss auch tatsächlich ausführbar sein (Ausführbarkeit). # Das Verfahren darf zu jedem Zeitpunkt nur endlich viel Speicherplatz benötigen (Dynamische Finitheit, siehe Platzkomplexität). # Das Verfahren darf nur endlich viele Schritte benötigen (Terminierung, siehe auch Zeitkomplexität). Darüber hinaus wird der Begriff Algorithmus in praktischen Bereichen oft auf die folgenden Eigenschaften eingeschränkt: # Der Algorithmus muss bei denselben Voraussetzungen das gleiche Ergebnis liefern (Determiniertheit). # Die nächste anzuwendende Regel im Verfahren ist zu jedem Zeitpunkt eindeutig definiert (Determinismus).

Church-Turing-These

Die Church-Turing-These lautet: „Jedes intuitiv berechenbare Problem kann durch eine Turingmaschine gelöst werden.“ Als formales Kriterium für einen Algorithmus zieht man die Implementierbarkeit in einem beliebigen zu einer Turing-Maschine äquivalenten Formalismus heran, insbesondere die Implementierbarkeit in einer Programmiersprache – die von Church verlangte Terminiertheit ist dadurch allerdings noch nicht gegeben. Der Begriff der Berechenbarkeit ist dadurch dann so definiert, dass ein Problem genau dann berechenbar ist, wenn es einen (terminierenden) Algorithmus zu dem Problem gibt, d. h. wenn eine entsprechend programmierte Turing-Maschine das Problem in endlicher Zeit lösen könnte.

Abstract State Machines

Turingmaschinen harmonieren sehr gut mit den ebenfalls abstrakt-mathematischen berechenbaren Funktionen, reale Probleme sind jedoch ungleich komplexer, daher wurden andere Maschinen vorgeschlagen. Diese Maschinen weichen z. B. in der Mächtigkeit der Befehle ab; anstatt den einfachen Operationen der Turingmaschine können sie z. T. sehr mächtige Operationen, wie z. B. Fouriertransformationen, in einem Rechenschritt ausführen. Oder sie beschränken sich nicht auf eine Operation pro Rechenschritt, sondern ermöglichen sehr parallele Operationen, wie z. B. die Addition zweier Vektoren in einem Schritt. Ein Modell einer realeren Maschine ist die [http://www.eecs.umich.edu/gasm/papers/seqthesis.html Sequential Abstract State Machine (seq. ASM)] mit folgenden Eigenschaften: Ein Algorithmus einer seq. ASM soll
- durch einen endlichen Programmtext spezifiziert werden können
- schrittweise ausgeführt werden können
- für bestimmte Zustände terminieren, muss aber nicht immer terminieren (sinnvolle Gegenbeispiele für die Forderung, dass immer terminiert werden muss, wären z.B. ein Programm das fortgesetzt Primzahlen findet, oder ein Betriebssystem)
- nur begrenzt viele Zustände pro Schritt ändern können (Begrenzung der Parallelität)
- nur begrenzt viele Zustände pro Schritt inspizieren können (Begrenzung der Exploration)

Ein Beispiel: der Euklidische Algorithmus

Der Euklidische Algorithmus, der bereits um 300 v. Chr. beschrieben wurde, dient zur Ermittlung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen A und B: # Sei A die Größere der beiden Zahlen A und B (entsprechend vertauschen, falls dies nicht bereits so ist) # Setze A = A – B # Wenn A und B ungleich sind, dann fahre fort mit Schritt 1, wenn sie gleich sind, dann beende den Algorithmus: Diese Zahl ist der größte gemeinsame Teiler. Beispiel: Es soll der größte gemeinsame Teiler der Zahlen 14 und 8 berechnet werden. Hierzu wird der euklidische Algorithmus verwendet: Das Ergebnis ist also 2.

Eigenschaften

Nichtdeterministische Algorithmen finden vor allem in der Theoretischen Informatik Anwendung, so dass in anderen Bereichen oft vorausgesetzt wird, dass es sich um einen deterministischen Algorithmus handelt. Eine Ausnahme bilden so genannte stochastische, randomisierte oder probabilistische Algorithmen, in die absichtlich ein Zufallsfaktor eingebaut wurde. Solche Algorithmen sind demnach nicht deterministisch und auch nicht determiniert. Stochastische Algorithmen dagegen sind im Allgemeinen deterministisch, orientieren sich aber an Erfahrungswerten. Die verschiedenen formalen Eigenschaften in Kürze:

Determiniertheit

Kurz: Bei jeder Ausführung mit gleichen Startwerten muss das gleiche Ergebnis berechnet werden. Algorithmen sind determiniert, wenn sie bei gleichen Parametern und Startwert stets das gleiche Resultat liefern. Das trifft zum Beispiel nicht für randomisierte Algorithmen zu, bei denen das Ergebnis zu einem gewissen Grad auf Zufall beruht.

Determinismus

Kurz: Es darf immer nur eine Möglichkeit vorhanden sein Deterministisch heißen alle Algorithmen, bei denen zu jedem Zeitpunkt der Ausführung maximal eine Möglichkeit der Programmfortsetzung besteht. Gibt es mehrere Möglichkeiten der Programmfortsetzung und lassen sich diesen Wahrscheinlichkeiten zuweisen, so spricht man von stochastischen, randomisierten oder probabilistischen Algorithmen. In der theoretischen Informatik gibt es neben dem Determinismus auch den Nichtdeterminismus, der aber in der Praxis kaum Verwendung findet. Zusätzliche Bedeutung bekommen solche nichtdeterministische Algorithmen allerdings durch den Einsatz von Quantencomputern, welche auch solche Algorithmen erfolgreich ausführen. Es gilt übrigens: Jeder deterministische Algorithmus ist auch determiniert. Nicht jeder determinierte Algorithmus ist jedoch deterministisch.

Finitheit

Statische Finitheit

Kurz: Die Beschreibung ist endlich. Die Beschreibung eines Algorithmus darf nicht unendlich groß sein. Als statische Finitheit wird die Endlichkeit des Quelltextes bezeichnet. Der Quelltext darf nur eine begrenzte Anzahl, wenn auch bei Bedarf sehr viele Regeln enthalten.

Dynamische Finitheit

Kurz: Fülle an Datenstrukturen und Zwischenspeicherungen sind zu jeder Zeit endlich. Zu jedem Zeitpunkt der Ausführung darf der von einem Algorithmus benötigte Speicherbedarf nicht unendlich groß sein. Andernfalls wäre der Algorithmus nicht ausführbar. Dies wird als dynamische Finitheit bezeichnet.

Terminiertheit

Kurz: Bricht nach endlicher Zeit kontrolliert ab. Algorithmen sind terminierend, wenn sie für jede mögliche Eingabe nach einer endlichen Zahl von Schritten zu einem Ergebnis kommen. Die tatsächliche Zahl der Schritte kann dabei beliebig groß sein. Steuerungssysteme und Betriebssysteme und auch viele Programme, die auf Interaktion mit dem Benutzer aufbauen, erfüllen diese Eigenschaft nicht: Wenn der Benutzer keinen Befehl zum Beenden gibt, läuft das Programm endlos weiter. Donald Knuth schlägt in diesem Zusammenhang vor, nicht terminierende Algorithmen als rechnergestützte Methoden ("Computational Methods") zu bezeichnen. Es ist übrigens im Allgemeinen nicht für jeden beliebigen Algorithmus möglich zu bestimmen, ob er terminiert oder nicht - siehe Halteproblem.

Algorithmenanalyse

Die Erforschung und Analyse von Algorithmen ist Hauptaufgabe der Informatik, und wird meist theoretisch (ohne konkrete Umsetzung in eine Programmiersprache) durchgeführt. Sie ähnelt somit dem Vorgehen in anderen mathematischen Gebieten, in denen die Analyse eher auf die zugrunde liegenden Konzepte als auf konkrete Umsetzungen ausgerichtet ist. Algorithmen werden zur Analyse in eine stark formalisierte Form gebracht und mit den Mitteln der formalen Semantik untersucht. Die Analyse unterteilt sich in verschiedene Teilgebiete. Beispielsweise wird das Verhalten von Algorithmen bezüglich Ressourcenbedarf wie Rechenzeit und Speicherbedarf in der Komplexitätstheorie behandelt, die Ergebnisse werden als asymptotische Laufzeiten angegeben. Der Ressourcenbedarf wird dabei in Abhängigkeit von der Länge der Eingabe ermittelt, d. h. die angegebene Komplexität hängt davon ab, wie groß die Zahlen sind, deren größter gemeinsamer Teiler gesucht wird, oder wie viele Elemente sortiert werden müssen etc. Das Verhalten bezüglich der Terminierung, d. h. ob der Algorithmus überhaupt jemals erfolgreich beendet werden kann, behandelt die Berechenbarkeitstheorie.

Beispiele

Algorithmen in der Wikipedia

In einzelnen Wikipedia-Artikeln gibt es zahlreiche Algorithmen-Beschreibungen, etwa den euklidischen Algorithmus und Quicksort. Eine Übersicht gibt die Liste von Algorithmen und die Kategorie Algorithmus.

Algorithmen im Alltag

Auch im Alltag begegnen uns Algorithmen in Form von Handlungsanweisungen oder Rezepten:

Siehe auch


- Liste von Algorithmen
- Ameisenalgorithmus
- Approximationsalgorithmus
- Datenstruktur
- Determinierter Algorithmus
- Deterministischer Algorithmus
- Entscheidungsproblem
- Evolutionärer Algorithmus
- Greedy Algorithmus
- Heuristik
- Komplexitätsklassen
- MMIX (virtuelle Maschine von Donald E. Knuth zur Darstellung von Algorithmen)
- Online-Algorithmus
- Optimierungsproblem
- Paralleler Algorithmus
- Probabilistischer Algorithmus
- Prozedur (Programmierung)
- Randomisierter Algorithmus
- Sortierverfahren
- Stochastischer Algorithmus
- Suchverfahren

Literatur


- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson Studium. 2002. ISBN 3-8273-7020-5.
- Donald E. Knuth: The Art of Computer Programming, Vol 1–3, Addison Wesley 1998. (Das ist der Standard in dem Bereich; Übersetzung existiert nicht – Juli 2000), ISBN 0201485419
- Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms, MIT Press, 2nd edition 2001, ISBN 0262531968
- Deutsche Übersetzung: Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - Eine Einführung, Oldenbourg Wissenschaftsverlag, 2004, ISBN 3-486-27515-1

Weblinks


- [http://www.grundstudium.info/algorithmen/ Algorithmen in der Informatik]
- [http://www.uni-flensburg.de/mathe/zero/veranst/algorithmen/algo_abschn11/algo_abschn11.html Was ist ein Algorithmus?]
- [http://www.nist.gov/dads/ Dictionary of Algorithms and Data Structures] des NIST (englisch)
- [http://www.bullhost.de/a/algorithmus.html Definition] Kategorie:Datenstruktur ja:アルゴリズム ko:알고리즘 th:อัลกอริทึม

Registermaschine (Berechenbarkeitstheorie)

Dieser Artikel befasst sich mit jener Registermaschine aus dem Bereich der Berechenbarkeitstheorie. Weiteres siehe: Registermaschine ---- Die Registermaschine (auch RAM für engl. random access machine) ist ein Rechnermodell der theoretischen Informatik, das einem realen Rechner (PC) sehr ähnlich ist. Eine Registermaschine kann alles, was auch ein realer Rechner kann. Da man auch beweisen kann, daß sich die Registermaschine und die Turingmaschine gegenseitig mit polynomieller Laufzeit simulieren können, gelten Aussagen, die man für die Turingmaschine beweisen kann, auch für die Registermaschine und damit auch für reale Rechner. Dies ist in der theoretischen Informatik von Vorteil, da man viele Aussagen an Hand der Turingmaschine leichter beweisen kann. Die hier vorgestellte Registermaschine stammt aus dem Bereich der Berechenbarkeitstheorie. Dies wird im weiteren Text nicht mehr erwähnt.

Definition

Eine Registermaschine arbeitet mit natürlichen Zahlen. Alle ab jetzt vorkommenden Zahlen sollten in diesem Kontext betrachtet werden. Eine Registermaschine besteht aus
- einem Befehlszeiger b
- einem Input-Wert m
- einem Output-Wert n
- und aus einem unendlich großen Speicher aus durchnummerierten Speicherzellen (Register) r(1), r(2), r(3), ... Weiterhin gibt es ein Registermaschinenprogramm, das aus einer Menge von Befehlen mit jeweils eindeutiger Nummer und einer Startmarke besteht. Ein Befehl kann folgendermaßen aussehen (i > 0): Zum Starten des Programmes sollte zusätzlich ein Eingebedatensatz bestehend aus m geordneten Werten vorhanden sein. Zu Beginn wird der Befehlszeiger b auf den Wert der Startmarke des Programmes gesetzt. Die Speicherzellen von Nummer 1 bis m werden auf die entsprechenden Werte des Eingabedatensatzes gesetzt. Die restlichen Speicherzellen erhalten den Wert 0. Die Registermaschine führt dann nacheinander die Befehle des Programms aus. Es wird immer der Befehl mit der Nummer b ausgeführt. Die Ausführung eines nichtexistenten Befehls terminiert das Programm. Nach der Terminierung werden alle Werte von r(1) bis r(n) ausgegeben. Registermaschinen lassen sich wie alle Maschinen anschaulich besonders gut durch Flussdiagramme darstellen.

Weblinks


- http://www.logic.at/lvas/185845/#UEsim Eine Sammlung von Registermaschinensimulatoren
- http://stud4.tuwien.ac.at/~e0125844/RegisterMachineGerman.html Ein etwas neuerer Registermaschinesimulator Kategorie: Theoretische Informatik

Maschinenfunktion

Eine Maschinenfunktion ist eine Funktion (das Turingprogramm einer Turingmaschine ist die Maschinenfunktion), die eine endliche Maschine in endliche vielen Schritten in einen Endzustand überführt. Beispiel: Ein Fahrkartenautomat, mit Münzeinwurf für 50 Cent, 1€ und 2€, der bei 2,50€ ein Fahrkarte herausgibt. Kategorie:Automatentheorie Kategorie:Theoretische Informatik

Primitive Rekursion

Primitiv-rekursive Funktionen sind Funktionen, die auf bestimmte Art aus einfachen Grundoperationen zusammengesetzt werden können. Der Begriff primitiv-rekursive Funktion wurde von der ungarischen Mathematikerin Rózsa Péter geprägt. Primitiv-rekursive Funktionen spielen in der Theoretischen Informatik eine Rolle, insbesondere in Zusammenhang mit Berechenbarkeit.

Eigenschaften

Primitiv-rekursive Funktionen zeichnen sich durch eine gewisse Gutartigkeit aus. Insbesondere kann man vor der Berechnung eines Funktionswertes angeben, wie komplex diese Operation ist, d.h. auch wie lange diese Berechnung dauern wird. Lange Zeit hoffte man, dass sich jede mathematische Funktion und jedes Problem primitiv-rekursiv berechnen lässt. Diese Hoffnung wurde durch die Ackermannfunktion zerstört, die erste bekannte Funktion, die nicht primitiv-rekursiv berechenbar war. Die Klasse Pr der primitiv-rekursiven Funktionen (von \mathbb^k \rightarrow \mathbb) umfasst zunächst die folgenden primitiv-rekursiven Grundfunktionen: #konstante Funktion: f_c^k \left( n_1, ..., n_k \right) := c, c \in \mathbb #Projektion auf ein Argument: \pi_i^k \left( n_1, ..., n_k \right) := n_i, 1 \le i \le k #Nachfolgefunktion: \nu \left( n \right) := n + 1 (auch Sukzessorfunktion genannt) Aus diesen werden mit folgenden Operationen alle weiteren primitiv-rekursiven Funktionen gewonnen: #Komposition: f \left( n_1, ..., n_k \right) := g \left( h_1 \left( n_1, ..., n_k \right), ..., h_m \left( n_1, ..., n_k \right) \right) falls g, h_1, ..., h_m \in Pr #Primitive Rekursion: f \left( 0, n_2, ..., n_k \right) := g \left( n_2, ..., n_k \right), f \left( n_1 + 1, n_2, ..., n_k \right) := h \left( f \left( n_1, ..., n_k \right), n_1, ..., n_k \right), falls h, g \in Pr Jede primitiv-rekursive Funktion ist LOOP-berechenbar (vgl. LOOP-Programm) und umgekehrt.

Beispiele

Es folgen einige Beispiele, wie sich bekannte Operationen als primitiv-rekursive Funktionen definieren lassen.

Vorgängerfunktion

Die Vorgängerfunktion p(x) = x - 1 ergibt sich durch primitive Rekursion. Als Funktion g verwendet man die Nullfunktion und als Funktion f die Projektion. Es ergibt sich dadurch: p(0) = g() = 0 p(n+1) = h(p(n),n) = \pi_2^2(p(n),n) = n

Addition

Die Addition \mbox \left(a,b \right)=a+b der Natürlichen Zahlen lässt sich wie folgt definieren: \mbox(0,b):=\pi_1^1(b)=b (Projektion) \mbox(n+1,b):=\nu \left(\mbox(n,b),n,b \right) (Primitive Rekursion) Um aus der Addition eine Subtraktion zu machen ersetzt man die Nachfolgerfunktion \nu durch die Vorgängerfunktion p.

Multiplikation

Zur Definition der Multiplikation \mbox(a,b)=a\cdot b dürfen wir die Addition schon verwenden, da diese ja, wie gerade gezeigt, primitiv-rekursiv ist: \mbox(0,b):= f_0^1(b)=0 (konstante Funktion) \mbox(n+1,b):= \mbox\left(\mbox(n,b),n,b \right)=\mbox(n,b)+b (Primitive Rekursion)

Potenzieren

Zur Definition des Potenzierens \mbox(a,b)=a^b dürfen wir die Addition und Multiplikation schon verwenden, da diese ja, wie gerade gezeigt, primitiv-rekursiv sind: \mbox(a,0):= v(0)=1 (konstante Funktion) \mbox(a,v(b)):= \mbox\left(\mbox(a,b),a,b \right)= (Primitive Rekursion) Siehe auch: µ-Rekursion Kategorie:Theoretische Informatik

Μ-Rekursion

μ-rekursive Funktionen spielen in der theoretischen Informatik eine Rolle, insbesondere in Zusammenhang mit Berechenbarkeit. Sie stellt eine Erweiterung der primitiv-rekursiven Funktionen dar. Im Gegensatz zu den primitiv-rekursiven Funktionen können mit μ-rekursiven Funktionen insbesondere auch Funktionen dargestellt werden, die nicht total, sondern partiell sind. Daher werden die μ-rekursiven Funktionen oft auch partiell-rekursive Funktionen genannt. Es gibt in der Klasse der μ-rekursiven Funktionen aber auch Funktionen, die total und nicht primitiv-rekursiv sind. Ein berühmtes Beispiel dafür ist die Ackermann-Funktion.

Eigenschaften

Die Klasse R der μ-rekursiven Funktionen (von \mathbb^k \rightarrow \mathbb) umfasst: # alle konstanten Funktionen: f_c^k \left( n_1, ..., n_k \right) := c, c \in \mathbb # alle Projektionen: \pi_i^k \left( n_1, ..., n_k \right) := n_i, 1 \le i \le k # die Nachfolgefunktion: \nu \left( n \right) := n + 1 und ist abgeschlossen gegenüber: # der Komposition: f \left( n_1, ..., n_k \right) := g \left( h_1 \left( n_1, ..., n_k \right), ..., h_m \left( n_1, ..., n_k \right) \right), falls g, h_1, ..., h_m \in Pr # Primitiver Rekursion: f \left( 0, n_2, ..., n_k \right) := g \left( n_2, ..., n_k \right), f \left( n_1 + 1, n_2, ..., n_k \right) := h \left( f \left( n_1, ..., n_k \right), n_1, ..., n_k \right), falls h, g \in Pr # Anwendung des μ-Operators

Definition des μ-Operators

Für eine Funktion f:\mathbb^ \rightarrow \mathbb ist die Funktion \mu f : \mathbb^k \rightarrow \mathbb definiert durch: \mu f(x) = \begin \min \ & \mbox \\ \mbox & \mbox\\ \end μ nennt man μ-Operator. Jede μ-rekursive Funktion entspricht einer WHILE-Schleife (vgl. WHILE-Programm) und umgekehrt. Einfach gehalten heisst das, dass μf(x) das kleinste y mit f(x,y) = 0 und für alle y' < y f(x,y') definiert ist. μ-Rekursion

Rationale Zahl

Eine rationale Zahl ist eine Zahl, die als Verhältnis (lateinisch Ratio) zweier ganzer Zahlen ausgedrückt werden kann (für gewöhnlich schreibt man a / b, lies a geteilt durch b), wobei der Nenner (hier b) ungleich Null ist. Jede Zahl, die sich als Bruch zweier ganzer Zahlen darstellen lässt, ist also eine rationale Zahl.

Definition

Eine reelle Zahl x heißt dann rational, wenn man sie als Quotient (oder Bruch) p/q zweier ganzer Zahlen mit q\neq 0 darstellen kann. Andernfalls heißt x irrational. Insbesondere ist jede ganze Zahl rational (wähle z.B. x/1). Bemerkenswerterweise besitzt jede rationale Zahl eine periodische Dezimalbruchentwicklung.

Zur Erklärung der rationalen Zahlen

Jede rationale Zahl lässt sich im Dezimalsystem darstellen, wobei bestimmte Zahlen eine periodische Dezimalbruch-Entwicklung haben. Im Gegensatz dazu haben alle irrationalen Zahlen (wie \sqrt 2, \sqrt 3 oder die Kreiszahl \pi) eine unendliche, nichtperiodische Ziffernfolge. Die Menge aller rationalen Zahlen wird mit \mathbb bezeichnet und bildet einen Körper (die Bezeichnung \mathbf ist auch noch gebräuchlich). siehe auch: reelle Zahlen, natürliche Zahlen, irrationale Zahlen

Darstellungsformen

Die rationalen Zahlen haben neben der Darstellung als gemeiner Bruch eine andere Darstellung, nämlich die Dezimalbruchentwicklung; z. B. ist In den eckigen Klammern sind die entsprechenden Entwicklungen im Dualsystem angegeben. Die Dezimal-, Binär- und anderen b-adischen Entwicklungen rationaler Zahlen sind stets periodisch oder endlich (d.h. periodisch mit Periode 0). Mehrstellige Perioden sind hier jeweils durch Leerzeichen abgetrennt. Die Bruchform einer rationalen Zahl kann man oft in so genannte Partialbrüche zerlegen, deren Nenner ganze Potenzen von Primzahlen sind; z. B. :5/6 = 1/2 + 1/3, 1/6 = 1/2 - 1/3, 1/72 = 1/8 - 1/9, 1/60 = -1/4 - 4/3 + 8/5. Es gibt auch Zerlegungen als so genannte ägyptische Brüche (Stammbrüche), z. B. :3/7 = 1/3 + 1/11 + 1/231, 25/31 = 1/2 + 1/4 + 1/18 + 1/1116, die alten Ägypter kannten nur solche Summen und haben mit diesen gerechnet. Das Zahlentripel (1/5, 24/35, 5/7) ist ein Beispiel eines pythagoräischen Bruchs (siehe auch pythagoräisches Tripel), denn :(1/5)^2 + (24/35)^2 = (5/7)^2.

Konstruktion von \mathbb aus \mathbb

Mathematisch gesehen, definiert man Brüche als geordnete Paare ganzer Zahlen (a, b), wobei wieder b ungleich Null ist - oft wird b auch einfach als (nichtnegative) natürliche Zahl definiert. Dann definiert man Addition und Multiplikation mit diesen Paaren mit Hilfe folgender Regeln: ::(a, b) + (c, d) = (a \cdot d + b \cdot c, b \cdot d) ::(a, b) \cdot (c, d) = (a \cdot c, b \cdot d) Einhergehend mit unserer Erwartung, dass 2/4 = 1/2 sein soll, führen wir eine Äquivalenzrelation \sim auf diesen Paaren mit der folgenden Regel ein: ::(a, b) \sim (c, d) genau dann wenn, a \cdot d = b \cdot c. Mit den obigen Rechenregeln bildet die Menge der Äquivalenzklassen modulo ~ einen Körper \mathbb, dessen Elemente rationale Zahlen genannt werden. Die Äquivalenzklasse von (a, b) schreibt man als a/b.

Eigenschaften

Man kann zeigen, dass \mathbb der kleinste Körper ist, der die natürlichen Zahlen \mathbb enthält. \mathbb ist der Quotientenkörper der ganzen Zahlen \mathbb. Rationale Zahlen liegen dicht auf der Zahlengerade, das heißt: Jede reelle Zahl, i.e. jeder Punkt auf der Zahlengerade, kann beliebig genau durch rationale Zahlen angenähert werden. Zwischen zwei rationalen Zahlen a und b liegt stets eine weitere rationale Zahl c (und somit beliebig viele). Man nehme einfach das arithmetische Mittel dieser beiden Zahlen: :c := (a + b) / 2 Was zunächst überraschend klingt, ist die Tatsache, dass die Menge der rationalen Zahlen gleichmächtig zu der Menge der natürlichen Zahlen ist. Das heißt: es gibt eine bijektive Abbildung zwischen \mathbb und \mathbb, die jeder rationalen Zahl q eine natürliche Zahl n zuweist und umgekehrt.

Verwandte Themen


- Cantor-Diagonalisierung
- Bewertungstheorie: p-Bewertung, p-ganze Zahl
- Ordinalzahlen
- Zahlensystem

Weblinks


- http://www.wakkanet.fi/%7Epahio/ohjelmi.html PC-Programm »Bruch«, berechnet gewöhnliche, partielle, ägyptische, pythagoräische und dyadische Brüche, Dezimal- und Binärentwicklungen; löst exakt Gleichungen zweiten Grades mit rationalen Koeffizienten; konkrete rationale cauchysche Folgen (auch auf deutsch und französisch) Kategorie:Zahlen ja:有理数 ko:유리수 simple:Rational number th:จำนวนตรรกยะ

Turingmaschine

Die Turingmaschine ist ein von dem britischen Mathematiker Alan Turing 1936 entwickeltes mathematisches Modell, um eine Klasse von berechenbaren Funktionen zu bilden. Sie wurde im Rahmen des von David Hilbert im Jahr 1920 formulierten Hilbertprogramms, speziell zur Lösung des so genannten Entscheidungsproblems, in der Schrift "On Computable Numbers, with an Application to the Entscheidungsproblem" vorgestellt. Alan Turing beabsichtigte mit der Turingmaschine ein Modell des mathematisch arbeitenden Menschen zu schaffen. Das Besondere an einer Turingmaschine ist, dass sie mit nur drei Operationen (Lesen, Schreiben und Kopf bewegen) die Probleme lösen kann, die auch von einem Computer gelöst werden könnten. Sämtliche mathematischen Grundfunktionen, wie Addition und Multiplikation lassen sich mit diesen drei Operationen simulieren. Darauf aufbauend kann man schließlich komplexere Programme simulieren. Die Church-Turing-These stellt schließlich die Behauptung auf, dass eine Turingmaschine alle von Menschen berechenbaren mathematischen Funktionen lösen kann. (Daraus darf jedoch nicht gefolgert werden, dass eine Turingmaschine alle mathematischen Funktionen lösen kann. So kann etwa an Hand des Halteproblems gezeigt werden, dass es mathematische Funktionen gibt, die nicht von Menschen (und folglich auch nicht von einer Turingmaschine) berechnet werden können.) Als Erweiterung ergibt sich: Da jeder Computer vollständig durch eine Turingmaschine simuliert werden kann, kann er alle von Menschen berechenbaren mathematischen Funktionen, jedoch nicht alle mathematischen Funktionen berechnen.

Definition

Informelle Beschreibung

Computer Die Turingmaschine besteht aus
- einem unbeschränkt langen Speicherband mit unbeschränkt vielen Feldern. In jedem dieser Felder kann genau ein Zeichen gespeichert werden. (Unbeschränkt heißt hier, das Band darf stets endlich lang sein, es ist aber für die aktuelle Rechnung ausreichend groß zu wählen.)
- einem programmgesteuerten Lese- und Schreibkopf, der sich auf dem Speicherband feldweise bewegen und die Zeichen verändern kann. Eine Turingmaschine modifiziert die Eingabe auf dem Band nach einem gegebenen Programm. Ist die Berechnung beendet, so befindet sich das Ergebnis auf dem Band. Es wird somit jedem Eingabewert ein Ausgabewert zugeordnet. Eine Turingmaschine muss aber nicht für alle Eingaben stoppen. In diesem Fall ist die Funktion für die Eingabe undefiniert. Als Ergebnis der Berechnung wird manchmal diejenige Zeichenfolge definiert, die nach dem Anhalten auf dem Band steht. Die Turingmaschine wird jedoch meistens (wie viele andere Automaten auch) für Entscheidungsprobleme eingesetzt, also für Fragen, die mit „ja“ oder „nein“ zu beantworten sind. Dabei wird das Anhalten der TM als „ja“ und das Nicht-Anhalten als „nein“ interpretiert. Zu beachten ist dabei, dass sich jedes Problem als Entscheidungsproblem formulieren lässt, indem man fragt, ob ein bestimmter Wert eine Lösung für ein konkretes Problem ist.

Formale Definition

Formal kann eine deterministische Turingmaschine als 7-Tupel M=(Q, \Sigma, \Gamma, \delta, q_0, \square, F) dargestellt werden.
- Q ist die endliche Zustandsmenge
- \Sigma \subset \Gamma ist das endliche Eingabealphabet
- \Gamma ist das endliche Bandalphabet
- \delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \ ist die Überführungsfunktion
- q_0 \in Q ist der Anfangszustand
- \square \in \Gamma \setminus \Sigma steht für das leere Feld
- F \subseteq Q ist die Menge der End- bzw. akzeptierenden Zustände Die Turingmaschine arbeitet wie folgt: In einem bestimmten (Start-)Zustand q_s liest sie ein Zeichen vom Band. In Abhängigkeit vom gelesenen Zeichen und dem Zustand, in dem sie sich gerade befindet, schreibt sie ein Zeichen auf das Band, bewegt den Schreib-/Lesekopf in die vorgegebene Richtung und ändert ihren internen Zustand. Dieser Vorgang wird durch die Überführungsfunktion realisiert. Damit hat die TM einen Takt ihres Arbeitszyklus' durchlaufen und steht für einen weiteren bereit. Erreicht die Turingmaschine einen End-Zustand, also einen Zustand der Menge F, ist die Berechnung beendet. Das Ergebnis befindet sich dann auf dem Band. Bei der nichtdeterministischen Turingmaschine ändert sich die Überführungsfunktion zu \delta : Q \times \Gamma \rightarrow \mathcal \left( Q \times \Gamma \times \ \right). Hierbei steht \mathcal wie üblich für die Potenzmenge.

Beispiel

Die folgende deterministische 1-Band-Turingmaschine M erwartet eine Folge von Einsen als Eingabe auf dem Band. Sie verdoppelt die Anzahl der Einsen wobei ein Leersymbol in der Mitte stehen bleibt. Aus "111" wird beispielsweise die Zeichenfolge "1110111". Der Schreib-/Lesekopf befindet sich initial auf der ersten Eins. Der Anfangszustand ist s1, der Endzustand s6. M = (Q, \Sigma, \Gamma, \delta, s1, 0, F)

- Q = \
- \Sigma = \
- \Gamma = \
- F = \
alter geles. schr. neuer Kopf- alter geles. schr. neuer Kopf- Zust. Symbol Symbol Zust. richtg. Zust. Symbol Symbol Zust. richtg. ------------------------------------ ------------------------------------ s1 1 -> 0 s2 R s4 1 -> 1 s4 L s1 0 -> 0 s6 0 s4 0 -> 0 s5 L s2 1 -> 1 s2 R s5 1 -> 1 s5 L s2 0 -> 0 s3 R s5 0 -> 1 s1 R s3 0 -> 1 s4 L s3 1 -> 1 s3 R M durchläuft zum Beispiel bei der Eingabe "11" folgende Zustände, wobei die aktuelle Kopfposition fett gedruckt ist: Schritt Zust. Band Schritt Zust. Band ------------------- ------------------- 1 s1 11 9 s2 1001 2 s2 01 10 s3 1001 3 s2 010 11 s3 10010 4 s3 0100 12 s4 10011 5 s4 0101 13 s4 10011 6 s5 0101 14 s5 10011 7 s5 0101 15 s1 11011 8 s1 1101 16 s6 -halt- Die Berechnung beginnt im Anfangszustand s1. Hier wird die erste Eins durch eine Null ersetzt, der Schreib-/Lesekopf bewegt sich nach rechts und neuer Zustand wird s2. Der Kopf wandert nun solange nach rechts, bis eine Null gelesen wird. Danach gelangt die Turingmaschine in den Zustand s3 und überliest alle weiteren Einsen, bis sie erneut eine Null findet. Diese wird dann durch eine Eins ersetzt. Im Zustand s4 bewegt sich der Kopf zurück, überliest wieder alle Einsen, bis er auf eine Null trifft, Zustandswechsel auf s5. Der Kopf bewegt sich nun solange nach links, bis die ursprünglich in Zustand s1 geschriebene Null gefunden wird. Diese wird wieder durch eine Eins ersetzt, der Kopf bewegt sich ein Feld nach rechts und die Turingmaschine gelangt wieder in den Zustand s1. Hier beginnt ein neuer Rechenzyklus.
Wird im Zustand s1 eine Null gelesen, so gelangt die Turingmaschine M in den Endzustand s6, woraufhin die Berechnung beendet wird.

Variationen des Turingmaschinen-Modells

In der Literatur findet man zahlreiche unterschiedliche Definitionen der Turingmaschine, die sich jeweils in einigen Details unterscheiden. So variieren etwa die Anzahl der Bänder, das verwendete Bandalphabet, die zusätzlich verwendeten Spezialzeichen und andere Eigenschaften. Die Vielfalt ist theoretisch durch die These von Church gerechtfertigt, welche im Hinblick auf die Berechenbarkeit die Äquivalenz aller universellen Maschinenmodelle postuliert. Selbst komplexitätstheoretisch sind die Unterschiede zwischen verschiedenen Definitionen weitgehend zu vernachlässigen. So lässt sich etwa jede f(n)-zeitbeschränkte k-Bandmaschine mit beliebig großem k durch eine nur O(f²(n))-zeitbeschränkte 1-Bandmaschine simulieren. Für die Simulation beliebig vieler Bänder kommt es also zu einem maximal quadratischen Mehraufwand. Insgesamt führen alle Arten von Variationen zu nicht mehr als polynomialen Aufwandsunterschieden (wobei Aufwand hier eine beliebige Ressource meint) und sind daher für viele komplexitätstheoretische Untersuchungen vernachlässigbar. Man passt in Abhängigkeit von den Zielen der jeweiligen Analyse das verwendete Modell so an, dass die Analyse möglichst einfach durchgeführt werden kann. Folgende Beispiele zeigen Anwendungen und Variationen des Turingmaschinen-Modells.

Universelle Turingmaschine

In der obigen Definition ist das Programm fest in die Maschine eingebaut und kann nicht verändert werden. Man kann aber eine universelle Turingmaschine definieren, welche die Kodierung einer Turingmaschine als Teil ihrer Eingabe nimmt, und das Verhalten der kodierten Turingmaschine auf der ebenfalls gegebenen Eingabe simuliert. Aus der Existenz einer solchen universellen Turingmaschine folgt zum Beispiel die Unentscheidbarkeit des Halteproblems. Eine ähnliche Idee, bei der das Programm als ein Teil der veränderbaren Eingabedaten betrachtet wird, liegt auch fast allen heutigen Rechnerarchitekturen zugrunde (Von-Neumann-Architektur). Formal ist eine universelle Turingmaschine eine Maschine UTM_\phi, die eine Eingabe w\|x liest. Das Wort w ist hierbei eine beliebige Beschreibung einer Maschine M_w, die zu einer bestimmten Funktion mit Eingabe x die Ausgabe berechnet. \| ist ein Trennzeichen zwischen Programmbeschreibung und Eingabe. UTM_\phi simuliert also das Verhalten von M_w mit Hilfe der Funktionsbeschreibung w und der Eingabe x. Der Index \phi in UTM_\phi zeigt an, dass es nicht nur eine einzige universelle Turingmaschine gibt. So könnten z.B. UTM_1 und UTM_2 verschiedene Wörter verstehen. Das Wort w muss dabei in einer Sprache codiert sein, die die UTM_\phi versteht.

Persistente Turingmaschine

Um interaktive Modelle (im Sinne von "Modellen mit Gedächtnis") durch eine Turingmaschine darzustellen, ist eine Erweiterung derselben um ebendieses Gedächtnis notwendig. Laut Definition ([http://www.cse.uconn.edu/~dqg/papers/its2003.ps Goldin et al., 2003: Turing Machines, Transition Systems and Interaction]) ist eine Persistente Turingmaschine (PTM) eine nichtdeterministische 3-Band-Turingmaschine mit einem Input-, einem Arbeits- und einem Output-Band. Der Input wird auf dem Arbeits-Band verarbeitet und erst nach vollständiger Bearbeitung gelangen die Ergebnisse auf dem Output-Band zurück in die "Umwelt". Danach kann ein erneuter Input aus der Umwelt verarbeitet werden. Zwischen zwei Arbeitsschritten bleiben die Inhalte des Arbeits-Bandes als "Gedächtnis" erhalten.

Ameise

Chris Langtons Ameise ist eine Turingmaschine mit zweidimensionalem Band, mit sehr einfachen Regeln und sehr verblüffenden Ergebnissen. Eine Abbildung und einen erklärenden Text findet man unter Ameise (Turingmaschine).

Fleißiger Biber

Ein beliebtes Problem ist der Fleißige Biber: Man finde die Turingmaschine, die mit einer bestimmten Anzahl von Zuständen die maximale Anzahl von "1"-Symbolen auf das Band schreibt und dann anhält.

Beziehung Turingmaschine - Formale Sprache

Akzeptierte Sprache

Eine Turingmaschine akzeptiert eine Sprache L, wenn sie bei Eingabe eines jeden Wortes x \in L nach endlich vielen Schritten in einen der definierten Endzustände übergeht. Wenn die Turingmaschine in einem anderen Zustand oder gar nicht hält, dann wird die Eingabe x von ihr nicht akzeptiert. Eine Sprache L \subseteq \Sigma^ heißt genau dann rekursiv aufzählbar, wenn es eine deterministische Turingmaschine gibt, die L akzeptiert.

Entscheidbare Sprache

Akzeptiert eine Turingmaschine eine Sprache und hält sie zusätzlich bei allen Eingaben, die nicht zu dieser Sprache gehören, so entscheidet die Turingmaschine diese Sprache. Eine Sprache L \subseteq \Sigma^ heißt genau dann rekursiv bzw. entscheidbar, wenn es eine deterministische Turingmaschine gibt, die L entscheidet.

Allgemeines

Die Menge der Turing-berechenbaren Funktionen ist die Menge aller Funktionen, die sich mit einer Turingmaschine berechnen lassen (die Turingmaschine muss die Aktion (H) ausführen!). Es gibt noch andere Verfahren, über die man Berechenbarkeit von Funktionen definieren kann, z. B. über rekursive Funktionen. Da andere Verfahren aber nachweislich dieselbe Klasse von Funktionen beschreiben wie die der Turingmaschine, liegt die Vermutung nahe, dass alle (intuitiv) berechenbaren Funktionen bereits durch das einfache Modell der Turingmaschine berechnet werden können. Dieses Ergebnis der Berechnungstheorie wird in der Churchschen These zusammengefasst.

Erweiterung

Eine Erweiterung bildet die Church-Turing-These, die besagt, dass ein Problem, das von der Turingmaschine nicht gelöst werden kann, auch von keinem Menschen gelöst werden könnte.

Siehe auch


- Von-Neumann-Maschine
- Goto-Programm
- linear beschränkte Turingmaschine (LBA)
- Nichtdeterministische Turingmaschine (NTM)
- LOOP-Programm
- WHILE-Programm
- Automatentheorie

Literatur


- Oswald Wiener, Manuel Bonik,