Zeigen Sie, dass Leere und Endlichkeit für lineare beschränkte Automaten unlösbar sind, ich habe nicht verstanden, kann mir jemand helfen?zeigen, dass Leere und Endlichkeit für lineare begrenzte Automaten nicht lösbar sind
Durch das Lösen von Leerstellen können Sie feststellen, ob ein linearer begrenzter Automat überhaupt etwas akzeptiert, und das Lösen der Endlichkeit bedeutet, dass Sie feststellen können, ob ein linearer begrenzter Automat eine endliche Menge akzeptiert oder nicht.
Der Beweis, dass die Leere linearer Automaten nicht lösbar ist, hängt davon ab, dass sie auch für Turing-Maschinen nicht lösbar ist.
Für jede Turing-Maschine gibt es einen linear begrenzten Automaten, der die Zeichenketten akzeptiert, die für die Turing-Maschine gelten.
Wenn eine Turing-Maschine nichts akzeptiert, dann ist die Menge der Strings, die gültige Berechnungen anhalten, leer. Die linearen begrenzten Automaten, die die Stopp-Berechnungen dieser Turing-Maschine akzeptieren, akzeptieren ebenfalls nichts. Wenn es möglich wäre festzustellen, ob ein linearer begrenzter Automat nichts akzeptiert oder nicht, dann wäre es möglich zu bestimmen, ob eine Turing-Maschine nichts akzeptiert oder nicht, aber dies ist ein Widerspruch, weil es nicht möglich ist, zu sagen, ob ein Turing vorliegt oder nicht Maschine akzeptiert nichts.
Der Beweis für die Endlichkeit, die für lineare beschränkte Automaten unlösbar ist, ist derselbe. Wenn die Menge, die eine Turing-Maschine akzeptiert, endlich ist, akzeptiert ein linearer begrenzter Automat diese endliche Menge. Wenn es möglich wäre zu bestimmen, ob ein linearer begrenzter Automat eine endliche Menge akzeptiert, wäre es auch möglich zu bestimmen, ob eine Turing-Maschine eine endliche Menge akzeptiert, aber dies ist ein Widerspruch, weil es unmöglich ist, eine Turing-Maschine zu bestimmen akzeptiert eine endliche Menge.
Diese Probleme sind für Turing-Maschinen unlösbar, da nur triviale Mengeneigenschaften für die berechenbaren Mengen lösbar sind. Die Menge K = {i | M_i (i) hält an} ist unlösbar und Endlichkeit und Leere können auf die Menge K reduziert werden, weshalb sie für Turing-Maschinen unlösbar sind.