Gibt es unbestreitbare Eigenschaften von nicht vollständig funktionierenden Automaten?

15

Gibt es unentscheidbare Eigenschaften von Automaten mit linearer Begrenzung (um den Trick mit der leeren eingestellten Sprache zu vermeiden)? Was ist mit einem deterministischen endlichen Automaten? (Unlösbares beiseite legen).

Ich möchte (wenn möglich) ein Beispiel für ein unentscheidbares Problem erhalten, das definiert wird, ohne Turing-Maschinen explizit zu verwenden.

Ist die Vollständigkeit eines Modells zur Unterstützung nicht berechenbarer Probleme erforderlich?

computability automata undecidability Hernan_eche
quelle

"Gibt es eine Lösung für dieses diophantinische Gleichungssystem?" Ist es das was du fragst? Mir ist nicht klar, was Sie wollen. Aber das Problem, das ich gegeben habe, ist unentscheidbar und erwähnt TM nicht, daher scheint es genau genommen die Anforderungen Ihres zweiten Absatzes zu erfüllen.

Rgrig

Zu entscheiden, ob zwei Pushdown-Automaten die gleichen Wörter erkennen, ist ebenso unentscheidbar wie andere Probleme mit Pushdown-Automaten . Ich kann mir keine unentscheidbaren Probleme mit DFAs vorstellen.

jmad

1

Die Antwort auf die Frage : „Ist es möglich , ein unentscheidbar Problem für einen Automaten weniger leistungsfähig als eine Turing - Maschine zu bauen“ ist ja . Tatsächlich kann man für jeden Automatentyp immer ein unentscheidbares Problem identifizieren.

Amelio Vazquez-Reina

1

Angesichts der akzeptierten Antwort formulierte ich die Frage neu, um zu fragen, was das OP (anscheinend) will.

Raphael

15

Unentscheidbare Probleme mit kontextfreien Grammatiken und damit auch mit Pushdown-Akzeptoren, bei denen es sich um eingeschränkte TMs aus Wikipedia handelt ...

Erzeugt ein CFG die Sprache aller Zeichenfolgen über dem Alphabet der Terminalsymbole, die in seinen Regeln verwendet werden?
Generieren sie bei zwei CFGs dieselbe Sprache?
Kann die erste bei zwei CFGs alle Zeichenfolgen generieren, die die zweite generieren kann?

Es gibt viele andere über CFGs / PDAs sowie CSGs / LBAs und viele andere "einfacher als TM" -Modelle.

David Lewis
quelle

+1, danke, ich bin immer noch versucht, nach einem einfacheren als CFG zu fragen und so weiter. Um herauszufinden, welches der ersten (einfacheren) bekannten Automaten + Probleme unentscheidbar ist

Hernan_eche

3

Um ein "einfacheres" oder "einfachstes" Problem zu finden, das unentscheidbar ist oder eine Eigenschaft hat, benötigen Sie eine genaue Definition von "einfach", von denen viele möglich sind. Aber die klassische in Automaten und formalen Sprachen ist "Ebene in der Chomsky-Hierarchie" (die mathematisch gesehen keine wirkliche Hierarchie darstellt - sie wurde ursprünglich für Grammatiken in natürlicher Sprache vorgeschlagen). FSA ist die niedrigste, und ich bin mir ziemlich sicher, dass jedes für FSAs unentscheidbare Problem auf eine "wesentliche" Weise auf "weniger einfache" Formalismen verweisen müsste (alle müssen genau definiert werden). CFL / CFG ist als nächstes am höchsten, also habe ich das ausgewählt.

David Lewis

+1 Ich stimme zu, finde das Minimum ist auch unentscheidbar, überraschenderweise ist es nicht möglich, ein unentscheidbares Problem für FSA zu schaffen, dann ist es für CFG möglich, ist nur versucht, etwas dazwischen zu finden, danke

Hernan_eche

1

@Hernan_e - es gibt eine sehr umfangreiche Struktur von Sub-CFL-Modellen und -Sprachen - zum Beispiel die 1-Zähler-pda / -Familie, die einen positiven ganzzahligen "Zähler" anstelle eines pda verwendet; das n-turn pda, das nur eine drehung von erhöhung zu erniedrigung des stapels erlaubt, und generalisierungen davon. Und es gibt viele unentscheidbare Fragen zu diesen sowie offene Fragen zu den Strukturen, zum Beispiel: Gibt es eine "minimale" nicht reguläre CFL in einem präzisen Begriff von "minimal". Aber das Zeug ist in der Regel auf der Grad und / oder Forschungsebene.

David Lewis

7

Es ist nicht klar, was Sie im späteren Teil der Frage fragen, hauptsächlich weil "ein Problem mit einem Maschinenmodell" nicht definiert ist.

Ich möchte ein Beispiel (wenn möglich) für ein unentscheidbares Problem erhalten, ohne Turing Machine zu benötigen

Sei eine Klasse von Maschinen und benutze als Code von . Wir können auch als den Code des ten TM interpretieren und dann fragen, ob bei gegebenem das te TM halt macht? Und dieses Problem in Bezug auf s ist nicht zu entscheiden. $\{M_i\}$ $i$ $M_i$ $i$ $i$ $M_i$ $i$ $M_i$

Eine Sprache ist nur ein Satz von Zeichenfolgen. Welche Interpretation Sie den Zeichenfolgen zuweisen, hat keinen Einfluss auf die Entscheidbarkeit der Sprache. Wenn Sie nicht formal definieren, was Sie unter einem Maschinenmodell und einem Problem mit diesen Maschinen verstehen, können Ihre späteren Fragen nicht beantwortet werden.

Ist Turing mit der minimalen Maschinerie fertig, um ein unentscheidbares Problem zu lösen?

Auch hier gilt der oben erwähnte Punkt. Eine vernünftigere Frage wäre: Gehen alle Unentscheidbarkeitsnachweise durch etwas, das der Unentscheidbarkeit des Stopp-Problems für TMs ähnelt? (Die Antwort lautet: Es gibt andere Wege).

Eine andere mögliche Frage ist: Was ist die kleinste Untergruppe von TMs, bei denen das Stopp-Problem für sie nicht zu entscheiden ist? Offensichtlich sollte eine solche Klasse Probleme enthalten, die nicht aufhören (ansonsten ist das Problem trivial entscheidbar). Wir können auf einfache Weise künstliche Untergruppen von TMs erstellen, bei denen das Halteproblem nicht entschieden werden kann, ohne in der Lage zu sein, irgendetwas Nützliches zu berechnen. Eine interessantere Frage betrifft große entscheidbare Mengen von TMs, bei denen das Anhalten für sie entscheidend ist.

Hier ist ein weiterer Punkt: Sobald Sie nur über eine sehr geringe Manipulationsfähigkeit für Bits verfügen (z. B. eine Polynomgröße ), können Sie eine Maschine mit drei Eingaben erstellen : , und , sodass sie 1 ausgibt, wenn ist akzeptierende Berechnung von TM Anhalten am Eingang . Dann können Sie folgende Fragen stellen: Gibt es ein st mit 1? Das ist ein unentscheidbares Problem. $\mathsf{CNF}$ $N$ $e$ $x$ $c$ $c$ $M_e$ $x$ $c$ $N(e,x,c)$

Kaveh
quelle

5

Es gibt ein sehr einfaches und unentscheidbares Problem für Automaten mit endlichen Zuständen. Brechen Sie das Alphabet in zwei Hälften , wobei die Buchstaben in „gesperrt“ sind Kopien. Nun, da ein endlicher Automat über entscheiden , ob es eine Zeichenfolge so akzeptiert , dass der unbarred Teil des vergitterten Teil gleich (wenn wir ignorieren die Balken). ZB Zeichenfolge wäre in Ordnung sein (beide Teile buchstabieren ). $\Sigma \cup \bar\Sigma$ $\bar\Sigma$ $A$ $\Sigma\cup\bar\Sigma$ $a a \bar a \bar a b\bar b \bar aa$ $aaba$

Ja, dies ist ein Post-Korrespondenz-Problem, das in einem Automaten mit endlichen Zuständen verborgen ist. Die Turing-Vollständigkeit ist in der Frage alles andere als offensichtlich. Es ist dort im Hintergrund, während die zwei Kopien (nicht gesperrt und gesperrt) zusammen eine Warteschlange codieren, die selbst von Turing-Macht ist.

Hendrik Jan
quelle

Hast du einen Hinweis dazu? Es ist nicht sofort ersichtlich, wie man PCP in dieses konvertiert. Zu Ihrer Information gibt es auch einige unentscheidbare Probleme mit FSM- "Wandlern".

22.

1

(u_{1}, \dots, u_{n})

$(u_1,\dots,u_n)$

(v_{1}, \dots, v_{n})

$(v_1,\dots,v_n)$

{u_{1} {\bar{v}}_{1}, \dots, u_{n} {\bar{v}}_{n}}^{+}

$\{ u_1\bar v_1, \dots, u_n\bar v_n \}^+$

\bar{v}

$\bar v$

v

$v$

3

"Ist es möglich, ein unentscheidbares Problem für einen weniger leistungsstarken Automaten als eine Turing-Maschine zu entwickeln?"

Ja. Ein Automat ist eine konsistente axiomatische Formulierung der Zahlentheorie (siehe z. B. (1) ) und muss daher nach Gödels 1. Unvollständigkeitssatz unentscheidbare Sätze enthalten.

Beispiel:

Jedes Problem , das für ein TM unentscheidbar ist, ist auch für jeden Automaten unentscheidbar, den ein TM simulieren kann. Warum? Denn wenn ein Automat, der weniger mächtig als ein TM ist, eine Sprache bestimmen könnte, die ein TM nicht entscheiden kann, sollte ein TM in der Lage sein, dies zu entscheiden, indem es den Automaten simuliert, der einen Widerspruch ergibt.

Amelio Vazquez-Reina
quelle

2

Die Frage, ob eine LBA anhält oder nicht, ist auch für eine TM entscheidend, sodass sie nicht Teil der Beispiele war, die ich in meiner Antwort angegeben habe. Jedes Problem, das für ein TM unentscheidbar ist, ist auch für ein LBA unentscheidbar.

Amelio Vazquez-Reina

1

{T | T M T h a l t s o n i n p u t T}

$\{T|TM T halts on input T\}$ das ist eindeutig nicht entscheidbar, aber das ist erfunden. Das kann wohl formalisiert werden.

David Lewis

1

{T | TM T (T) halts}

$\{T|\text{ TM } T(T) \text{ halts}\}$

1

@DavidLewis Roseck behauptet nicht, dass ein unentscheidbares Problem mit TMs immer noch unentscheidbar ist, wenn Sie es so interpretieren, dass es sich um LBAs handelt. Roseck stellt lediglich fest, dass, wenn es ein Problem gibt, das von TMs nicht entschieden werden kann, dasselbe Problem ohne Neuinterpretation auch von nichts entschieden werden kann, was ein TM simulieren kann. Das TM-Stopp-Problem und das LBA-Stopp-Problem sind zwei unterschiedliche Probleme.

Ben

1

@Ben - wenn ja, dann müsste "... für jeden Automaten, der ..." unentscheidbar sein " by ". Aber das ist eine triviale Aussage.

David Lewis

1

Emil Post wollte die Antwort auf genau diese Frage finden: Gibt es eine nicht rekursive (nicht berechenbare) Menge, die das Halteproblem nicht löst? Es gelang ihm nur zum Teil, aber was er tat, war die Schaffung sogenannter einfacher Mengen .

Aus Wikipedia:

Eine Teilmenge der Naturalien heißt einfach, wenn sie koinfinitiv und rekursiv aufzählbar ist, aber jede unendliche Teilmenge ihres Komplements nicht rekursiv aufzählbar ist. Einfache Mengen sind Beispiele für rekursiv aufzählbare Mengen, die nicht rekursiv sind. Werfen Sie einen Blick auf dem Wikipedia - Artikel für weitere Informationen und Referenzen, einfachen Satz .

Pål GD
quelle

Gibt es unbestreitbare Eigenschaften von nicht vollständig funktionierenden Automaten?

Antworten: