Рассмотрим язык {1^n| n=k^2, k натуральное} над алфавитом {0;1} Опишите машину тьюринга, которая за полиномиальное время распознает язык.

задан 11 Сен 16:19

Машина перебирает случаи k=1,2,..., рисует где-то k палочек, возводит это число в квадрат (это подпрограмма), и сравнивает результат c n. Если произошло совпадение, то ответ "да". Если оно не произошло вплоть до n-го шага, ответ "нет". Ясно, что этапов здесь не более n, а на каждом этапе проводится вычисление полиномиальной от n сложности (возведение в квадрат).

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

Ваш ответ

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

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

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

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

отмечен:

×124

задан
11 Сен 16:19

показан
29 раз

обновлен
11 Сен 16:22

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

по почте:

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

по RSS:

Ответы

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

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