Maschinen in P unentscheidbar?

Bei einer Turing-Maschine sagen wir, dass wenn die von der Maschine festgelegte Sprache von einer Maschine in Polynomzeit bestimmt werden kann. Wir sagen, dass wenn die Maschine in Polynomzeit läuft. Beachten Sie, dass es Maschinen geben kann, die unnötig lange laufen, aber dennoch eine Sprache in . Nach dem Satz von Rice wissen wir das$M$$L(M) \in P$$M \in P$$P$

$\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) \in P \mbox{ } \}$ unentscheidbar ist. Ist bekannt, ob:

$\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }M \in P \mbox{ } \}$ ebenfalls unentscheidbar ist?

Hier ist eine Umschreibung des Beweises in der theoretischen Antwort. Wir reduzieren das Halteproblem. Angenommen, wir erhalten eine Maschine und müssen entscheiden, ob bei der leeren Eingabe anhält. Wir konstruieren eine neue Maschine , die eine einzelne Eingabe akzeptiert , die wie folgt funktioniert:$M$$M$$M'$$x$

1. Sei.$n = |x|$
2. $M'$ führt für Schritte aus.$M$$n$
3. Wenn innerhalb von Schritten angehalten hat führt eine Dummy-Schleife aus, die die exponentielle Zeit . Ansonsten hält einfach an.$M$$n$$M'$$\Omega(2^n)$$M'$

Da Turing-Maschinen nur mit Polynom-Overhead simuliert werden können läuft in Polynom-Zeit , wenn nicht anhält . Wenn anhält, nimmt exponentielle Zeit in Anspruch. Daher hält an, wenn keine Polynomzeit ist.$M$$M'$$M$$M'$$M$$M'$

Dies zeigt ganz allgemein, dass , auch wenn wir wissen , dass höchstens in der Zeit abläuft für einige superpolynomielle zeit konstruierbar , dann können wir nicht entscheiden , ob in Polynom Zeit abläuft.$M$$f(n)$$f$$M$

Die Art und Weise, wie Ihre zweite Sprache geschrieben ist, ist in Bezug auf normale Standards nicht genau formuliert. ist eine Reihe von Sprachen und keine Reihe von Maschinen. Basierend auf dem, was Sie im Rest Ihrer Frage gesagt haben, gehe ich davon aus, dass Sie versuchen, zwischen Maschinen zu unterscheiden, die höchstens polynomiell laufen, und solchen, die ein Problem in lösen . Vielleicht wäre dies ein besserer Weg, um es zu schreiben als:$P$$P$

$A=\left \{ \left \langle M \right \rangle | (\exists k \forall x) M(x) \text{ halts in } O \left ( |x|^{k}\right ) \text{ time} \right \}$

$O$ kann durch ersetzt werden $\Theta$ Wenn Sie schwächere Computer wie Protokollzeit-TMs ausschließen möchten.

Beachten Sie, dass: $A\subset\{\langle M \rangle|L(M) \in P \}$

Wie von sdcvvc beobachtet , gilt der Satz von Rice hier nicht sofort und reicht nicht aus, da die verwendete "nicht triviale" Eigenschaft eine Eigenschaft von sein muss$L(M)$. Eine an eine Maschine gebundene Zeit ist keine Eigenschaft der Sprache, sondern eine Eigenschaft dieser Maschine.

Eine Antwort für eine vorgegebene $k$wurde die theoretische Frage diskutiert, auf die in den Kommentaren Bezug genommen wird. Die Wahl dieser Konstante war der Schlüssel zum Beweis der Unentscheidbarkeit. In unserer Sprache enthalten wir alle$k\in\mathbb{N}$ und haben daher kein Maximum $k$ arbeiten mit.

Ich hatte keine Zeit, um ausreichend Nachforschungen anzustellen, aber ich stelle mir vor, dass es nicht unangemessen wäre, ihre Ergebnisse auf irgendwelche auszudehnen $k>2$ über direkte Induktion.

Ein aktuelles Papier geschrieben von David Gajser, der durch dem die cstheory Post motiviert war, antwortet eine verallgemeinerte Version dieser Frage:

Lassen $HALT_{T(n)} = \{ \langle M\rangle|\forall x M(x) \text{ halts in at most } T(n=|x|) \text{ time}\}$

Für Einzelband-Turingmaschinen: $HALT_{T(n)}$ ist unentscheidbar, wenn $T(n)= \Omega(nlog(n))$

Für Turingmaschinen mit mehreren Bändern: $HALT_{T(n)}$ ist entscheidbar iff $T(n) \leq k+1$ für einige $k\in \mathbb{N}$

Er erweitert diese Unentscheidbarkeitsergebnisse auf Klassen mit beliebig großen Konstanten (wie z $P$). Ihm zufolge ist die Antwort auf Ihre Frage, dass die Sprache ($A$) ist unentscheidbar.