![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Тема 8.2 Машины Тьюринга.
Будем считать, что машина Тьюринга имеет ленту (магнитную, печатную и т.д.), которая бесконечна в обе стороны и разбита на участки называемые ячейками. Имеется считывающее устройство и существует механизм, который передвигает это устройство, как вправо, так и влево. Дан конечный алфавит А, следующего вида:
В каждую ячейку машина может печатать только один знак. Алфавит А называется внешним алфавитом машины. Считаем, что машина может находиться в одном из конечного числа состояний: В каждый момент времени t считывающее устройство видит только одну ячейку и при этом на ленте конечное число знаков (не пустых символов). Если в момент времени t машина находиться в состоянии Участок между непустыми символами Машина делает 4 операции: 1. переход от состояния 2. смена обозреваемого значка: 3. считывающее устройство передвигается на одну ячейку вправо (П) 4. считывающее устройство передвигается на одну ячейку влево (Л) Работа машины заключается в следующей последовательности шагов: 1. смена обозреваемого значка и смена состояния: 2. машина меняет состояние и двигается на одну ячейку вправо: 3. машина меняет состояние и двигается на одну ячейку влево: Выполнение этих шагов осуществляется под действием команды (приказы), которые зависят от настоящей ситуации. Множество приказов обозначается:
|