Машина Тьюринга:Унарное сложение — различия между версиями

Версия 17:42, 5 марта 2007

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