Формализация машины Тьюринга
sergey shishkinНа данном этапе работы важным является формирование метода формальной записи конкретного алгоритма в разработанной модели. Приведем далее образец такой записи. Для этого опишем формализацию "машины Тьюринга" в виде контролируемого близостью конструкционного алгоритма.
Абстрактная вычислительная машина Тьюринга состоит из двух основных элементов:
- ленты — бесконечной последовательности ячеек, в каждой из которых может быть записан символ конечного алфавита.
- управляющего устройства, способного взаимодействовать с одной ячейкой и перемещаться к левой и правой соседней ячейке, при этом способ взаимодействия определяется состоянием устройства, и это состояние выбирается из конечного множества состояний.
Взаимодействие между ячейкой и управляющим устройством обусловлено:
- текущим состоянием устройства;
- символом, хранимым в текущей ячейке;
- сопоставленным с символом ячейки текущим правилом текущего состояния.
Результаты взаимодействия зависят от текущего правила, заданного текущим состоянием, и возможно сочетание следующих результатов:
- изменение символа хранимого в ячейке;
- возможно относительное перемещение ленты и управляющего устройства до его совмещения с правой или левой соседней ячейкой (относительно текущего расположения);
- переход управляющего устройства в новое состояние;
- завершение работы в случае перехода устройством в состояние, помеченное терминальным.
Ключевым, но не единственным в описании является взаимодействие содержимого текущей ячейки и текущего правила в текущем состоянии.
Формализуем данное текстовое описание машины Тьюринга в виде макро-алгоритма одним из многих возможных способов.