Машина Тьюринга:Унарное сложение

Материал из DISCOPAL
Версия от 09:55, 4 августа 2008; WikiSysop (обсуждение) (1 версия)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Приведем пример машины Тьюринга, выполняющей унарное сложение двух операндов. Операнды представляются в унарной системе, т. к. целое неотрицательное число 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')))  # конец.
 }
}  

Графовое представление МТ

[svg]

Примеры выполнения МТ

«1» + «1»

/bin/bash: inkscape: command not found /bin/bash: inkscape: command not found

«111» + «1»

/bin/bash: inkscape: command not found /bin/bash: inkscape: command not found


«11» + «111»

/bin/bash: inkscape: command not found /bin/bash: inkscape: command not found

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.