КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Тема 8.2 Машины Тьюринга
Будем считать, что машина Тьюринга имеет ленту (магнитную, печатную и т.д.), которая бесконечна в обе стороны и разбита на участки называемые ячейками. Имеется считывающее устройство и существует механизм, который передвигает это устройство, как вправо, так и влево. Дан конечный алфавит А, следующего вида: , где - пустой знак В каждую ячейку машина может печатать только один знак. Алфавит А называется внешним алфавитом машины. Считаем, что машина может находиться в одном из конечного числа состояний: . Состояние Q – называется внутренним алфавитом машины, где - пассивное состояние машины, а все остальные состояния называются активными состояниями машины. В каждый момент времени t считывающее устройство видит только одну ячейку и при этом на ленте конечное число знаков (не пустых символов). Если в момент времени t машина находиться в состоянии и обозревает ячейку , то называется локальной информацией машины. Участок между непустыми символами - называется глобальной информацией машины. Машина делает 4 операции: 1. переход от состояния к состоянию - называется сменой состояния 2. смена обозреваемого значка: в 3. считывающее устройство передвигается на одну ячейку вправо (П) 4. считывающее устройство передвигается на одну ячейку влево (Л) Работа машины заключается в следующей последовательности шагов: 1. смена обозреваемого значка и смена состояния: ; 2. машина меняет состояние и двигается на одну ячейку вправо: ; 3. машина меняет состояние и двигается на одну ячейку влево: ; Выполнение этих шагов осуществляется под действием команды (приказы), которые зависят от настоящей ситуации. Множество приказов обозначается: и называется программой машины.
Дата добавления: 2014-01-04; Просмотров: 222; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |