5.4Berechenbarkeit und Turing-Maschinen

Berechenbarkeit, Entscheidbarkeit und das Halteproblem

Manche Ja-Nein-Fragen über Programme kann kein Programm beantworten – das Halteproblem ist die berühmteste.

Leitformel
ChL(w)={1,w∈L0,w∉L\mathrm{Ch}_L(w) = \begin{cases} 1, & w \in L \\ 0, & w \notin L \end{cases}
ChL(w)\mathrm{Ch}_L(w)={1,w∈L0,w∉L= \begin{cases} 1, & w \in L \\ 0, & w \notin L \end{cases}
Lernziel

Entscheidbarkeit und Semi-Entscheidbarkeit unterscheiden, die Unentscheidbarkeit des Halteproblems per Diagonalargument beweisen und den Satz von Rice anwenden.

Einheit wird geladen …