Субязык не узнаваем по Тьюрингу или это может быть?

10

Пусть A и B - языки с A ⊆ B, а B распознаваема по Тьюрингу. Может ли быть не узнаваемым по Тьюрингу? Если да, то есть ли пример?

computability GFE
источник

18

Это то, что смущает многих студентов. Суть здесь в том, что наличие подмножества другого языка мало что говорит об их сложности вычислений. Вы всегда можете рассмотреть тривиальный язык и и любой другой язык находится между ними по множеству включений. $\emptyset$ $\Sigma^*$

Поэтому просто знание того, что язык содержит или содержится в простом для вычисления языке, ничего не говорит о сложности его вычисления.

Кава
источник

Но я не могу найти какой-либо язык подмножеств Σ ∗, который не распознается по Тьюрингу.

GFE

3

@ Вильгельм, возьми любой язык, который не распознается по Тьюрингу, и он будет работать.

Каве

Понятно, поэтому я могу использовать проблему остановки, чтобы доказать, что такой язык существует.

GFE

@ Вильгельм, да. :)

Kaveh

1

$X$ $X^c$ $X^c$ $\Sigma^*$ $A \subseteq B$ $B$ $A$

шлифовальный
источник

Σ^{*}

$\Sigma^*$

Σ^{*}

$\Sigma^*$

X

$X$

X \subset Σ^{*}

$X \subset \Sigma^*$

-3

Ваше обсуждение успешно смутило меня :(

"Может ли быть не узнаваемым по Тьюрингу?"

Я чувствую, что А всегда узнаваем по Тьюрингу . Вот мое мышление,

Поскольку B является распознаваемым по Тьюрингу => Существует некоторый TM, который принимает все слова языка B => Существует TM, который принимает (все слова языка A + некоторые другие слова) => Существует TM, который принимает все слова языка A => A распознаваема по Тьюрингу.

Это неправильно? Может ли быть случай, когда A не-TRL, а B - TRL. Пожалуйста, помогите

bongubj
источник

1

Да, это неправильно: акцептор языка не должен принимать никаких слов, кроме слов в языке.

reinierpost

Пожалуйста, не размещайте последующие вопросы в качестве ответов. Используйте комментарии (после того, как вы докажете системе, что вы заслуживаете доверия) или создайте новую публикацию, если новый вопрос значительно отличается (здесь это не так).

Рафаэль

-4

В этом случае А не может быть узнаваемым по Тьюрингу. Возьмите это как пример:

язык B - это объединение языка tr (C) и языка не tr (A). Вы можете создать машину Тьюринга, которая распознает B. A не TR и A ⊆ B.

это правильно? я не знаю, если это так .. =)

Филипп А.
источник

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$

Субязык не узнаваем по Тьюрингу или это может быть?

Ответы: