|
Персональные инструменты |
![]() |
||
|
![]() |
![]() Машина Тьюринга:Унарное сложение — различия между версиямиМатериал из CustisWiki
Версия 20:16, 17 октября 2005Приведем пример машины Тьюринга, выполняющей унарное сложение двух операндов. Операнды представляются в унарной системе, т. к. целое неотрицательное число n представляется n+1 единицей. СодержаниеТабличное представление МТMT={ 'k':1, 'start': '1pass', 'stop': 'q', 'program': { #(Состояние, символы на лентах) -> (новое состояние, (действия по каждой ленте)) ('1pass', ('1')): ('1pass', (('1','R'))), # проходим первое число ('1pass', ('*')): ('2pass', (('1','R'))), # меняем разделитель ('2pass', ('1')): ('2pass', (('1','R'))), # проходим второе число ('2pass', ('*')): ('del1', (('*','L'))), # конец второго числа ('del1', ('1')): ('del2', (('*','L'))), # удаляем первую лишнюю 1 ('del2', ('1')): ('rewind',(('*','L'))), # удаляем вторую лишнюю 1 ('rewind',('1')): ('rewind',(('1','L'))), # перематываем к началу. ('rewind',('*')): ('q', (('*','R'))) # конец. } } Графовое представление МТ
Примеры выполнения МТ«1» + «1»«111» + «1»
«11» + «111»
Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion». Репликация: База Знаний «Заказных Информ Систем» → «Машина Тьюринга:Унарное сложение» |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |