O sub-idioma não é reconhecível por Turing, ou poderia ser?

10

Seja A e B idiomas com A ⊆ B, e B é reconhecível por Turing. A não pode ser reconhecido por Turing? Se sim, existe algum exemplo?

computability gfe
fonte

18

Isso é algo que confunde muitos estudantes. O ponto aqui é que ser subconjunto de outro idioma não implica muito em sua dificuldade de computação. Você sempre pode considerar o idioma trivial e e qualquer outro idioma está entre eles na inclusão do conjunto de caracteres. $\emptyset$ $\Sigma^*$

Portanto, apenas saber que uma linguagem contém ou está contida em uma linguagem fácil de calcular não diz nada sobre a dificuldade de calculá-la.

Kaveh
fonte

Mas não consigo encontrar nenhum idioma de subconjunto de ∗ que não seja reconhecível por Turing.

Gfe #

3

@Wilhelm, use qualquer idioma que não seja reconhecível por Turing e funcionará.

Kaveh

Entendo, para que eu possa usar o problema da parada para provar que existe uma linguagem assim.

Gfe #

@Wilhelm, sim. :)

Kaveh

1

Quando uma linguagem reconhecível por Turing não é decidível, isso implica que não é reconhecível co-Turing (em outras palavras: não é reconhecível). Como é um subconjunto perfeitamente válido de , isso suporta o fato de que, para um idioma que é reconhecível por Turing, pode muito bem não ser. $X$ $X^c$ $X^c$ $\Sigma^*$ $A \subseteq B$ $B$ $A$

Sander
fonte

Eu acho que a resposta de Kaveh é melhor e mais objetiva. Qualquer idioma é um subconjunto de e sabemos que é decidível e que existem idiomas arbitrariamente rígidos.

Σ^{*}

$\Sigma^*$

Σ^{*}

$\Sigma^*$

Pål GD

Foi o que tentei explicar, já que pode ser qualquer idioma, porque o é válido automaticamente. ;)

X

$X$

X \subset Σ^{*}

$X \subset \Sigma^*$

Sander,

-3

Sua discussão me confundiu com sucesso :(

"A não pode ser reconhecível por Turing?"

Sinto que A é sempre reconhecível por Turing . Aqui está o meu pensamento,

Como B é Turing reconhecível => Existe alguma TM que aceita todas as palavras da linguagem B => Existe uma TM que aceita (todas as palavras da linguagem A + algumas outras palavras) => Existe uma TM que aceita todas as palavras da linguagem A => A é Turing reconhecível.

Isso está errado? Pode haver algum caso em que A seja Não TRL enquanto B seja TRL. Por favor, ajude

bongubj
fonte

11

Sim, está errado: um aceitador de um idioma não deve aceitar nenhuma palavra, exceto as que estão no idioma.

reinierpost

Não poste perguntas de acompanhamento como respostas. Use comentários (depois de provar ao sistema que você é confiável) ou crie uma nova postagem se a nova pergunta for significativamente diferente (não é o caso aqui).

Raphael

-4

Nesse caso, A não poderia ser reconhecido por Turing. Tome isso como um exemplo:

o idioma B é a união de um idioma tr (C) e um idioma não tr (A). você pode criar uma máquina de turing que reconheça B. A não é tr e A ⊆ B.

Isso está certo? Eu não sei se é ... então .. =)

Philip A.
fonte

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$

O sub-idioma não é reconhecível por Turing, ou poderia ser?

Respostas: