Für example kann die Sprache von Turing-Maschinen, die ihre eigene Codierung nicht akzeptieren, von keiner Turing-Maschine akzeptiert werden.Was sind alle bekannten Sprachen, die Turing-Maschinen nicht akzeptieren können?
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ählige Sprachen (daher unzählige unentscheidbare).
Rices Theorem erlaubt Ihnen, viele Beispiele von Sprachen zu finden, die unentscheidbar sind. Siehe die Wikipedia-Seite: Rice's Theorem
Grundsätzlich, wenn Sie eine Reihe von Sprachen haben, die nicht trivial ist (dh es gibt TMs, die Sprachen in der Menge erkennen, und TMs, die Sprachen nicht in der Menge erkennen), dann ist es Unentscheidbar ist, ob eine beliebige TM-Sprache in S ist. 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 im Set erkennen).