Gibt es eine unentscheidbare endliche Sprache endlicher Wörter?

10

Gibt es einen Bedarf für $L\subseteq \Sigma^*$ sein unendlich unentscheidbar zu sein?

Ich meine , was ist, wenn wir eine Sprache wählen $L'$ sein eine begrenzte endliche Version von $L\subseteq \Sigma^*$ , das heißt $|L'|\leq N$ , ( $N \in \mathbb{N}$ ) mit $L' \subset L$ . Kann $L'$ eine unentscheidbare Sprache sein?

Ich sehe, dass es ein Problem gibt, "wie man die $N$ Wörter wählt, die für das wir eine Regel für die Auswahl der ersten Elemente von festlegen müssen, eine Art "endliche" Kleene-Stern-Operation . Das Ziel ist es, eine Sprache der Unentscheidbarkeit zu finden, ohne eine unendliche Menge zu benötigen, aber ich kann sie nicht sehen. $\in$ $L' "$ $N$ $L'$

Notiz bearbeiten:

Obwohl ich eine Antwort gewählt habe, sind viele Antworten und alle Kommentare wichtig.

formal-languages computability undecidability Hernan_eche
quelle

Hier scheint es (mindestens) drei Fragen zu geben. Bitte konzentrieren Sie sich auf eines und bearbeiten Sie die anderen.

Raphael

Ich habe die Verweise auf das Power-Set entfernt, da es hier nicht relevant ist.

P (S)

$\mathcal{P}(S)$ ist genau dann endlich, wenn

S

$S$ endlich ist.

Raphael

@Raphael Es ist in Ordnung, aber ich erwähne Power Set, weil ich manchmal lese "Es gibt keine Surjektion von auf , daher muss es eine unentscheidbare Sprache geben." $\mathbb{N}$ $\mathcal{P}(\mathbb{N})$ Ich würde gerne verstehen, warum das mit einer endlichen Menge , mit mit endlich nicht funktioniert hat , anstatt benötigen , deshalb setze ich

L^{'}

$L'$

| L^{'} | \leq N

$|L'|\leq N$

N

$N$

N

$\mathbb{N}$

P (S)

$\mathcal{P}(S)$

Hernan_eche

1

Soweit ich weiß, folgt die Existenz unentscheidbarer Sprachen nicht unmittelbar aus dem Nichtvorhandensein einer solchen Vermutung; Du brauchst ein paar Kleinigkeiten mehr. Das würde eine weitere wunderbare Frage stellen! Warum fragst du es nicht? Daraus sollten Sie ersehen, warum sich das Argument nicht auf endliche Sprachen überträgt.

Raphael

3

Endliche Sprache sind entscheidbar, Punkt, Ende der Geschichte. Dafür gibt es eine beliebige Anzahl von Algorithmen. Wenn Sie auf dem klassischen Turing Machine-Modell bestehen, können Sie dies auch so tun, wenn auch weniger scharfsinnig. Es ist nicht erforderlich, Automaten mit endlichen Zuständen oder reguläre Sprachen oder ein anderes Automatenmodell aufzurufen, da diese tatsächlich ohne zusätzliche Klarheit gegenüber Turing-Maschinen übertrieben sind.

David Lewis

15

Ja, muss unendlich sein, um unentscheidbar zu sein. $L$

Um die Antworten von Raphael und Sam zusammenzufassen, sollten Sie sich "entscheidbar" als Dinge vorstellen, die ein Computerprogramm lösen kann. Das erforderliche Programm ist sehr einfach, es muss nur "Ja" für Elemente in ausgeben oder auf andere Weise Nein sagen. $L$

Je "komplexer" ist, desto länger ist das Programm, das Sie schreiben müssen. Mit anderen Worten, je länger das Programm läuft, desto mehr Dinge können Sie überprüfen ... Wenn also jemand eine Sprache die endlich ist, sagen Sie , können Sie das schreiben folgendes Programm: $L$ $L$ $L=\{ a_1, a_2, \ldots, a_n\}$

if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;

Wenn Ihnen jemand ein größeres (aber endlich) gibt, schreiben Sie einfach ein längeres Programm. Dies ist immer wahr und jedes endliche hat sein eigenes Programm. Der einzige "interessante" Fall ist, was passiert, wenn unendlich ist - Ihr Programm kann nicht unendlich sein. $L$ $L$ $L$

Das Problem der "Unentscheidbarkeit" ist noch interessanter: Es sind jene (unendlichen) , die kein Programm haben, das für sie richtig funktioniert. Wir wissen, dass solche Sprachen existieren müssen, da es weit mehr (unendliche) Sprachen als die Anzahl der Programme endlicher (aber unbegrenzter) Länge. $L$ $L$

Ran G.
quelle

+1 Dies ist eine sehr klare Antwort. Ich möchte, dass Sie einen Punkt erweitern. Sie haben gesagt: "Wenn Ihnen jemand ein größeres (aber endlich) gibt, schreiben Sie einfach ein längeres Programm." * Aber ich denke das Gegenteil, wenn man eine ** feste ** endliche Menge von Programmen , was ist, wenn man kein längeres Programm schreiben kann ? Ich denke, einige Eingaben eine endliche Menge werden JA ergeben, andere nicht . Als dann einige der Eingaben den Indikatorfunktionen aber * die meisten $L$ $P$ $|P|=K$ $\in L$ $\mathcal{P}(P) \gt K$ $\in L$ $P$ nicht!, Weil mögliche Sprachen

2^{K}

$2^K$

> K

$\gt K$ mögliche Programme, dann wird es unentscheidbare Probleme geben. Liege ich falsch? Warum?

Hernan_eche

1

Wenn Sie die Größe des Programms auf gibt es höchstens verschiedene Programme, die höchstens verschiedene Sprachen (unendlich oder nicht) korrekt klassifizieren . Für diesen speziellen Satz von Programmen gibt es also unentscheidbare Sprachen und sogar eine endliche. Dies ist jedoch eine schwächere Aussage, da Sie nur eine begrenzte Anzahl von Programmen betrachten (z. B. , Sie haben nur 2 mögliche Programme; natürlich können sie nicht viel und scheitern in fast jeder Sprache )

| P | = k

$|P|=k$

O (2^{k})

$O(2^k)$

O (2^{k})

$O(2^k)$

| P | = 1

$|P|=1$

L

$L$

Ran G.

danke, ich weiß, dass dies eine schwächere Aussage ist, aber es ist mutig, dass es endliche und unendliche unentscheidbare Sprachen geben kann, und ich denke, dieser Sonderfall muss in Ihrer Antwort enthalten sein, der Teil "Ja, es besteht die Notwendigkeit, dass L unendlich ist." um unentscheidbar zu sein. " scheint unter bestimmten Bedingungen kein Bedürfnis zu sein .

Hernan_eche

6

Nicht genau. Der Begriff "unentscheidbar" hat eine bestimmte Bedeutung: Nicht von einer Standard-Turing-Maschine entscheidbar. Um zu sein undecidable, muss unendlich sein. Was Sie wollen, ist nur ein anderer Begriff, nämlich "nicht durch entscheidbar ". Nennen Sie das letztere Unentscheidbar. Dann gibt es für jedes endliche keine Notwendigkeit, dass unendlich ist, um unentscheidbar zu sein. Nur nicht verwirren (oder missbrauchen) und unentscheidbar

L

$L$ undecidable

P

$P$

P

$P$

P

$P$

L

$L$

P

$P$ undecidable

P

$P$

Ran G.

10

Ich bin mir nicht sicher, ob ich die Frage richtig verstehe, aber jede endliche Sprache ist regelmäßig. Es gibt keine regulären Sprachen, die unentscheidbar sind, und daher gibt es keine endlichen Sprachen, die unentscheidbar sind. Alle diese Aussagen sind bekannt und Beweise finden sich in Hopcroft und Ullman .

Sam Jones
quelle

8

Wenn Ihre Sprache endlich ist, können Sie eine Tabellensuche für eine fest codierte Tabelle durchführen, die alle Wörter in . Es ist umständlich, dies als Turing-Maschine aufzuschreiben, aber bei anderen gleichwertigen Modellen ist das ziemlich klar. $L'$ $L'$

In der Tat sind endliche Automaten ausreichend. Konstruieren Sie einen Automaten für wie folgt: $L'$

Erstellen Sie für jedes eine lineare Zustandskette, die akzeptiert . $w \in L'$ $w$
Erstellen Sie einen neuen Ausgangszustand . $q_0$
Verbinden Sie mit den Anfangszuständen aller in 1. konstruierten Automaten mit -übergängen. $q_0$ $\varepsilon$

Der so konstruierte Automat akzeptiert offensichtlich . Daher ist regulär und damit berechenbar (durch ). $L'$ $L'$ $\mathrm{REG} \subsetneq \mathrm{RE}$

Beachten Sie, dass einige Überlegungen für co-finite , dh ; Sie codieren nur die Elemente, die nicht in . $L'$ $\big|\overline{L'}\big| < \infty$ $L'$

Raphael
quelle

2

Um überhaupt interessant zu sein (um über Berechenbarkeit nachzudenken), muss ein Entscheidungsproblem unendlich viele "Ja" -Antworten und unendlich viele "Nein" -Antworten haben. Solche Entscheidungsprobleme entsprechen genau Sprachen, die unendlich viele Zeichenfolgen über ihrem Alphabet enthalten und auch unendlich viele Zeichenfolgen über ihrem Alphabet ausschließen.

Alles andere kann trivialerweise nur in einer endlichen Menge an Informationen codiert werden (im schlimmsten Fall einfach in einer großen Liste von Zeichenfolgen, entweder in oder nicht in der Sprache) und kann daher durch einfache DFAs / reguläre Ausdrücke berechnet werden. Ich würde hoffen, dass es offensichtlich ist, dass Sie für jede endliche Liste von Zeichenfolgen sofort einen regulären Ausdruck aufschreiben können, der einfach alle Zeichenfolgen ODER-verknüpft.

Ein Witz meines Dozenten für Theorie der Berechnung war, dass das Problem "Existiert Gott?" ist berechenbar - es wird entweder von einer Maschine berechnet, die sofort akzeptiert, oder von einer Maschine, die sofort ablehnt; wir wissen einfach nicht welche!

Ben
quelle

Gibt es eine unentscheidbare endliche Sprache endlicher Wörter?

Antworten: