Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


Машины Тьюринга и тезис

Машины Тьюринга и тезис


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


Определение машины Тьюринга


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


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


Опишем теперь машину Тьюринга \Theta более тщательно. Машина \Theta располагает конечным числом знаков (символов, букв), образующих так называемый внешний алфавит A=\{a_0,a_1,\ldots,a_n\}. В каждую ячейку обозреваемой ленты в каждый дискретный момент времени может быть записан только один символ из алфавита A. Ради единообразия удобно считать, что среди букв внешнего алфавита A имеется "пустая буква", и именно она записана в пустую ячейку ленты. Условимся, что "пустой буквой" или символом пустой ячейки является буква a_0. Лента предполагается неограниченной в обе стороны, но в каждый момент времени на ней записано конечное число непустых букв.


Далее, в каждый момент времени машина \Theta способна находиться в одном состоянии из конечного числа внутренних состояний, совокупность которых Q=\{q_0,q_1,\ldots,q_m\}. Среди состояний выделяются два — начальное q_1 и заключительное (или состояние остановки) q_0. Находясь в состоянии q_1 машина начинает работать. Попав в состояние q_0, машина останавливается.


Работа машины \Theta определяется программой (функциональной схемой). Программа состоит из команд. Каждая команда T(i,j) (i=1,2,\ldots,m;\, j=0,1,\ldots,n) представляет собой выражение одного из следующих видов:


q_ia_j\to q_ka_lC;\quad q_ia_j\to q_ka_l\Pi;\quad q_ia_j\to q_ka_lL,
(32.1)

где 0 \leqslant k \leqslant m,~ 0 \leqslant l \leqslant n. В выражениях первого вида символ C будем часто опускать.


Как же работает машина Тьюринга? Находясь в какой-либо момент времени в незаключительном состоянии (т. е. в состоянии, отличном от q_0), машина совершает шаг, который полностью определяется ее текущим состоянием q_i и символом a_j, воспринимаемым ею в данный момент на ленте. При этом содержание шага регламентировано соответствующей командой T(i,j)\colon q_ia_j\to q_ka_iX, где X\in\{C,\Pi,L\}. Шаг заключается в том, что:


1) содержимое a_j обозреваемой на ленте ячейки стирается и на его место записывается символ a_i (который может совпадать с a_j);


2) машина переходит в новое состояние q_k (оно также может совпадать с предыдущим состоянием q_i);


3) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если X=\Pi, или к обозрению следующей левой ячейки, если X=L, или же продолжает обозревать ту же ячейку ленты, если X=C.


В следующий момент времени (если q_k\ne q_0) машина делает шаг, регламентированный командой T(k,l)\colon q_ka_i\to q_ra_sX и т.д.


Поскольку работа машины, по условию, полностью определяется ее состоянием q_i в данный момент и содержимым a_j обозреваемой в этот момент ячейки, то для каждых q_i и a_j~(i=1,2,\ldots,m;\, j=0,1,\ldots,n) программа машины должна содержать одну и только одну команду, начинающуюся символами q_ia_j. Поэтому программа машины Тьюринга с внешним алфавитом A=\{a_0,a_1,\ldots,a_n\} и алфавитом внутренних состояний Q=\{q_0,q_1,\ldots,q_m\} содержит m(n+1) команд.


Словом в алфавите A или в алфавите Q, или в алфавите A\cup Q называется любая последовательность букв соответствующего алфавита. Под k-й конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-то шага (или слово в алфавите A, записанное на ленту к началу k-ro шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное.


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


Будем говорить, что непустое слово а в алфавите A\setminus\{a_0\}= \{a_1,\ldots,a_n\} воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю справа ячейку из тех, в которых записано слово \alpha. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q_1 (соответственно в состоянии остановки q_0). Наконец, будем говорить, что слово \alpha перерабатывается машиной в слово \beta, если от слова \alpha, воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову \beta, воспринимаемому в положении остановки.




Применение машин Тьюринга к словам


Проиллюстрируем на примерах все введенные понятия, связанные с машинами Тьюринга.


Пример 32.1. Дана машина Тьюринга с внешним алфавитом A=\{0;1\} (здесь 0 — символ пустой ячейки), алфавитом внутренних состояний Q=\{q_0,q_1,q_2\} и со следующей функциональной схемой (программой):


q_10\to q_2o\Pi;\quad q_20\to q_01;\quad q_11\to q_11\Pi;\quad q_21\to q_21\Pi.

Посмотрим, в какое слово переработает эта машина слово 101, исходя из стандартного начального положения. Будем последовательно выписывать конфигурации машины при переработке ею этого слова. Имеем стандартное начальное положение:


\begin{array}{cc} \begin{matrix}{}\\(1)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\,~~ q_1\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&0&1&\phantom{1}&\phantom{1}&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}

На первом шаге действует команда: q_11\to q_11\Pi. В результате на машине создается следующая конфигурация:


\begin{array}{cc} \begin{matrix}{}\\(2)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad~ q_1\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&0&1&0&\phantom{1}&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}

На втором шаге действует команда: q_10\to q_20\Pi и на машине создается конфигурация:


\begin{array}{cc} \begin{matrix}{}\\(3)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad q_2\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&0&1&0&0&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}

Наконец, третий шаг обусловлен командой: q_20\to q_01. В результате него создается конфигурация:


\begin{array}{cc} \begin{matrix}{}\\(4)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad q_0\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&0&1&0&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}

Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q_0.


Таким образом, исходное слово 101 переработано машиной в слово 10101.


Полученную последовательность конфигураций можно записать более коротким способом. Конфигурация (1) записывается в виде следующего слова в алфавите A\cup Q\colon 10q_11 (содержимое обозреваемой ячейки записано справа от состояния, в котором находится в данный момент машина). Далее, конфигурация (2) записывается так: 101q_10, конфигурация (3) — 1010q_20 и, наконец, (4) — 1010q_01. Вся последовательность записывается так:


10q_11 \Rightarrow 101q_10 \Rightarrow 1010q_20 \Rightarrow 1010q_01.

Приведем последовательность конфигураций при переработке этой машиной слова 11011, исходя из начального положения, при котором в состоянии q_1 обозревается крайняя левая ячейка, в которой содержится символ этого слова (самостоятельно проанализируйте каждый шаг работы машины, указывая, какая команда обусловила его):


\begin{aligned}&\begin{array}{cc} \begin{matrix}{}\\(1)\end{matrix}&\qquad \begin{aligned}&\qquad\quad\;~ q_1\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(2)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\quad q_1\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(3)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\,~~ q_1\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(4)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\; q_2\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(5)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad q_2\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&\phantom{1}&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(6)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad\quad\;~ q_2\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&0&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\\ &\begin{array}{cc} \begin{matrix}{}\\(7)\end{matrix}&\qquad \begin{aligned}&\qquad\qquad\qquad\qquad\qquad\quad\;~ q_2\\ &\begin{array}{c|c|c|c|c|c|c|c|c}\hline \phantom{1}&\phantom{1}&1&1&0&1&1&1&\phantom{1} \\\hline \end{array} \end{aligned} \end{array}\end{aligned}

Более короткая запись этой последовательности конфигураций, те. процесса работы машины, будет


q_111011 \Rightarrow 1q_11011 \Rightarrow 11q_1011 \Rightarrow 110q_211 \Rightarrow 1101q_21 \Rightarrow 11011 q_20 \Rightarrow 11011q_01.

Таким образом, слово 11011 переработано машиной в слово 110111.


Пример 32.2. Машина Тьюринга задается внешним алфавитом A= \{0,1,\ast\} (как и в предыдущем примере 0 — символ пустой ячейки), алфавитом внутренних состояний Q=\{q_0,q_1,q_2,q_3\} и программой:
\begin{gathered}q_10\to q_10L,~ q_20\to q_31\Pi,~ q_30\to q_10L,~ q_11\to q_20L,~ q_21\to q_21L,\\ q_31\to q_31\Pi,~ q_1\ast\to q_00,~ q_2\ast\to q_2\ast L,~ q_3\ast\to q_3\ast\Pi. \end{gathered}

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


\begin{array}{|c|c|c|c|}\hline A \setminus Q & q_1& q_2& q_3\\\hline 0& q_10L& q_11\Pi& q_10L\\ 1& q_20L& q_21L& q_31\Pi\\ \ast& q_00& q_2\ast L& q_3\ast\Pi\\\hline \end{array}

Чтобы определить по таблице, что будет делать машина, находясь, например, в состоянии q_2 и наблюдая в обозреваемой ячейке символ 1, нужно найти в таблице клетку, находящуюся на пересечении столбца q_2 и строки, содержащей 1. В этой клетке записано q_21L. Это означает, что на следующем шаге машина останется в прежнем состоянии q_2, сохранит содержимое обозреваемой ячейки 1 и перейдет к обозрению следующей левой ячейки на ленте.


Применим эту машину к слову 11\ast11. Вот последовательность конфигураций, возникающих в процессе работы машины (исходная конфигурация — стандартная начальная):


\begin{aligned} 11*1q_11 &\Rightarrow 11*q_210 \Rightarrow 11q_2*10 \Rightarrow 1q_21*10 \Rightarrow q_211*10 \Rightarrow q_2011*10 \Rightarrow \\ & \Rightarrow q_311*10 \Rightarrow 11q_31*10 \Rightarrow 111q_3*10 \Rightarrow 111*q_310 \Rightarrow 111*1q_30 \Rightarrow \\ & \Rightarrow 111*q_110 \Rightarrow 111q_2*00 \Rightarrow 11q_21*0 \Rightarrow 1q_211*0 \Rightarrow q_2111*0 \Rightarrow \\ & \Rightarrow q_20111*0 \Rightarrow 1q_3111*0 \Rightarrow 11q_311*0 \Rightarrow 111q_31*0 \Rightarrow 1111q_3*0 \Rightarrow \\ & \Rightarrow 1111*q_30 \Rightarrow 1111q_1*0 \Rightarrow 1111q_000. \end{aligned}

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


\begin{gathered}11*q_11 \Rightarrow 111q_00; \qquad 111q_11 \Rightarrow 11111q_00;\\ 11*11q_11 \Rightarrow 11111q_00;\\ \qquad 11111*1q_11 \Rightarrow 1111111q_00.\end{gathered}

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


Этот маленький опыт работы с машинами Тьюринга позволяет сделать некоторые выводы. Так тщательно описанное устройство этой машины (разбитая на ячейки лента, считывающая головка) по существу не имеет никакого значения. Машина Тьюринга — не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита A\cup Q, т. е. конфигураций. Таким образом, для определения машины Тьюринга нужно задать ее внешний и внутренний алфавиты, программу и указать, какие из символов обозначают пустую ячейку и заключительное состояние.




Конструирование машин Тьюринга


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


Пример 32.3. Попытаемся построить такую машину Тьюринга, которая из n записанных подряд единиц оставляла бы на ленте n-2 единицы, также записанные подряд, если n \geqslant 2, и работала бы вечно, если n=0 или n=1.


В качестве внешнего алфавита возьмем двухэлементное множество A=\{0;1\}. Количество необходимых внутренних состояний будет определено в процессе составления программы. Считаем, что машина начинает работать из стандартного начального положения, т.е. когда в состоянии q_1 обозревается крайняя правая единица из n записанных на ленте.


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


q_11\to q_20L;\quad q_21\to q_30L.

Машина находится в состоянии q_3 и обозревает третью справа ячейку из тех, в которых записано данное слово (n единиц). Не меняя содержимого обозреваемой ячейки, машина должна остановиться, т.е. перейти в заключительное состояние q_0, независимо от содержимого ячейки. Вот эти команды:


q_30\to q_00;\quad q_31\to q_01.

Теперь остается рассмотреть ситуации, когда на ленте записана всего одна единица или не записано ни одной. Если на ленте записана одна единица, то после первого шага (выполнив команду q_11\to q_20L) машина будет находиться в состоянии q_2 и будет обозревать вторую справа ячейку, в которой записан 0. По условию, в таком случае машина должна работать вечно. Это можно обеспечить, например, такой командой: q_20\to q_20\Pi, выполняя которую шаг за шагом, машина будет двигаться по ленте неограниченно вправо (или протягивать ленту через считывающую головку справа налево). Наконец, если на ленте не записано ни одной единицы, то машина, по условию, также должна работать вечно. В этом случае в начальном состоянии q_1 обозревается ячейка с содержимым 0, и вечная работа машины обеспечивается следующей командой: q_10\to q_10\Pi.


Запишем составленную программу (функциональную схему) построенной машины Тьюринга в виде таблицы:


\begin{array}{|c|c|c|c|} \hline A \setminus Q & q_1 & q_2 & q_3 \\ \hline 0 & q_10\Pi & q_20\Pi & q_00\\ \hline 1& q_00L & q_20L & q_01 \\ \hline \end{array}

В заключение отметим следующее. Созданная нами машина Тьюринга может применяться не только к словам в алфавите A=\{0;1\}, представляющим собой записанные подряд п единиц (n \geqslant 2). Она применима и ко многим другим словам в этом алфавите, например (проверьте самостоятельно) к словам: 1011, 10011, 111011, 11011, 1100111, 1001111, 10111, 10110111, 10010111 и т.д. (исходя из стандартного начального положения). С другой стороны, построенная машина не применима (т.е. при подаче этих слов на вход машины она работает вечно) не только к слову "1" или к слову, состоящему из одних нулей. Она не применима и к следующим словам (проверьте самостоятельно): 101, 1001, 11101, 101101, 1100101101 и т.д..




Вычислимые по Тьюрингу функции


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


Остается договориться о некоторых условностях для того, чтобы это определение стало до конца точным. Во-первых, напомним, что речь идет о функциях (или возможно о частичных функциях, т. е. не всюду определенных), заданных на множестве натуральных чисел и принимающих также натуральные значения. Во-вторых, нужно условиться, как записывать на ленте машины Тьюринга значения хи x_1,x_2,\ldots,x_n аргументов функции f(x_1,x_2,\ldots,x_n), из какого положения начинать переработку исходного слова и, наконец, в каком положении получать значение функции. Это можно делать, например, следующим образом. Значения x_1,x_2,\ldots,x_n аргументов будем располагать на ленте в виде следующего слова:


0\; \underbrace{1\,\ldots\,1}_{x_1}\; 0\; \underbrace{1\,\ldots\,1}_{x_2}\; 0\,\ldots\,0\; \underbrace{1\,\ldots\,1}_{x_n}\;0.

Здесь полезно ввести следующие обозначения. Для натурального x обозначаем:


1^x= \underbrace{1\,\ldots\,1}_{x},\quad 0^x= \underbrace{0\,\ldots\,0}_{x}.

Дополнительно полагаем 0^0=1^0=\Lambda — пустое слово. Так что на слова 1^0=\Lambda,1^1=1,1^2=11,1^3=111,\ldots будем смотреть как на "изображения" натуральных чисел 0,1,2,3\ldots соответственно. Таким образом, предыдущее слово можно представить следующим образом: 01^{x_1}01^{x_2}0\ldots01^{x_n}0. Далее, начинать переработку данного слова будем из стандартного начального положения, т.е. из положения, при котором в состоянии q_1 обозревается крайняя правая единица записанного слова. Если функция f(x_1,x_2,\ldots,x_n) определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд f(x_1,x_2,\ldots,x_n) единиц; в противном случае машина должна работать бесконечно. При выполнении всех перечисленных условий будем говорить, что машина Тьюринга вычисляет данную функцию. Таким образом, сформулированное определение 35.4 становится абсолютно строгим.


Обратимся к примерам. Нетрудно понять, что машина Тьюринга из примера 32.2 по существу вычисляет функцию f(x)=x+1, а машина Тьюринга из примера 32.3 вычисляет функцию f(x)=x-2.


Пример 32.5. Построим машину Тьюринга, вычисляющую функцию f(x)=x\slash2. Эта функция не всюду определена: областью ее определения является лишь множество всех четных чисел. Поэтому, учитывая определение 32.4, нужно сконструировать такую машину Тьюринга, которая при подаче на ее вход четного числа давала бы на выходе половину этого числа, а при подаче нечетного — работала бы неограниченно долго.


Сконструировать машину Тьюринга — значит написать (составить) ее программу. В этом процессе два этапа: сначала создается алгоритм вычисления значений функции, а затем он записывается на языке машины Тьюринга (программируется).


В качестве внешнего алфавита возьмем двухэлементное множество A\{0;1\}. В этом алфавите натуральное число х изображается словом 11\ldots1, состоящим из x единиц, которое на ленте машины Тьюринга записывается в виде x единиц, стоящих в ячейках подряд. Работа машины начинается из стандартного начального положения: 01\ldots1q_110 (число единиц равно x).


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


\begin{aligned}&(1)\colon\quad q_11\to q_21L;\\ &(2)\colon\quad q_21\to q_10L;\\ &(3)\colon\quad q_20\to q_20L. \end{aligned}


Если число x единиц нечетно, то машина продолжит движение по ленте влево неограниченно, т.е. будет работать бесконечно. Если же число x единиц четно, то в результате выполнения команд создается конфигурация q_10010101\ldots01010, в которой число единиц равно x\slash2. Остается сдвинуть единицы так, чтобы между ними не стояли нули. Для осуществления этой процедуры предлагается следующий алгоритм. Будем двигаться по ленте вправо, ничего на ней не меняя, до первой единицы и перейдем за единицу. Передвижение осуществляется с помощью следующих команд:


\begin{aligned}&(4)\colon\quad q_10\to q_30\Pi;\\ &(5)\colon\quad q_30\to q_30\Pi;\\ &(6)\colon\quad q_31\to q_41\Pi. \end{aligned}


В результате их выполнения получим конфигурацию


001q_4010101\ldots010100.
(*)

Заменим 0, перед которым остановились, на 1 и продвинемся вправо до ближайшего 0:


\begin{aligned}&(7)\colon\quad q_40\to q_51\Pi;\\ &(8)\colon\quad q_51\to q_51\Pi. \end{aligned}


Получим конфигурацию 00111q_50101\ldots010100, в которой правее обозреваемой ячейки записаны "пары" 01,\ldots,01. Кроме того, на ленте одна единица записана лишняя. Продвинемся по ленте вправо до последней "пары" 01. Это можно сделать с помощью своеобразного цикла:


\begin{aligned}(9)\colon\quad &q_50\to q_60\Pi;\\ (10)\colon\quad &q_61\to q_51\Pi. \end{aligned}


Получим конфигурацию 001110101\ldots01010q_600. Двигаться дальше вправо бессмысленно. Вернемся на две ячейки назад и заменим единицу из последней "пары" 01 на ноль:


\begin{aligned}(11)\colon\quad &q_60\to q_70L;\\ (12)\colon\quad &q_70\to q_70L; \\ (13)\colon\quad &q_71\to q_80L. \end{aligned}


Получим конфигурацию 001110101\ldots01q_800. Число единиц на ленте снова равно x\slash2. Продвинемся влево на одну ячейку с помощью команды


(14)\colon\quad q_80\to q_90L.


В результате чего получим конфигурацию 001110101\ldots010q_9100. Теперь уничтожим самую правую единицу и продвинемся по ленте влево до следующей единицы:


\begin{aligned}& (15)\colon\quad q_91\to q_{10}0L;\\ & (16)\colon\quad q_{10}0\to q_{10}0L. \end{aligned}


Получим конфигурацию


001110101\ldots0q_{10}100,
(**)

в которой левее обозреваемой ячейки записана серия пар 10,10,\ldots,10 (если читать справа налево). Теперь на ленте недостает одной единицы, т.е. число единиц равно (x\slash2)-1. Продвинемся по ленте влево до последней "пары" 10. Это можно сделать с помощью цикла


\begin{aligned}& (17)\colon\quad q_{10}1\to q_{11}1L;\\ & (18)\colon\quad q_{11}0\to q_{10}0L, \end{aligned}


выполнив который, придем к следующей конфигурации: 001q_{11}110101\ldots 0100. Вернемся вправо к ближайшему нулю и превратим его в единицу:


\begin{aligned}& (19)\colon\quad q_{11}1\to q_{12}1\Pi;\\ & (20)\colon\quad q_{12}1\to q_{12}1\Pi;& (21)\colon\quad q_{12}0\to q_{13}1\Pi. \end{aligned}


Получим конфигурацию 001111q_{13}101\ldots0100, в которой число единиц снова равно x\slash2.


Если теперь перешагнем вправо по ленте через обозреваемую единицу и переведем машину в состояние q_4 с помощью команды


(22)\colon\quad q_{13}1\to q_{4}1\Pi,


то придем к следующей конфигурации: 0011111q_401\ldots0100, которая по существу аналогична конфигурации (*). В результате программа зацикливается (становится циклической): снова ближайший 0 превращается в 1, а самая правая 1 — в 0, затем машина возвращается к самому левому нулю, оказываясь в начале следующего цикла, и т.д.


Как же завершается работа программы? В некоторый момент конфигурация будет иметь вид 00111\ldots1110q_{10}100. Выполнив команды (17), (18), придем к конфигурации 00111\ldots1q_{11}110100. Далее выполняются команды (19), (20), (21), что приводит к конфигурации: 00111\ldots111111q_{13}00. Остается остановить машину. Это делается с помощью команды


(23)\colon\quad q_{13}0\to q_{0}0L.


Заключительная конфигурация имеет вид: 00111\ldots1111q_0100.


Запишем программу машины Тьюринга в табличной форме:


\begin{array}{|c|c|c|}\hline Q \setminus A & 0 & 1\\ \hline q_{1} & q_{3}0\Pi & q_{2}1L\\ q_{2} & q_{2}0L & q_{1}0L\\ q_{3} & q_{3}0\Pi & q_{4}1\Pi\\ q_{4} & q_{5}1\Pi & \\ q_{5} & q_{6}0\Pi & q_{5}1\Pi\\ q_{6} & q_{7}0L & q_{5}1\Pi\\ q_{7} & q_{7}0L & q_{8}0L\\ q_{8} & q_{9}0L & q_{2}1L\\ q_{9} & & q_{10}0L\\ q_{10} & q_{10}0L & q_{11}1L\\ q_{11} & q_{10}0L & q_{12}1\Pi\\ q_{12} & q_{13}1\Pi & q_{13}1\Pi\\ q_{13} & q_{0}0L & q_{4}1\Pi\\ \hline \end{array}

Предлагается самостоятельно проследить за работой этой машины Тьюринга, взяв в качестве исходных конкретные слова: 111, 1111, 111111, 1111111111.




Правильная вычислимость функций на машине Тьюринга


В предыдущем пункте мы рассмотрели вопрос о том, что значит и каким образом "данная машина Тьюринга вычисляет функцию f(x_1,x_2,\ldots,x_n)". Для этого нужно, чтобы каждое из чисел x_1,x_2,\ldots,x_n было записано на ленту машины непрерывным массивом из соответствующего числа единиц, а сами массивы были разделены символом 0. Если функция f(x_1,x_2,\ldots,x_n) определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд f(x_1,x_2,\ldots,x_n) единиц. При этом мы не очень строго относились к тому, в каком начальном положении машина начинает работать (часто это было стандартное начальное положение), в каком завершает работу и как эта работа протекает.


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


Определение 32.6. Будем говорить, что машина Тьюринга правильно вычисляет функцию f(x_1,x_2,\ldots,x_n), если начальное слово q_101^{x_1}01^{x_2}0\ldots 01^{x_n}0 она переводит в слово q_001^{f(x_1,x_2,\ldots,x_n)}0\ldots0 и при этом в процессе работы не пристраивает к начальному слову новых ячеек на ленте ни слева, ни справа. Если же функция f не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе работы не будет надстраивать ленту слева.


Пример 32.7. Приведем программы машин Тьюринга, правильно вычисляющих функции S(x)=x+1 и O(x)=0. Функция S(x)=x+1 осуществляет перевод: q_101^x0 \Rightarrow q_001^{x+1}. Ее программа:


q_10\to q_2\Pi,\quad q_21\to q_21\Pi,\quad q_20\to q_31,\quad q_31\to q_31L,\quad q_30\to q_00.

Функция O(x)=0 осуществляет перевод: q_101^x0 \Rightarrow q_000^{x+1}. Ее программа:


q_10\to q_20\Pi,\quad q_21\to q_21\Pi,\quad q_20\to q_30L,\quad q_31\to q_40,\quad q_40\to q_30L,\quad q_30\to q_00

Соответствующую машину Тьюринга обозначили \rm{O}.

Пример 32.8. Построить две машины "левый сдвиг" B^{-} и "правый сдвиг" B^{+}. Первая из начального стандартного положения перерабатывает слово 01^x0 в то же самое слово и останавливается, обозревая самую левую ячейку с нулем. Вторая машина из начального состояния, в котором обозревается левая ячейка с нулем, слово 01^x0 перерабатывает в то же самое слово и останавливается, обозревая самую правую ячейку с нулем.


Программа машины B^{-}\colon\, q_10\to q_20L,q_21\to q_21L,q_20\to q_00. Ясно, что программа машины B^{+} получается из программы предыдущей машины заменой символа "L" символом "П".




Композиция машин Тьюринга


Определение 32.9. Пусть заданы машины Тьюринга \Theta_1 и \Theta_2, имеющие общий внешний алфавит \{a_0,a_1,\ldots,a_m\} и алфавиты внутренних состояний \{q_0,q_1,\ldots,q_n\} и \{q_0,q'_1,\ldots,q'_n\} соответственно. Композицией (или произведением) машины \Theta_1 на машину \Theta_2 называется новая машина \Theta с тем же внешним алфавитом \{a_0,a_1,\ldots,a_m\}, внутренним алфавитом \{q_0,q_1,\ldots,q_n,q_{n+1},\ldots,q_{n+t}\} и программой, получающейся следующим образом. Во всех командах из \Theta_1 содержащих символ остановки q_0, заменяем последний на q_{n+1}. Все остальные символы в командах из \Theta_1 остаются неизменными. В командах из \Theta_2 символ q_0 оставляем неизменным, а все остальные состояния q'_i\,(i=1,\ldots,t) заменяем соответственно на q_{n+i}. Совокупность всех так полученных команд образует программу машины-композиции \Theta.


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


Пример 32.10. Сконструируем машины Тьюринга, правильно вычисляющие функции-проекторы I_m^n(x_1,x_2,\ldots,x_n)=x_m (1 \leqslant m \leqslant n).


Рассмотрим сначала конкретный случай n=2,n=3, т.е. функцию I_2^3(x_1, x_2,x_3)=x_2. Мы должны переработать слово q_101^{x_1}01^{x_2}01^{x_3}0 в слово q_001^{x_2}0. Будем применять к начальной конфигурации последовательно сконструированные ранее машины Тьюринга B^{+},V,B^{-},\rm{O}\colon.


\begin{aligned}& & & q_101^{x_1}01^{x_2}01^{x_3}0;\\ &B^{+}\colon & & 01^{x_1}q01^{x_2}01^{x_3}0;\\ &V\colon & & 01^{x_2}q01^{x_1}01^{x_3}0;\\ &B^{+}\colon & & 01^{x_2}01^{x_1}q01^{x_3}0;\\ &\rm{O}\colon & & 01^{x_2}01^{x_1}q00^{x_3}0 ;\\ &B^{-}\colon & & 01^{x_2}q01^{x_1}00^{x_3}0;\\ &\rm{O}\colon & & 01^{x_2}q00^{x_1}00^{x_3}0;\\ &B^{-}\colon & & q01^{x_2}00^{x_1}00^{x_3}0.\end{aligned}


Таким образом, функция I_2^3(x_1,x_2,x_3)=x_2 вычисляется следующей композицией машин:


B^{+}VB^{+}\rm{O}B^{-}\rm{O}B^{-}=B^{+}VB^{+}(\rm{O}B^{-})^2.

Проверьте самостоятельно, что функция I_2^2(x_1,x_2)=x_2 вычисляется композицией B^{+}V\rm{O}B^{-}.


Теперь мы можем представить себе алгоритм построения композиции машин B^{+},V, B^{-},\rm{O} для вычисления любой функции вида I_m^n(x_1,x_2,\ldots,x_n)= x_m с помощью правого сдвига B^{+}, применив его m-1 раз, нужно сначала достичь массива 01^{x_m}


(B^{+})^{m-1}\colon\quad 01^{x_1}0\ldots q01^{x_m}0\ldots01^{x_n}0.


Затем, двигаясь влево, транспонировать (с помощью V) массив 01^{x_m} с каждым соседним слева массивом, пока массив 01^{x_m} не выйдет на первое место:


(V\cdot B^{-})^{m-1}\colon\quad q01^{x_m}01^{x_1}0\ldots 01^{x_{m-1}} 01^{x_{m+1}}0\ldots 01^{x_n}0.


Теперь нужно дойти до крайнего правого массива с помощью (n-1)-кратного применения правого сдвига B^{+}\colon


(B^{+})^{n-1}\colon\quad 01^{x_m}01^{x_1}0\ldots 01^{x_{m-1}}01^{x_{m+1}}0\ldots q01^{x_n}0.


Наконец, нужно стирать последовательно справа налево все массивы единиц, кроме первого:


(\rm{O}B^{-})^{n-1}\colon\quad q01^{x_{m}}00^{x_{1}}0\ldots 00^{x_{m-1}} 00^{x_{m+1}}0\ldots 00^{x_{n}}0.


Итак, данную функцию (правильно) вычисляет следующая машина Тьюринга:


(B^{+})^{m-1} (V\cdot B^{-})^{m-1} (B^{+})^{n-1} (\rm{O}\cdot B^{-})^{n-1}.

При n=3,m=2 эта машина имеет вид:


B^{+}VB^{-}(B^{+})^2(\rm{O}B^{-})^2= B^{+}VB^{+}(\rm{O}B^{-})^2,

т.е. совпадает с построенной выше машиной. При n=2,m=2 эта машина имеет вид: B^{+}(VB^{-})B^{+}(\rm{O}B^{-})= B^{+}V\rm{O}B^{-}, т.е. также совпадает с соответствующей рассмотренной выше машиной Тьюринга.




Тезис Тьюринга (основная гипотеза теории алгоритмов)


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


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


Остается уточнить, что значит уметь вычислять значения функции. Это значит вычислять значения функции с помощью подходящей машины Тьюринга. Для каких же функций возможно их тьюрингово вычисление? Многочисленные исследования ученых, обширный опыт показали, что такой класс функций чрезвычайно широк. Каждая функция, для вычисления значений которой существует какой-нибудь алгоритм, оказывалась вычислимой посредством некоторой машины Тьюринга. Это дало повод Тьюрингу высказать следующую гипотезу, называемую основной гипотезой теории алгоритмов, или тезисом Тьюринга:


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


Это означает, что строго математическое понятие вычислимой (по Тьюрингу) функции является по существу идеальной моделью взятого из опыта понятия алгоритма. Данный тезис есть не что иное, как аксиома, постулат, выдвигаемый нами, о взаимосвязях нашего опыта с той математической теорией, которую мы под этот опыт хотим подвести. Конечно же данный тезис в принципе не может быть доказан методами математики, потому что он не имеет внутриматематического характера (одна сторона в тезисе — понятие алгоритма — не является точным математическим понятием). Он выдвинут исходя из опыта, и именно опыт подтверждает его состоятельность. Точно так же, например, не могут быть доказаны и математические законы механики; они открыты Ньютоном и многократно подтверждены опытом.


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


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




Машины Тьюринга и современные электронно-вычислительные машины


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


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


Далее, машина Тьюринга обладает бесконечной внешней памятью (неограниченная в обе стороны лента, разбитая на ячейки). Но ни в одной реально существующей машине бесконечной памяти быть не может. Это говорит о том, что машины Тьюринга отображают потенциальную возможность неограниченного увеличения объема памяти современных ЭВМ.


Наконец, можно провести более подробный сравнительный анализ работы современной ЭВМ и машины Тьюринга. В большинстве ЭВМ принята трехадресная система команд, обусловленная необходимостью выполнения бинарных операций, в которых участвует содержимое сразу трех ячеек памяти. Например, число из ячейки a умножается на число из ячейки b, и результат отправляется в ячейку c. Существуют ЭВМ двухадресные и одноадресные. Так, одноадресная ЭВМ работает следующим образом: вызывается (в сумматор) число из ячейки a; в сумматоре происходит, например, умножение этого числа на число из ячейки b; результат отправляется из сумматора в ячейку c. Машину Тьюринга можно считать одноадресной машиной, в которой система одноадресных команд упрощена еще больше: на каждом шаге работы машины команда предписывает замену лишь единственного знака, хранящегося в обозреваемой ячейке, а адрес обозреваемой ячейки при переходе к следующему такту может меняться лишь на единицу (обозрение соседней справа или слева ячейки ленты) или не меняться вовсе. Это удлиняет процесс, но в то же время резко унифицирует его, делает стандартным.


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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2020 MathHelpPlanet.com. All rights reserved