WikiDer > Beenden Sie das Problem

Es Stoppproblem, auch bekannt als "Halteproblem", ist es Entscheidungsproblem von dem Mathematik und Informatik, um zu bestimmen, ob a Algorithmus mit endlicher Eingabe in endlich vielen Schritten endet oder unendlich weitergeht. Es ist ein bekanntes Beispiel für ein mathematisches Problem, das unentscheidbar und eines der ersten als solche erkannten Probleme. Dies wurde bewiesen durch Alan Turing im 1936.

Definition

Das Stoppproblem wird informell wie folgt definiert Entscheidungsproblem:

Ein Programm gegeben ${Anzeigestil M}$ und ein Eingabewert ${Anzeigestil x}$, herausfinden, ob ${Anzeigestil M}$ mit Eingang ${Anzeigestil x}$ stoppt nach einer endlichen Anzahl von Schritten.

Um das Stoppproblem formal zu definieren, müssen wir uns darauf einigen, was wir unter dem Begriff Programm verstehen. Ursprünglich das Stoppproblem für Turing-Maschinen formuliert, kann aber auch analog für andere Turingfull Formalismen definiert.

Die Eingabe einer Turingmaschine besteht aus einer Reihe von Symbolen, a Schnur. Damit Turing-Maschinen als Input für andere Turing-Maschinen verwendet werden können, müssen wir sie zuerst codieren, oder Computerprogrammierung. Zum Beispiel können wir alle Turing-Maschinen in einer Reihe auflisten und dann die Sequenznummer in dieser Reihe als Code für die Turing-Maschine verwenden. wenn ${Anzeigestil w}$ ein Code für eine Turingmaschine ist, dann schreiben wir ${displaystyle M_{w}}$ für die durchlaufende Turingmaschine ${Anzeigestil w}$ ist kodiert. Außerdem schreiben wir ${displaystyle langle x,yangle }$ für den Code des Paares ${Anzeigestil(x,y)}$. Das Stoppproblem kann nun formal wie folgt definiert werden:

${displaystyle h(langle w,xangle )={ egin{cases}1&{ ext{as Turingmaschine }}M_{w}{ ext{ stoppt in endlich vielen Schritten mit }}x{ ext{ als Eingabe}}/ 0&{ ext{other}}end{cases}}}$

Entscheidungsprobleme werden oft auch als Menge positiver Eingabewerte definiert, daher lautet die Definition des Stoppproblems alternativ:

${displaystyle H={langle w,xangle mid { ext{Turingmaschine }}M_{w}{ ext{ stoppt in endlich vielen Schritten mit }}x{ ext{ als Eingabe}}}}$

Unentscheidbarkeit

Alan Turing bewies 1936, dass das Stoppproblem unentscheidbar ist. Das heißt, es gibt keine Turingmaschine, die in allen Fällen richtig entscheidet, ob eine Turingmaschine mit einem bestimmten Eingangswert in endlich vielen Schritten stoppt oder nicht.

Für seinen Beweis bzw. für die Definition des Algorithmus kam Turing auf die später berühmte Idee der Turing-Maschine.

Quellen

• (und) Elaine Rich, Automaten, Berechenbarkeit und Komplexität. Theorie und Anwendungen., 2008