Машина Тьюринга

Схематическая иллюстрация работы машины Тьюринга.

Машина Тьюринга - математическое понятие, введенное для формального уточнения интуитивного понятия алгоритма. Названа в честь английского математика Алана Тьюринга, который предложил это понятие в 1936. Аналогичную конструкцию машины впоследствии и независимо от Тьюринга ввел американский математик Эмиль Пост. [1]

Основная идея, лежащая в основе машины Тьюринга, очень проста. Машина Тьюринга - это абстрактная машина (автомат), работающий с лентой, состоящей из отдельных ячеек, в которых записаны символы. Машина также головку записи и чтения символов из ячеек и которая может двигаться вдоль ленты. На каждом шаге машина считывает символ из ячейки, на которую указывает головка и, на основе считанного символа и внутреннего состояния, делается следующий шаг. При этом, машина может изменить свое состояние, записать другой символ в ячейку или передвинуть головку на одну ячейку влево или вправо. [2]


1. История

Формальные определения алгоритма появились в тридцатых-сороковых годах 20 века. Одним из первых было определение английского математика Алана Тьюринга, который в 1936 году описал схему некоторой гипотетической (абстрактной) машины и предложил называть алгоритмами то, что умеет делать такая машина. При этом определении, если что-то не может быть сделано машиной Тьюринга, это уже не метод. Иначе говоря, Тьюринг формализовал правила выполнения действий с помощью описания работы некоторой конструкции.


2. Определение

У каждой машины Тьюринга является лента, потенциально бесконечная в обе стороны. Есть конечное множество символов ленты S 0,..., S n, что называется алфавитом машины. В каждый момент времени каждая ячейка может быть занята не более одним символом. Машина имеет некоторую конечное множество внутренних состояний q 0, q 1,..., q n. В каждый данный момент времени машина находится только в одном из этих состояний.

Наконец, есть головка, которая в каждый данный момент времени находится на одной из ячеек ленты. Машина действует не непрерывно, а лишь в дискретные моменты времени. Если в какой-то момент t головка воспринимает ячейку (т.е. находится на ячейке), содержащий символ S i, и машина находится во внутреннем состоянии q j, то действие машины определена одной из четырех действий:

  1. головка затирает символ S i, и записывает в той же ячейке новый символ S k,
  2. головка передвигается в соседнюю левую ячейку,
  3. головка передвигается в соседнюю правую ячейку,
  4. машина останавливается.

В случаях (1) - (3) машина переходит в новое внутреннее состояние q r, и готова снова к действию в следующий момент t + 1. Предположим, что символ S 0 представляет пустую ячейку, и следовательно, головка всегда воспринимает некий символ.

Первые три из возможных действий машины могут быть описаны соответственно такими благоустроенными четверками, называемых командами:

  1. S_i q_j \ to S_k q_r S
  2. S_i q_j \ to S_k q_r L
  3. S_i q_j \ to S_k q_r R

Здесь первые два символа - это соответственно внутренние состояния машины и воспринят символ, следующие три определяют действие машины (запись головкой символа S k, или перемещение головки на одну ячейку влево или перемещение головки на одну ячейку вправо) и новое состояние машины. Если лента вложена в машину Тьюринга, головка машины установлена ​​на одну из ячеек ленты и машина приведена в один из своих внутренних состояний, то машина начинает оперировать на ленте: ее головка пишет и стирает символы и передвигается из одной ячейки в другую. Если при этом машина когда-то останавливается, то лента, которая расположена в ней в данный момент, называется результатом применения машины к данной ленты.

Несмотря на свой простое устройство, машина Тьюринга может выполнять сложные преобразования слов. Сначала, когда лента содержит входное слово, автомат находится против некоторой из ячеек и в каком состоянии. В зависимости от выбора начальной ячейки, образуются различные результаты работы машины Тьюринга. В процессе своей работы машина Тьюринга будет будто перепрыгивать из одной ячейки программы на другую, согласно информации на ленте и указаниями в командах программы, пока не дойдет до команды, которая переведет автомат в конечное состояние.


3. Возможности машины Тьюринга

Богатство возможностей конструкции Тьюринга проявляется в том, что если какие-то алгоритмы A и B реализуются машинами Тьюринга, то можно строить программы машин Тьюринга, которые реализуют композиции алгоритмов A и B, например, выполнить A, затем выполнить B или выполнить A. Если в результате образовалось слово так, то выполнить B. В противном случае не выполнять B или выполнять поочередно A, B, пока B не даст ответ нет.

В интуитивном смысле такие композиции являются алгоритмами. Поэтому их реализация с помощью машины Тьюринга служит одним из средств обоснования универсальности конструкции Тьюринга.

Реализуемость таких композиций приходится в общем виде, независимо от особенностей конкретных алгоритмов A и B. Доказательство заключается в том, что указывается способ построения из программ A и B программы нужной композиции. Пусть, например, нужно построить машину A \ cdot B , Эквивалентную последовательному выполнению алгоритмов A и B. Пока выполняется алгоритм A, в программе A \ cdot B работает часть A без учета части B. Когда алгоритм A дойдет до конца, то вместо остановки произойдет переход в первое состояние части B, и затем часть B будет работать обычным образом, как части A и не было.

Аналогично конструируют и другие композиции машин Тьюринга; каждый раз строятся общие правила: что на что менять в исходных программах.

Описывая различные алгоритмы для машин Тьюринга и утверждая реализуемость всевозможных композиций алгоритмов, Тьюринг убедительно показал разнообразие возможностей предложенной им конструкции, что позволило ему выступить с таким тезисом:

Всякий алгоритм может быть реализован соответствующей машиной Тьюринга.

Это основная гипотеза теории алгоритмов в форме Тьюринга. Одновременно этот тезис является формальным определением алгоритма. Благодаря ей можно доказывать существование или несуществование алгоритмов, создавая соответствующие машины Тьюринга или доказывая невозможность их построения. Благодаря этому появляется общий подход к поиску алгоритмических решений.

Если поиск решения наталкивается на препятствие, то можно использовать это препятствие для доказательства невозможности решения, опираясь на основную гипотезу теории алгоритмов. Если же при доказательстве невозможности возникает своя препятствие, то она может помочь продвинуться в поиске решения, хотя бы частично устранив старую препятствие. Так, по очереди пытаясь доказать то существование, то отсутствие решения, можно постепенно приблизиться к пониманию сути поставленной задачи.

Доказать тезис Тьюринга нельзя, так как в его формулировке не определено понятие всякий алгоритм, т.е. левая часть тождества. Его можно только обосновать, представляя различные известные алгоритмы в виде машин Тьюринга. Дополнительное обоснование этого тезиса состоит в том, что позже было предложено еще несколько общих определений понятия алгоритма и каждый раз удавалось доказать, что, хотя новые алгоритмические схемы и выглядят иначе, они в действительности эквивалентны машинам Тьюринга:

все, что реализовано в одной из этих конструкций, можно сделать и в других

Эти утверждения доказываются строго, потому что в них речь идет уже о тождестве формальных схем.


4. Источники информации

  1. Энциклопедия кибернетики, т. 2, с. 444-446.
  2. Good Math, Bad Math, Basics: The Turing Machine (with an interpreter!), 9 февраля 2007.

Литература

  • Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. - М. : Мир, 1982. - 416 с.
  • Пенроуз Р. Новый ум короля. - М. : URSS, 2011. - 400 с.
  • Хопкрофта Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. - М. : Вильямс, 2007. - 528 с.
  • Эббинхауз Г.-Д., Якобс К., Ман Ф.-К., Хермес Г. Машины Тьюринга и рекурсивные функции. - М. : Мир, 1972. - 264 с.

См.. также

Ссылка



Сигма Это незавершенная статья математики.
Вы можете помочь проекту, исправив и дополнив ее.