Für Beispiel , die Sprache der Turing-Maschinen, die dies tun Akzeptieren Sie nicht ihre eigene Codierung kann nicht von einer Turing-Maschine akzeptiert werden.
Es gibt unendlich viele Sprachen, die kein TM entscheiden kann. In der Tat sind "die meisten" Sprachen unentscheidbar; es gibt abzählbar viele entscheidbare Sprachen, aber unzählbar viele Sprachen (daher unzählbar viele unentscheidbare).
Rices Theorem erlaubt Ihnen, viele Beispiele für Sprachen zu finden, die unentscheidbar sind. Siehe die Wikipedia-Seite: Rices Theorem
Wenn Sie eine Reihe von Sprachen haben, die nicht trivial sind (dh es gibt TMs, die Sprachen in der Menge erkennen, und TMs, die Sprachen nicht in der Menge erkennen), dann ist es unentscheidbar, ob eine beliebige TM-Sprache ist ist in S. Zum Beispiel sei S die Menge, die aus der leeren Sprache besteht. Dann ist es unentscheidbar festzustellen, ob ein beliebiges TM die leere Sprache akzeptiert, d. H. Keine Zeichenfolgen. Stellen Sie sich alle nicht-trivialen Sprachen ein und Sie haben eine neue unentscheidbare Sprache (alle Codierungen von TMs, die Sprachen in der Menge erkennen).
Tags und Links theory turing-machines computability