Необходимо построить машину Тьюринга_Поста, вычисляющую функцию f (x,y,z)=max{x+y,z} и проиллюстрировать ee на примере слова A=1*111*111.
Начальное машинное слово m=q1a01^na01^ma0 - это пара чисел (n,m). После вычислений число n+m это машинное слово q0a(01^(n+m))a0.
A как сюда привязать максимум?
машина Тьюринга
машина Тьюринга
Последний раз редактировалось NatNiM 30 ноя 2019, 09:10, всего редактировалось 1 раз.
Причина: test
Причина: test
машина Тьюринга
Для поиска максимума можно использовать следующую машину Тьюринга:
Алфавит: * (пусто), 1, !, %.
Состояния: 1, 2,...,7.
B верхней строке таблицы текущий символ на ленте. B левом столбце - состояния. Каждая ячейка содержит 3 элемента:
1) на что заменить текущий символ
2) куда двигать головку (L - влево, R - вправо, N - остаться на месте)
3) в какое состояние перейти.
K примеру, входное слово 11*1111 будет преобразовываться так:
!1*1111
!1*%111
!!*%%11
*!*%%11
***%%11
***1111
Алфавит: * (пусто), 1, !, %.
Состояния: 1, 2,...,7.
B верхней строке таблицы текущий символ на ленте. B левом столбце - состояния. Каждая ячейка содержит 3 элемента:
1) на что заменить текущий символ
2) куда двигать головку (L - влево, R - вправо, N - остаться на месте)
3) в какое состояние перейти.
K примеру, входное слово 11*1111 будет преобразовываться так:
!1*1111
!1*%111
!!*%%11
*!*%%11
***%%11
***1111
Последний раз редактировалось Dm13 30 ноя 2019, 09:10, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 26 гостей