Informatik: Heiße AlgoRhythmen: Grenzen der Berechenbarkeit
Released by matroid on Mi. 10. Januar 2007 11:53:48 [Statistics]
Written by ehpie - 3843 x read [Outline] Printable version Printer-friendly version -  Choose language   
Informatik

\(\begingroup\)

Grenzen der Berechenbarkeit

Dem Moorschen Gesetz nach verdoppelt sich die Anzahl der Transistoren auf einem Chip alle zwei Jahre. Wenn man diesem Gesetz Glauben schenken mag, so würden unsere Computer in der Lage sein immer kompliziertere Rechnungen durchzuführen. Das ist zum einen sehr erfreulich, mag den einen oder anderen aber vielleicht auch beunruhigen. Die diesem Artikel zugrunde gelegte Frage lautet: Gibt es nun aber tatsächlich zu jedem Problem ein Berechnungsverfahren, das von einem hinreichend schnellen Computer in absehbarer Zeit abgearbeitet werden kann?

Um diese Frage zu beantworten beschränkt man sich auf die Menge der Entscheidungsprobleme. Also Probleme, die entweder mit "richtig" oder "falsch" beantwortet werden können. Ein Berechnungsverfahren für Entscheidungsprobleme nennt sich Entscheidungsverfahren. Gibt es nun zu jedem Entscheidungsproblem ein Entscheidungsverfahren, welches von einer Maschine abgearbeitet werden kann? Man könnte meinen, dass diese Frage erst in den letzten Jahrzehnten mit Beginn des Informationszeitalters aufkam. Doch lange bevor überhaupt der erste Computer seinen Dienst aufnahm, war sie bereits beantwortet. David Hilbert war es, der diese Frage unter dem Namen "Entscheidungsproblem" als integralen Bestandteil seines Hilbertprogrammes zu Beginn des 20. Jahrhunderts folgendermaßen formulierte: "Das Entscheidungsproblem ist gelöst, wenn man ein Verfahren kennt, das bei einem vorgelegten logischen Ausdruck durch endlich viele Operationen die Entscheidung über die Allgemeingültigkeit bzw. Erfüllbarkeit erlaubt.(...)Das Entscheidungsproblem muss als das Hauptproblem der mathematischen Logik bezeichnet werden" Nicht nur deshalb besteht ein enger Zusammenhang zu den gleichfalls im Hilbertprogramm formulierten zentralen Fragen über die Vollständigkeit und Widerspruchsfreiheit der Mathematik. Diese beiden Fragen fanden ihre Beantwortung im berühmten Unvollständigkeitssatz von Gödel. Allerdings ließ Gödel die Frage des Entscheidungsproblems offen. Es gelang jedoch Church und unabhängig Alan Turing im Jahre 1936 eine befriedigende Antwort auf diese Frage zu finden. Die große Leistung Alan Turings bestand vor allem darin die Begriffe Problem und Berechnungsverfahren zu präzisieren. Er bediente sich dabei eines theoretischen Rechnermodels, welches heute unter dem Namen Turing-Maschine Eingang in die theoretische Informatik gefunden hat. Ein an das Vorgehen von Turing angelehnter Beweis soll im Folgenden betrachtet werden:

Definition Die Turing Maschiene

Eine Turing-Maschine T ist durch ein Sechstupel T={A, B, S, \delta, s_0, F) definiert, wobei A={e_1,...,e_r} das Alphabet, B das Leersymbol, S={s_0, s_2, s_3, ...,s_n } die Zustandsmenge, \delta: S \times A -> Q \times A \times {L,R,N) die Überführungsfunktion, s_0 \in S der Anfangszustand und F die Menge der Endzustände ist. Als Ergänzung zur mathematischen Definition lässt sich die Turing-Maschine auch durch das folgende Bild veranschaulichen. Bild Die Turing Maschine besteht aus einer Kontrolleinheit, aus einem Schreib- und Lesekopf sowie einem einseitig unbegrenzten Band. Die Kontrolleinheit kann endlich viele interne Zustände aus einer endlichen Zustandsmenge S annehmen. Das einseitig unendlich lange Band ist in verschiedene Felder aufgeteilt, wobei jedes genau ein Zeichen aufnehmen kann. Das Band dient als Eingabe und Speicherband. Bevor die Maschine beginnt zu arbeiten wird das Band "von außen" mit einem Starteintrag beschrieben, welcher aus Zeichen des Alphabetes A besteht. Alle sonstigen Felder des Bandes tragen zunächst (vor Beginn der Rechnung) das Leersymbol B. Die Maschine besitzt einen Anfangszustand s_0, sowie mehrere mögliche Endzustände aus der Menge F der Endzustände. Die Maschine bildet also den Starteintrag x auf den Endzustand f(x) ab. Die Funktionsweise der Maschine wird durch die Überführungsfunktion beschrieben. Je nach Zustand der Maschine und je nach dem über welchem Feld sie steht kann sie ihren Zustand ändern, das Feld umschreiben, und sich nach links oder rechts bewegen, sowie an ihrer Position verweilen.

Rechenbeispiel Turing Maschine

Jede Operation auf einem modernen Rechner lässt sich auch auf einer Turing Maschine durchführen. Ein einfaches Beispiel ist die Erhöhung einer gegebenen natürlichen Zahl um 1. Es lässt sich also die einfache Rechnung f(n)=n+1 durchführen. Die spezielle Turingmaschine für diese Rechnung lässt sich beschreiben durch: \E={0,1} B={\*} S={s_0, s_1, s_a} s_0 ist Anfangszustand F={s_a} und die Überführungsfunktion ist gegeben durch: \delta(s_0,0)=(s_a, 1, N) \delta(s_0,1)=(s_1, 0, L) \delta(s_1,1)=(s_1, 0, L) \delta(s_1,0)=(s_a, 1, N) \delta(s_1,\*)=(s_a, 1, N) Die Funktionsweise dieser speziellen Turingmaschine lässt sich auch anhand der obigen Abbildung mit dem speziellen Starteintrag 1101 überprüfen. Die Turingmaschine sollte die Abbildung 1101->1110 garantieren.

Definition 1. (intuitive) Berechenbarkeit

Es sei E ein Alphabet und M1, M2 \subsetequal E^\* Eine Funktion f: M_1 -> M_2 heißt \darkblue\stress\ berechenbar\normal\black||, falls es einen Algorithmus \(nach Def.2\) A_f: M_1->M_2 gibt mit A_f(w)=f(w) für alle w \in M_1. \mixoff

Definition 2. Algorithmus (intuitiv)

Unter einem Algorithmus versteht man eine präzise, endliche Verarbeitungsvorschrift, die so formuliert ist, dass die in der Vorschrift notierten elementaren Operationen von einer (mechanisch oder elektronisch) arbeitenden Maschine ausgeführt werden können.
Diese Definition ist intuitiv, da nicht exakt formuliert ist, wie eine solche Maschine auszusehen hat. Man kann dieser Formulierung allerdings bereits gewisse, den Algorithmus charakterisierende Eigenschaften, entnehmen, wie z.B. Abstraktion, Finitheit, Terminierung, Determinismus, Determiniertheit. Algorithmen können als Funktionen angesehen werden, die aus einer Menge zulässiger Eingabedaten (Eingangsoperanden) in die Menge der Ausgangsdaten(Ausgangsoperanden) abbilden. Eine präzise mathematische Formulierung gelang Turing durch das Turing-Maschinen Modell:

3.Definition Algorithmus

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.

4.Definition Turing-berechenbar

Eine Funktion f: M1 -> M2 heißt Turing-berechenbar, wenn es eine Turing-Maschine gibt, die f berechnet. Diese Definition wäre äquivalent mit der Definition 1, falls eine intuitiv berechenbare Funktion auch immer Turing-berechenbar wäre. Diese führt auf die folgende These:

5.Church-Turing These

Jede (intuitiv) berechenbare Funktion ist auch Turing-berechenbar. Diese Aussage rechtfertigt sich dadurch, dass in der Erfahrung noch keine intuitiv berechenbare Funktion vorgekommen ist, die nicht Turing berechenbar ist. Natürlich lässt sich diese These nicht beweisen, da der Begriff der berechenbaren Funktion nicht präzisiert ist. Welche Konsequenzen ergeben sich nun aber für die einleitende Frage, ob jedes Problem von einem Computer gelöst werden kann, bzw. ob das Entscheidungsproblem positiv gelöst werden kann. Es lässt sich nun zeigen, dass das Entscheidungsproblem, und somit die Frage nach der Berechenbarkeit von Problemen allgemein, eine negative Lösung besitzt. Zum Beweis formulieren wir nach der Idee von Turing ein spezielles Entscheidungsproblem, das so genannte Halteproblem: Das Halteproblem beschäftigt sich mit der Frage, ob eine Turing-Maschine (bzw. ein Algorithmus) auf eine beliebige Eingabe nach endlich vielen Schritten terminiert. Der Beweis, dass das Halteproblem nicht lösbar (entscheidbar bzw. berechenbar) ist, wird durch einen Widerspruchsbeweis geführt: Angenommen, das Halteproblem wäre entscheidbar. Dann lässt sich für das Halteproblem ein Entscheidungsverfahren in Form eines Algorithmus M folgendermaßen angeben: Der Algorithmus M bekommt als Eingabewert einen Algorithmus A zusammen mit einem dafür definierten Eingabewert x überwiesen. Der Algorithmus M soll den Ausgabewert "true" liefern, falls A mit zugewiesenem x terminiert. Falls A nicht terminiert, soll der Ausgabewert von A "false" sein. Dieser Algorithmus lässt sich durch Pseudocode veranschaulichen: \sourceon Pseudocode begin M(A, x); if (A(x)) terminiert) return true else return false end; \sourceoff Es lässt sich nun ein Algorithmus M'(A) formulieren, der als Eingabe einen Algorithmus A erhält und dann M auf der Eingabe (A,A) laufen lässt. Falls M true ausgibt, soll M' in eine Endlosschleife gehen (nicht terminieren), und halten (terminieren) wenn M false ausgibt. Auch dieser Algorithmus lässt sich durch Pseudocode veranschaulichen: \sourceon Pseudocode begin M'(A); if(M(A,A)) while(true); /* Endlosschleife */ else return; /* Stop */ end; \sourceoff M' terminiert dann, wenn A mit sich selbst als Eingabe nicht terminiert, bzw. M' terminiert nicht, wenn A mit sich selbst als Eingabe terminiert. Nun geben wir M' sich selbst als Eingabe über. Dann terminiert M' genau dann, wenn M' nicht terminiert. Um diesen Widerspruch zu lösen, muss die Vorausetzung der Entscheidbarkeit des Halteproblems fallen gelassen werden. Dieser Beweis zeigt, dass sich nicht berechenbare Funktionen konstruieren lassen. Insbesondere ist also gezeigt, dass es prinzipielle Grenzen der Berechbarkeit gibt, die mit keinem noch so schnellen Computer zu überwinden sind.

Ich danke Plex und Gockel für die hilfreiche und freundliche Diskussion. Quellen: A.M. Turing: On Computable Numbers, with an application to the Entscheidungsproblem Hilbert, Ackermann: Grundzüge der theoretischen Logik Rede von Hilbert auf dem Mathematiker Kongress in Paris 1900 Sander,Stucky,Herschel: Automaten, Sprachen, Berechenbarkeit de.wikipedia.org/wiki/Algorithmus de.wikipedia.org/wiki/Halteproblem en.wikipedia.org/wiki/Entscheidungsproblem
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Informatik :: Algorithmen :: Halteproblem :: Theoretische Informatik :: Turingmaschinen :
Heiße AlgoRhythmen: Grenzen der Berechenbarkeit [von ehpie]  
Ein Artikel über den Begriff der Berechenbarkeit und prinzipielle Hindernisse für die Lösbarkeit bestimmter Probleme. Es wird u.A. das Halteproblem besprochen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 3843
 
Aufrufstatistik des Artikels
Insgesamt 148 externe Seitenaufrufe zwischen 2012.01 und 2021.11 [Anzeigen]
DomainAnzahlProz
https://google.com106.8%6.8 %
https://matheplanet.com10.7%0.7 %
http://google.de10772.3%72.3 %
https://google.de74.7%4.7 %
http://google.nl53.4%3.4 %
http://google.it42.7%2.7 %
http://google.at32%2 %
https://html.duckduckgo.com32%2 %
https://www.startpage.com21.4%1.4 %
http://suche.t-online.de21.4%1.4 %
http://avira.search.ask.com10.7%0.7 %
http://search.incredimail.com10.7%0.7 %
http://r.duckduckgo.com10.7%0.7 %
http://google.com10.7%0.7 %

Häufige Aufrufer in früheren Monaten
Insgesamt 114 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2015 (71x)http://google.de/url?sa=t&rct=j&q=
2020-2021 (9x)https://google.com/
2020-2021 (6x)https://google.de/
201206-06 (6x)http://google.de/url?sa=t&rct=j&q=halteproblem turing computable numbers
201205-05 (5x)http://google.de/url?sa=t&rct=j&q=grenzen der berechenbarkeit
201203-03 (5x)http://google.nl/url?sa=t&rct=j&q=hilbert ackermann entscheidungsproblem
201211-11 (4x)http://google.de/url?sa=t&rct=j&q=hilbert/ackermann grundzüge der theoreti...
201204-04 (4x)http://google.de/url?sa=t&rct=j&q=hilbert ackermann entscheidungsproblem
201501-01 (4x)http://google.it/url?sa=t&rct=j&q=

[Top of page]

"Informatik: Heiße AlgoRhythmen: Grenzen der Berechenbarkeit" | 5 Comments
The authors of the comments are responsible for the content.

Re: Heiße AlgoRhythmen: Grenzen der Berechenbarkeit
von: Tobert am: Mi. 10. Januar 2007 16:46:00
\(\begingroup\)Hi, was bedeuten die s_0 ,s_1, s_a in dem Beispiel denn genau? sind das verschiedene Stellen der Zahl 1101? Oder wie werden die Ziffern in der Menge s genau beschreiben? Tobi\(\endgroup\)
 

Re: Heiße AlgoRhythmen: Grenzen der Berechenbarkeit
von: Ex_Mitglied_5557 am: Do. 11. Januar 2007 00:40:27
\(\begingroup\)Ist eigentlich ein Fortsetzungsartikel (passt gut zur Berechenbarkeit) zu Orakel-Turingmaschinen geplant? Da kann man nämlich auch ganz witzige Sachen machen, z.B. die Jump-Hierachie aufbauen: Was passiert, wenn ich mir jetzt einfach ein Orakel zu den normalen Turingmaschinen hinzunehme, dass die Turing-Maschinen bei Bedarf befragen können, welches das Halte-Problem entscheidet. Kann ich dann "alle Probleme lösen", oder gibt es auch dann wieder unlösbare Probleme? Antwort: Zweiteres. Aber was passiert, wenn ich mir ein solches Orakel hinzunehme? ... ;) Wobei auch Orakel-TMs aus Sicht der Komplexitätstheorie interessant sind: Was kann ich wie schnell berechnen, wenn ich bestimmte Orakelabfragen zulasse (die in einem Zeitschritt ablaufen)? Viele Grüße, Cyrix\(\endgroup\)
 

Zustandsmenge
von: ehpie am: Do. 11. Januar 2007 23:19:57
\(\begingroup\)Die s_0 ,s_1, s_a sind Elemente der Zustandsmenge und auch nur als solche definiert. Die Frage wie diese internen Zustände konkret aussehen ist innerhalb des Modells nicht beantwortet und ist fuer die Funktionstuechtigkeit des Modells auch nicht von Bedeutung. Wenn die Turing Maschine eine Zahl um eins erhöhen soll dann koennte der Schreib- und Lesekopf einfach in das erste Feld eine 1 schreiben und terminieren. Wenn das erste Feld aber bereits eine 1 enthaelt muss der Kopf solange weiterwandern, bis eine 0 kommt. Dann in dieses Feld eine 1 schreiben und dann terminieren. s_0 ist der Startzustand. s_1 ist der Zustand, indem die Maschine auf der Suche nach einem freien Feld ist. s_a ist der Endzustand. Die Bedeutung der Zustände fuer die Rechung erklärt sich im Prinzip durch die Ueberfuehrungsfunktion und laesst sich nur in den einfachsten Faellen verbal ausformulieren. Ich meine zu glauben, dass sich diese Turing Maschine auch ohne den Zustand s_1 konstruieren laesst, was vielleicht Ursache auftretender Verstaendnisprobleme wäre. Gruß ehpie \(\endgroup\)
 

Re: Heiße AlgoRhythmen: Grenzen der Berechenbarkeit
von: Ex_Mitglied_40174 am: Mi. 17. Januar 2007 21:08:16
\(\begingroup\)www.korrekturen.de/beliebte_fehler/algorythmus.html scnr.\(\endgroup\)
 

Re: Heiße AlgoRhythmen: Grenzen der Berechenbarkeit
von: Gockel am: Mi. 17. Januar 2007 21:38:17
\(\begingroup\)In Adaption von Ende kann man da (immer noch/schon wieder) nur fragen "Bist du mit dem Konzept von Wortspielen vertraut?" mfg Gockel.\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]