«А. Тьюринг и машина Тьюринга» Яъхя Шакиб А. М
жүктеу/скачать 42.5 Kb.
|
- Бұл бет үшін навигация:
- Машины Тьюринга
Тема: «А. Тьюринг и машина Тьюринга»Выполнил: Яъхя Шакиб А. М. Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического общества статью «О вычислимых числах в приложении к проблеме разрешения», которая наравне с работами Поста и Черча лежит в основе современной теории алгоритмов. Предыстория создания этой работы связана с формулировкой Давидом Гильбертом на Международном математическом конгрессе в Париже в 1900 году неразрешенных математических проблем. Одной из них была задача доказательства непротиворечивости системы аксиом обычной арифметики, которую Гильберт в дальнейшем уточнил как «проблему разрешимости» - нахождение общего метода, для определения выполнимости данного высказывания на языке формальной логики. Статья Тьюринга как раз и давала ответ на эту проблему - вторая проблема Гильберта оказалась неразрешимой. Но значение статьи Тьюринга выходило далеко за рамки той задачи, по поводу которой она была написана. Приведем характеристику этой работы, принадлежащую Джону Хопкрофту: «Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т.е. процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга». Машина Тьюринга является расширением модели конечного автомата, расширением, включающим потенциально бесконечную память с возможностью перехода (движения) от обозреваемой в данный момент ячейки к ее левому или правому соседу. Формально машина Тьюринга может быть описана следующим образом: Пусть заданы: конечное множество состояний – Q, в которых может находиться машина Тьюринга; конечное множество символов ленты – Г; функция (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии и обозревает символ ) в тройку декартова произведения Q х Г х {L,R} (машина переходит в состояние , заменяет символ на символ и передвигается влево или вправо на один символ ленты) – Q x Г-->Q х Г х {L,R} один символ из Г-->е (пустой); подмножество є Г --> определяется как подмножество входных символов ленты, причем е є (Г-); одно из состояний – є Q является начальным состоянием машины. Решаемая проблема задается путем записи конечного количества символов из множества є Г – Si є на ленту:e S1 S2 S3 S4 ......... Sn e после чего машина переводится в начальное состояние и головка устанавливается у самого левого непустого символа – , после чего в соответствии с указанной функцией переходов (, )-->(,, L или R) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов.
произвольное конечное множество A (алфавит); его элементы называются символами; некоторый выделенный символ a0 A (пробел, или пустой символ); конечное множество S, называемое множеством состояний; некоторое выделенное состояние s0 S, называемое начальным; таблицу переходов, которая определяет поведение машины в зависимости от состояния и текущего символа (см. ниже); некоторое подмножество F S, элементы которого называются заключительными состояниями (попав в такое состояние, машина останавливается). Таблица переходов устроена следующим образом: для каждой пары указана тройка . Здесь сдвиг одно из чисел -1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа S x A S x A x {-1,0,1}, определенная на тех парах, в которых состояние не является заключительным. Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация, складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z A), текущей позиции головки (некоторое целое число) и текущего состояния машины (элемент S). Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте. При этом, если новое состояние является одним из заключительных, работа машины заканчивается. Остается договориться, как мы подаем информацию на вход машины и что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово, которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1). Таким образом, любая машина Тьюринга задает некоторую частичную функцию на двоичных словах. Все такие функции естественно назвать вычислимыми на машинах Тьюринга.
жүктеу/скачать 42.5 Kb. Достарыңызбен бөлісу:
|