|
Помогите, пожалуйста, составить машину Тьюринга, которая вычисляет предикат P(x), где x - четное число. То есть если х - четное, то предикат - Истина. Иначе - ложь. Предполагаю, внешним алфавитом может быть набор {1, 0, *, ^}, где ^ - пустой символ. Внутренним алфавитом будут значения истина И, и ложь Л задан 27 Май '12 4:12 
carapuz |
|
Еще Вариант решения - предпочтительнее предыдущего: Внешний алфавит $%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 
chipnddail Я не специалист в теории алгоритмов. А что такое "единичная система счисления"?
(28 Май '12 11:02)
DocentI
@DocentI, Исправил, в унарной системе счисления - с основанием 1.
(28 Май '12 11:16)
chipnddail
Думаете, мне стало понятней? Это означает, что число представлено как сумма единичек? Потому что позиционной системы счисления с основанием 1 быть не может.
(28 Май '12 11:32)
DocentI
|