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