Die Subsprache ist nicht Turing-erkennbar, oder könnte es sein?

10

A und B seien Sprachen mit A ⊆ B, und B ist Turing-erkennbar. Kann A nicht Turing-erkennbar sein? Wenn ja, gibt es ein Beispiel?

computability gfe
quelle

18

Dies ist etwas, das viele Studenten verwirrt. Der Punkt hier ist, dass eine Teilmenge einer anderen Sprache nicht viel über ihre Schwierigkeit der Berechnung bedeutet. Sie können immer die triviale Sprache und berücksichtigen, und jede andere Sprache befindet sich zwischen ihnen, um die Aufnahme einzuschließen. $\emptyset$ $\Sigma^*$

Nur zu wissen, dass eine Sprache eine leicht zu berechnende Sprache enthält oder in dieser enthalten ist, sagt daher nichts über die Schwierigkeit aus, sie zu berechnen.

Kaveh
quelle

Aber ich kann keine Teilmengensprache von Σ Σ finden, die nicht Turing-erkennbar ist.

gfe

3

@Wilhelm, nimm jede Sprache, die nicht Turing-erkennbar ist und es wird funktionieren.

Kaveh

Ich verstehe, also kann ich das Halteproblem nutzen, um zu beweisen, dass es eine solche Sprache gibt.

gfe

@ Wilhelm, ja. :)

Kaveh

1

Wenn ein Turing erkennbare Sprache ist nicht entscheidbar, impliziert dies , dass es nicht-co-Turing erkennbar ist (in anderen Worten: ist nicht erkennbar). Da ist eine absolut gültige Teilmenge von , Dies unterstützt die Tatsache , dass für eine Sprache wobei Turing-erkennen ist, kann sehr wohl nicht sein. $X$ $X^c$ $X^c$ $\Sigma^*$ $A \subseteq B$ $B$ $A$

Sander
quelle

Ich denke, Kavehs Antwort ist besser und auf den Punkt gebracht. Jede Sprache ist eine Teilmenge von

und wir wissen , dass

entscheidbar ist und dass es willkürlich Fest Sprachen.

Σ^{*}

$\Sigma^*$

Σ^{*}

$\Sigma^*$

Pål GD

Das ist , was ich versuchte, zu erklären , wie

jede Sprache sein könnte, weil

automatisch hält. ;)

X

$X$

X \subset Σ^{*}

$X \subset \Sigma^*$

Sander

-3

Ihre Diskussion hat mich erfolgreich verwirrt :(

"Kann A nicht Turing-erkennbar sein?"

Ich denke, A ist immer Turing-erkennbar . Hier ist mein Denken,

Da B Turing erkennbar ist => Es gibt ein TM, das alle Wörter der Sprache akzeptiert. B => Es gibt ein TM, das akzeptiert (alle Wörter der Sprache A + einige andere Wörter) => Es gibt ein TM, das alle Wörter akzeptiert der Sprache A => A ist Turing erkennbar.

Ist das falsch? Kann es einen Fall geben, in dem A nicht TRL ist, während B TRL ist? Freundlich helfen

Bongubj
quelle

1

Ja, es ist falsch: Ein Akzeptor für eine Sprache darf keine Wörter außer denen in der Sprache akzeptieren.

Reinierpost

Bitte posten Sie keine Anschlussfragen als Antworten. Verwenden Sie Kommentare (nachdem Sie dem System bewiesen haben, dass Sie vertrauenswürdig sind) oder erstellen Sie einen neuen Beitrag, wenn sich die neue Frage erheblich unterscheidet (hier nicht der Fall).

Raphael

-4

In diesem Fall konnte A nicht Turing-erkennbar sein. Nehmen Sie dies als Beispiel:

Sprache B ist die Vereinigung einer Sprache tr (C) und einer Sprache nicht tr (A). Sie können eine Turingmaschine erstellen, die B erkennt. A ist nicht tr und A ⊆ B.

ist das richtig? Ich weiß nicht, ob es so ist.

Philip A.
quelle

3

C \in R E

$C\in RE$

A \notin R E

$A\notin RE$

C = \emptyset

$C=\emptyset$

A

$A$

B = A \cup C

$B=A \cup C$

Die Subsprache ist nicht Turing-erkennbar, oder könnte es sein?

Antworten: