 |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
Машина Тьюринга
|
|
Машина Тьюринга. Описание, способы задания, особенности программирования машин Тьюринга (МТ). Основные операции над МТ, доказательство теоремы о существовании универсальной МТ. Примеры.
Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического общества статью, где для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Эта работа наравне с работами Поста и Черча лежит в основе современной теории алгоритмов.
Предыстория её создания связана с формулировкой списка из 23 кардинальных проблем математики, представленного Давидом Гильбертом на II Международном Конгрессе математиков в Париже в 1900 году.
Характеристика, данная работе Тьюринга Джоном Хопкрофтом: «Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т.е. процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга». (с16)
Машина Тьюринга является расширением модели конечного автомата, расширением, включающим потенциально бесконечную память с возможностью перехода (движения) от обозреваемой в данный момент ячейки к ее левому или правому соседу.
Неформально, машина Тьюринга (далее МТ) представляет собой автомат с конечным числом состояний и неограниченной памятью, представленной бесконечной лентой. Лента поделена на бесконечное число ячеек, и на ней выделена стартовая ячейка.
В каждой ячейке ленты может быть записан только один символ из некоторого конечного алфавита, где также предусмотрен символ для обозначения пустой ячейки.
С лентой взаимодействует головка чтения-записи, которой управляет «управляющее устройство» МТ — автомат с конечным множеством состояний.
Имеется выделенное стартовое состояние и состояние завершения.
Перед запуском МТ находится в начальном состоянии, а головка позиционируется на пустой ячейке ленты.
На каждом шаге головка считывает информацию из текущей ячейки, и посылают ее управляющему устройству МТ. В зависимости от этих символов и собственного состояния, управляющий устройство может производить следующие операции:
· записывать символ алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой);
· передвигать головку на одну ячейку влево, вправо или остается на месте;
· менять свое внутреннее состояние; (с18)
Рис.2 Машина Тьюринга
Формально машина Тьюринга может быть описана следующим образом (с19):
· конечное множество состояний – Q = { q0, q1,..., qn}, в которых может находиться машина Тьюринга, называемое внутренним алфавитом;
· конечное множество символов ленты – А = {a0, а1,...,аt} называемое внешним алфавитом;
· функция 
(функция переходов или программа), которая задает отображение пары из декартова произведения Q x А (машина находится в состоянии 
и обозревает символ ak) в тройку декартова произведения Q х А х {L,R,E} (машина переходит в состояние qj, заменяет символ ak на символ am и передвигается влево, вправо на один символ ленты или остается на месте) – Q x А-->Q х А х {L,R,E}: 
. Предполагается, что для каждой пары qiak, i=1,…n, k=0,…t имеется точно одна команда. Множество этих команд называется программой и в программе имеется n(t+1) команд;
· один символ 
(пустой);
· подмножество 
определяется как подмножество входных символов ленты, причем 
; т.е. в начальный момент на ленте имеется конечное число непустых символов.
· одно из состояний – 
является начальным состоянием машины, а 
заключительным.
Обязательно требование детерминизма, т.е. не должно быть команд с одинаковой левой частью.
Должна быть команда, в правой части которой есть заключительное состояние.
Для МТ ниоткуда не следует, что начав работать из начального состояния, она когда-нибудь выйдет на заключительное состояние. Вводить это требование не получается, т.к. по описанию нельзя заранее предугадать эту ситуацию.
Способы задания МТ:
Список команд (с20)
Таблица переходов (с20)
Граф переходов. (с21)
Таблица переходов
МТ можно описать в виде таблицы, где строки соответствуют состояниям, а столбцы символам внешнего алфавита. Данное представление автоматически обеспечивает детерминизм и удобно тем, что видно, что задали все возможные команды, т.е. для любой левой части есть правая.
| a0 | a1 | |
| q1 | q2a1E | q1a1R |
| q2 | q0a0R | q2a1L |
| q0 | … | … |
Дата публикования: 2015-01-10; Прочитано: 1256 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!
