|
Персональные инструменты |
|||
|
|
Машина Тьюринга:Унарное сложениеМатериал из CustisWikiЭто снимок страницы. Он включает старые, но не удалённые версии шаблонов и изображений. Приведем пример машины Тьюринга, выполняющей унарное сложение двух операндов. Операнды представляются в унарной системе, т. к. целое неотрицательное число 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»Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации. |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||