Теория алгоритмов

Математическая логика и теория алгоритмов Глава 2. Теория алгоритмов Параграф 3. Машина Тьюринга Концепция этой машины возникла в середине 30-х гг. XX в. у А. Тьюринга в результате произведенного им анализа действий человека, выполняющего в соответствии с заранее разработанным планом те или иные вычисления, т.е. последовательные преобразования знаковых комплексов. Например, производя вычисления согласно избранному плану, математик, рассматривая какое-либо место в своих записях и находясь в определенном “умонастроении”, делает необходимые изменения в написанном, проникается новым “умонастроением” и переходит к рассмотрению дальнейших записей. Структура машины Машина Тьюринга состоит из: 1. Управляющего устройства, которое может находиться в одном из состояний, образующих конечное множество Q = { q 1 , … , q n } . Среди состояний управляющего устройства выделены начальное состояние q 1 и заключительное q z . В начальном состоянии машина находится перед началом работы, попав в заключительное машина останавливается. 2. Ленты, разбитой на ячейки, в каждой из которых находится один из символов конечного алфавита A = { a 1 , … , a m } . Лента бесконечна в обе стороны, однако в начальный момент времени только конечное число ячеек ленты заполнено непустыми символами, остальные ячейки пусты, т. е. содержат пустой символ 𝜆 (пробел). Из характера работы машины следует, что и в любой последующий момент времени лишь конечный отрезок ленты будет заполнен символами. Поэтому важна не фактическая (как говорят в математике, актуальная) бесконечность ленты, а ее неограниченность, т. е. возможность писать на ней сколь угодно длинные, но конечные слова. Текущее состояние qj Головка Лента aj Текущая ячейка 3. Устройства обращения к ленте, т. е. считывающей и пишущей головки. Она в каждый момент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке и состояния управляющего устройства записывает в ячейку символ (быть может, совпадающий с прежним или пустой, т. е. стирает символ), сдвигается на ячейку влево или вправо, или остается на месте. При этом управляющее устройство переходит в новое состояние (или остается в старом). Таким образом, память машины Тьюринга - это конечное множество состояний (внутренняя память) и лента (внешняя память). Данные машины Тьюринга - это слова в алфавите ленты; на ленте записываются и исходные данные, и окончательные результаты. Элементарные шаги машины - это считывание и запись символов, сдвиг головки на ячейку влево и вправо, а также переход управляющего устройства в следующее состояние. Детерминированность машины Тьюринга Детерминированность машины, т. е. последовательность ее шагов, определяется следующим образом. Для любого внутреннего состояния q i и символа a j однозначно заданы: а) следующее состояние q'i , может и совпадающее с q i ; б) символ a'j , который нужно записать вместо a j в ту же ячейку (стирание символа будем понимать как запись пустого символа 𝜆); в) направление сдвига головки d k , обозначаемое одним из трех символов: L (влево), R (вправо), E (на месте). Это задание может описываться системой правил (команд), имеющих вид qi aj → q'i a'j dk . Далее, это задание может описываться таблицей, строкам которой соответствуют состояния q i , столбцам - выходные символы a j , а на пересечении строки q i и столбца a j записана тройка q'i a'j d k . a1 a2 ⋯ am q1 q2 q4 a3 R ⋯ qn Наконец, задание может описываться некоторой блок-схемой, которая называется диаграммой переходов. В этой диаграмме состояниям соответствуют вершины, а правилу вида q i a j → q'i a'j d k - ребро, ведущее из вершины q i в q'i , на котором написано aj → a'j dk с левой частью qi aj . q2 a2 → a3 R q4 Условие однозначности требует, что для любого j и любого i ≠ z в системе команд имелась одна команда вида q i a j → q'i a'j d k с левой частью q i a j . Состояние q z в левых частях команд не встречается. На диаграмме переходов это условие означает, что из каждой вершины q i , кроме q z , выходят ровно m ребер, причем на разных ребрах левые части различны. В вершине q z выходящих ребер нет. Конфигурация и работа машины Полное состояние машины Тьюринга, по которому можно определить ее дальнейшее поведение определяется ее внутренним состоянием, состоянием ленты и положением головки на ленте. Полное состояние машины называется ее конфигурацией (иногда машинным символом). Конфигурация обозначается тройкой 𝛼 1 q i 𝛼 2 , где q i - текущее внутреннее состояние, 𝛼 1 - слово слева от головки, а 𝛼 2 - слово, образованное символом, обозреваемое головкой, и символами справа от него. Причем слева от 𝛼 1 и справа от 𝛼 2 нет пустых символов. Например, конфигурация с внутренним состоянием qi , в которой на ленте записано слово abcde, а головка обозревает символ d, запишется в виде abcq i de. Стандартная начальная конфигурация - это конфигурация вида q 1 𝛼, а конечная - вида q z 𝛼. Ко всякой незаключительной конфигурации K применима ровно одна команда вида q i a j → q'i a'j d k , которая переводит конфигурацию K в какую-то новую конфигурацию K'. Этот переход записывают в виде K ⏪⏫ K'. Иногда символ T опускают, T если ясно о какой машине T идет речь. Пусть для конфигураций K 1 , K n имеется последовательность конфигураций K 1 , K 2 , … , K n такая, что K 1 → K 2 → … → K n . Это условие записывается в виде K 1 ⇒ K n , и говорят, что в процессе работы машина T от конфигурации K 1 перешла к конфигурации K n . Например, пусть в системе команд машины T имеются команды q 2 a 5 → q 3 a 4 R, q3 a1 → q4 a2 L. Тогда q2 a5 a1 a2 → a4 q3 a1 a2 → q4 a4 a2 a2 , т.е. q2 a5 a1 a2 ⇒ q4 a4 a2 a2 . Последовательность конфигураций K 1 → K 2 → K 3 → … однозначно определяется начальной конфигурацией K 1 и полностью описывает работу машины T. Эта последовательность конечна, если в ней встретится заключительная конфигурация, и бесконечная в противном случае. Пример. Пусть машина имеет алфавит A = { 1, 𝜆 } и состояния { q 1 , q z } , а система команд q 1 1 → q 1 1R и q 1 𝜆 → q 1 1R. Любая начальная конфигурация имеет вид q1 111 … 1 . Тогда машина будет работать следующим образом: q1 111 … 1 → 1q1 11 … 1 → 11q1 1 … 1 → 111 … q1 1 → 111 … 1q1 𝜆 → 111 … 11q1 𝜆 → … . Машина будет работать бесконечно, заполняя ленту вправо единичками. Если 𝛼 1 q 1 𝛼 2 ⇒ 𝛽 1 q z 𝛽 2 , то говорят, что машина T перерабатывает слово 𝛼 1 𝛼 2 в слово 𝛽1 𝛽2 и обозначают это через T(𝛼1 𝛼2 ) = 𝛽1 𝛽2 . Исходными данными машины Тьюринга называются записанные на месте слова в алфавите A исх (A исх ⊂ A) и векторы из таких слов (словарные векторы над A исх ). Это значит, что для каждой машины рассматриваются только те начальные конфигурации, в которых на ленте записаны векторы над A исх . Запись на ленте словарного вектора (𝛼1 , … , 𝛼k ) называется правильной, если она имеет вид 𝛼1 𝜆𝛼2 𝜆 … 𝛼k-1 𝜆𝛼k (при условии 𝜆 ∉ A исх ) или 𝛼 1 *𝛼 2 * … *𝛼 k , где * - специальный символ разделитель, не входящий в A исх . Для любого вектора над A исх машина T либо работает бесконечно, либо перерабатывает его в совокупность слов, разделенных пробелом, над некоторым алфавитом результатов A рез ; A исх и A рез могут пересекаться и даже совпадать. В ходе работы на ленте могут появляться символы, не входящие в A исх и A рез , которые образуют промежуточный алфавит A пр (содержащий, в частности разделитель). Таким образом, получается A = A исх ∪ A пр ∪ A рез . В простейших случаях, A исх = A рез и Aисх = Aрез ∪ { 𝜆 } . Пусть f - функция, отображающая множество векторов над A исх во множество векторов над A рез . Говорят, что машина Тьюринга T правильно вычисляет функцию f, если: 1) для любых V и W таких, что f(V) = W, q 1 V * ⇒ q z W * , где V * и W * - правильные записи векторов V и W, соотвественно; 2) для любого V, для которого f(V) не определена, машина T, запущенная из конфигурации q 1 V * , работает бесконечно. Если для функции f существует машина T, которая правильно ее вычисляет, то говорят, что f вычислима по Тьюрингу. Понятно, что всякой правильно вычисляющей машине Тьюринга, т.е. машине, которая, начав со стандартной конфигурации q 1 𝛼, может остановиться только в стандартной конфигурации q z 𝛽, можно поставить в соответствие вычисляемую функцию. Две машины Тьюринга с одинаковым алфавитом A исх называются эквивалентными, если они вычисляют одну и ту же функцию. Пример. Пусть машина T содержит команды q i a j → q'i a'j E и q'i a'j → q'' i a'' j d k . Если заменим эти две команды одной q i a j → q'' i a'' j d k , то получим новую машину T', которая эквивалентна машите T. Оказывается, для любой машины T существует эквивалентная ей машина, не содержащая в командах E, т.е. можно рассматривать машины, головки которых постоянно движутся. Рассмотрим представление натуральных чисел в унарном коде, т.е. A исх = { 1 }, либо Aисх = { 1, * } . Тогда число x в унарном коде представляется в виде слова 11 … 1 = 1 x , состоящего из x единиц. Тогда числовая функция f(x 1 , … , x n ) правильно вычислима по Тьюрингу, если существует машина T такая, что q 1 1 x1 *1 x2 * … *1 xn ⇒ q z 1 y , когда f(x1 , … , xn ) = y , и T работает бесконечно, начиная с q1 1 x1 *1 x2 * … *1 xn ⇒ qz 1 y , если функция f(x 1 , … , x n ) не определена. Некоторые операции над машинами Тьюринга Теорема. Если f 1 (x) и f 2 (y) вычислимы по Тьюрингу, то функция f 2 (f 1 (x)) также вычислима по Тьюрингу. Идея доказательства заключается в следующем. Пусть T 1 - машина, вычисляющая f 1 , T2 - f2 , а множества их состояний Q1 = { q11 , … , q1n1 } и Q2 = { q21 , … , q2n2 } . Построим диаграмму переходов машины T из диаграмм T 1 и T 2 следующим образом. Отождествим начальную вершину q 21 диаграммы T 2 с конечной вершиной q 1z машины T1 . Для систем команд это равносильно тому, что к системе команд T1 приписываем систему команд T 2 , и при этом q 1z отождествляем с q 21 . Начальным состоянием T объявляем q 11 , а конечным - q 2z . Пусть f 2 (f 1 (x)) определена. Тогда T 1 1 x = 1 f1 (x) и q 11 1 x ⇒ q 1z 1 f1 (x) . Тогда T пройдет ту же конфигурацию, но только перейдет в состояние q 21 1 f1 (x) . Эта конфигурация является начальной конфигурацией для T 2 , поэтому q 21 1 f1 (x) ⇒ q 2z 1 f2 (f1 (x)) . В таком случае для машины T имеем q 11 1 x ⇒ q 2z 1 f2 (f1 (x)) . Если же f 2 (f 1 (x)) не определена, то либо T 1 , либо T 2 не остановится, а значит T не остановится. Композицию машин записывают T 2 (T 1 ). Аналогично, имеет место теорема для суперпозиции функций от нескольких переменных. Например, композиция T + (T коп ) вычисляет функцию f(x) = 2x. Математическая логика и теория алгоритмов Тема. Машины Тьюринга Задание 1. Известно, что на ленте записано слово из n единиц 11 … 1 , где n ⩾ 1. Постройте машину Тьюринга с внешним алфавитом A = { 𝜆, 1 } , которая отыскивала бы левую единицу этого слова, если в начальный момент головка машины обозревает одну из ячеек с буквой данного слова. Решение: 𝜆11 … 1q1 111𝜆 Задание 2. Во введенном в лекции представлении чисел сложить числа a и b - это значит слово 1 a *1 b переработать в слово 1 a+b , т.е. удалить разделитель * и сдвинуть одно из чисел к другому. Это преобразование осуществляет машина T + с четырьмя состояниями и следующей системой команд q1 * → qz 𝜆R; q1 1 → q2 𝜆R; q2 1 → q2 1R; q2 * → q3 1L; q3 1 → q3 1L; q3 𝜆 → qz 𝜆R. 1 𝜆 * q1 q2 𝜆R qz 𝜆R q2 q2 1R q3 1L q3 q3 1L qz 𝜆R Здесь первая из команд задана для случая, когда a = 0 и исходное слово *1 b . Кроме того, здесь записаны не все команды. Например, нет команд вида q 1 𝜆 → и q 2 𝜆 → . Эти команды опущены, т.к. при любой начальной конфигурации данные состояния невозможны. Обычно всегда так и поступают, т.е. выписывают те команды, для которых возможны состояния машин. Рассмотрим, к примеру, как данная машина осуществляет сложение 3 + 2 , т.е. перерабатывает слово 111*11 в слово 11111. Итак, имеем q1 111*11 → 𝜆q2 11*11 → 𝜆q2 11*11 → 𝜆1q2 1*11 → 𝜆11q2 *11 → 𝜆1q3 1111 → → 𝜆q3 11111 → q3 𝜆11111 → 𝜆qz 11111. Эту систему команд можно записать в виде диаграммы переходов следующим образом. q1 * → 𝜆R qz 1 → 𝜆R 𝜆 → 𝜆R q2 1 → 1R q3 * → 1L 1 → 1L Задание 3. Машина, производящая копирование слова, т.е. переработка слова a в a*a. Для чисел эту задачу решает машина T коп . 1 𝜆 * q1 q2 0R qz 𝜆R q1 *L q1 1L q2 q2 1R q3 *R q3 *R q3 q3 1R q4 1L q4 q4 1L q4 *L q1 0R Рассмотрим, например, переработку слова 11 в слово 11*11. q1 11 → 0q2 1 → 01q2 𝜆 → 01*q3 𝜆 → 01q4 *1 → 0q4 1*1 → q4 01*1 → 0q1 1*1 → → 00q2 *1 → 00*q3 1 → 00*1q3 𝜆 → 00*q4 11 → 00q4 *11 → 0q4 0*11 → 00q1 *11 → → 0q1 0*11 → q1 01*11 → q1 𝜆11*11 → 𝜆qz 11*11. Для этой машины T коп диаграмма перехода имеет следующий вид 0 → 1L *→L q1 1→R 1 → 0R 𝜆→R qz q2 1→R *, 𝜆 → *R q3 *, 1 → L 𝜆 → 1L q4 0→R Если в какой-то команде правые части одинаковы, то левые части обычно пишут через запятую, а не рисуют несколько ребер. Как здесь, например, q 2 * → q 3 *R и q 2 𝜆 → q 3 *R. Задания для самостоятельной работы Задание 1. Имеется машина Тьюринга с внешним алфавитом A = { 𝜆, 1 } , алфавитом внутренних состояний Q = { q 1 , q z } и система команд: q 1 𝜆 → q z 1R; q 1 1 → q 1 1R. Составьте функциональную схему (таблицу) и определите, в какое слово перерабатывает машина каждое из следующих слов, если начальная конфигурация имеет следующий вид: а) 1𝜆1q 1 1𝜆𝜆11; б) 1q 1 1𝜆111𝜆1; в) 1𝜆q 1 𝜆111. Задание 2. Пусть машина Тьюринга задается следующей функциональной схемой: Q\A 𝜆 q1 1 * q2 𝜆L qz 𝜆E q2 q3 1R q2 1L q2 *L q3 q1 𝜆L q3 1R q3 *R Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина, исходя из следующей конфигурации: а) 111*11q 1 1; б) 1111*1q 1 1; в) *111q 1 1; г) 11111q 1 *. Примечание: постарайтесь усмотреть общую закономерность в работе машины. Задание 3. Сконструируйте машину Тьюринга с внешним алфавитом A = { 𝜆, 1 } , которая каждое слово в алфавите A 1 = { 1 } перерабатывает в пустое слово, исходя из стандартного начального положения.