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

Текущая версия на 09:55, 4 августа 2008

Приведем пример машины Тьюринга, распознающую четные входные строки (пустую строку и строки состоящие из четного числа единиц).

Табличное представление МТ

#
# Распознавание четных строк (содержащих четное число "1").
#
MT={
 'k':1, 
 'start': 'even',
 'stop': 'q',
 'program': {
 #(Состояние, символы на лентах) -> (новое состояние, (действия по каждой ленте))
  ('even', ('*')):    ('2ok',  (('*','L'))), 
  ('even', ('1')):    ('odd',  (('1','R'))), 
  ('odd',  ('1')):    ('even', (('1','R'))), 
  ('odd',  ('*')):    ('2bad', (('*','L'))), 
  ('2ok',  ('1')):    ('2ok',  (('*','L'))), 
  ('2ok',  ('*')):    ('q',    (('1',''))), 
  ('2bad', ('1')):    ('2bad', (('*','L'))), 
  ('2bad', ('*')):    ('q',    (('0',''))) 
 }
}  

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

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

Пустая строка

«111»

«1111»