Персональные инструменты
 

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

Материал из CustisWiki

Версия от 07:54, 6 марта 2007; BenderBot (обсуждение | вклад) (реплицировано из внутренней CustisWiki)

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

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

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

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

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

[svg]

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

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

«111»

«1111»


Любые правки этой статьи будут перезаписаны при следующем сеансе репликации. Если у вас есть серьезное замечание по тексту статьи, запишите его в раздел «discussion».

Репликация: База Знаний «Заказных Информ Систем» → «Машина Тьюринга:Распознавание четности»