Помогите, пожалуйста, составить машину Тьюринга, которая вычисляет предикат P(x), где x - четное число. То есть если х - четное, то предикат - Истина. Иначе - ложь. Предполагаю, внешним алфавитом может быть набор {1, 0, *, ^}, где ^ - пустой символ. Внутренним алфавитом будут значения истина И, и ложь Л

задан 27 Май '12 4:12

10|600 символов нужно символов осталось
0

Еще Вариант решения - предпочтительнее предыдущего:

Внешний алфавит $%A=\{1,T,F,B\}$% алфавит ленты; B - пустой символ.

Внутренний алфавит $%Q=\{STOP,q_1,q_2\}$% алфавит внутренних состояний.

$%M=\{L,R,H\}$%, перемещения головки влево, вправо и остановка. $$ 1q1->Bq2R\\ Bq1->TSTOPH\\ 1q2->Bq1R\\ Bq2->FSTOPH$$ Можно проверить в онлайн эмуляторе МТ.

ПОЯСНЕНИЯ

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

PS Предыдущий вариант решения заменил на новое - более правильное

ссылка

отвечен 28 Май '12 2:52

изменен 28 Май '12 11:16

Я не специалист в теории алгоритмов. А что такое "единичная система счисления"?

(28 Май '12 11:02) DocentI

@DocentI, Исправил, в унарной системе счисления - с основанием 1.

(28 Май '12 11:16) chipnddail

Думаете, мне стало понятней? Это означает, что число представлено как сумма единичек? Потому что позиционной системы счисления с основанием 1 быть не может.

(28 Май '12 11:32) DocentI
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,509

задан
27 Май '12 4:12

показан
2776 раз

обновлен
28 Май '12 11:32

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

по почте:

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

по RSS:

Ответы

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

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