Приведите пример языка L, нележащего в классе P, такого, что язык 𝐿* в классе P лежит

задан 29 Фев 0:20

Возьмите какой-нибудь пример языка не из P (например, неразрешимого), и добавьте к нему однобуквенные слова.

(29 Фев 5:32) falcao

@falcao как понимать однобуквенные слова в случае языка stop(описание машин Тьюринга и слова для них), например? Какой пример вообще нужен?

(29 Фев 19:26) ntm

@ntm: специфика языка тут особо не важна. Важно знать, что существуют неразрешимые языки. Они состоят из каких-то слов над каким-то алфавитом. Например, над {0,1}. Неразрешимость означает, что по слову мы не умеем алгоритмически узнавать, принадлежит ли слово этому языку. Если мы добавим к нему слова 0 и 1, то язык останется алгоритмически неразрешимым. Но при этом L* станет равно языку всех слов, а такой язык лежит в классе P.

(29 Фев 19:41) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×71

задан
29 Фев 0:20

показан
101 раз

обновлен
29 Фев 19:41

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru