Машина Тьюринга:Распознавание четности

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

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

#
# Распознавание четных строк (содержащих четное число "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»

---

Внимание! Данная статья выбрана для репликации во внешнюю базу знаний компании. Пожалуйста, не допускайте в этой статье публикацию конфиденциальной информации, ведения обсуждений в теле статьи, и более ответственно относитесь к качеству самой статьи — проверяйте орфографию, пишите по-русски, избегайте непроверенной вами информации.