Навигация
Календарь
Машина Тьюринга. Задачи и решения
Один из важнейших вопросов современной информатики — существует ли формальный исполнитель, с помощью которого можно имитировать любого формального исполнителя. ответ на этот вопрос был получен почти одновременно двумя выдающимися учеными — А. Тьюрингом и Э. Постом. Предложенные ими исполнители отличались друг от друга, но оказалось, что они могут имитировать друг друга, а главное — имитировать работу любого формального исполнителя.
Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.
Рассмотрим работу Машины Тьюринга.
Машина Тьюринга представляет собой бесконечную ленту, поделенную на ячейки, и каретку (считывающе-печатающее устройство), которая движется вдоль ленты.
Таким образом Машина Тьюринга формально описывается набором двух алфавитов:
A=
Q=
Каждая ячейка ленты может содержать символ из внешнего алфавита A =
Допустимые действия Машины Тьюринга таковы:
1) записать какой-либо символ внешнего алфавита в ячейку ленты (символ, бывший там до того, затирается)
2) сместиться в соседнюю ячейку
3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q
Машина Тьюринга — это автомат, который управляется таблицей.
Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q =
В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «
Машина Тьюринга (целая часть от деления)
Машина Тьюринга: вычисление остатка от деления
Здравствуйте Друзья, помогите пожалуйста с задачей. Необходимо построить машину Тьюринга.
Сложение четырех целых без знака (Машина Поста), Троичное вычитание «-1» (Машина Тьюринга).
Здравствуйте! Можете пожалуйста помочь с задачками: Машина Поста: Сложение четырех целых без.
Машины Поста и Тьюринга. Посчитать количество букв имени (4) и фамилии (7), а затем указать разницу
Помогите решить задачу. На Машине Поста нужно написать программу Необходимо посчитать количество.
Деление нацело любых натуральных чисел на машине Тьюринга (оба числа записаны на ленте последовательностью единиц такой длины каково число)? Это довольно сложная задача.
Деление делается через вычитание. При вычитании вычитаемое уничтожается, значит надо еще уметь делать копию числа. Кроме того, на ленте нужно место для результата деления.
Идея алгоритма такая.
1)копируем делитель к делимому,
2)производим вычитание этой копии из делимого.
3)если вычлось, то добавляем 1 к результату деления.
Потом опять переходим на шаг (в состояние) 1. Так делаем до тех пор, пока удаётся вычитать. Если вычесть не удалось, то очищаем на ленте всё, кроме результата деления.
Добавлено через 50 минут
Вот для примера НАМ для деления двух чисел
Машина Тьюринга
A=
Машина Тьюринга
На входной ленте задано двоично-десятичное число. Получить десятичное представление этого числа.
Машина Тьюринга
Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное неполному.
Алгоритмы. Машина Тьюринга. Альтернативные определения алгоритма. Теория вычислимости и проблема останова.
Мы часто решаем задачи различной сложности: бытовые, математические, и т.п. Некоторые решаются легко, над некоторыми приходится изрядно подумать, для некоторых мы так и не находим решения.
В общем случае, способ решения задачи (если оно есть) можно описать с помощью конечного числа элементарных действий.
Например, решение квадратного уравнения:
Можно ввести следующее интуитивное понятие алгоритма:
Алгоритм набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий, при любом наборе исходных данных.
Это, конечно, не строгое определение, но оно описывает суть понятия алгоритма.
Алгоритмы составляются в расчёте на конкретного исполнителя, и, соответственно, должны быть составлены на языке, который исполнитель сможет понять.
Исполнителем алгоритма может быть человек, а может быть и вычислительная машина, или какой-нибудь другой автомат, например, ткацкий станок.
Выделяются следующие свойства алгоритмов:
Дискретность алгоритм должен представлять собой некую последовательность отдельных, чётко определённых шагов (действий). Каждое из этих действий должно быть конечно по времени. Детерминированность на каждом шаге работы алгоритма, следующий шаг однозначно определяется текущим состоянием системы. Как следствие, на одинаковых исходных данных, алгоритм всякий раз возвращает одинаковые результаты, сколько бы раз его ни выполняли. Понятность алгоритм должен быть сформулирован на языке, понятном исполнителю. Если речь идёт о вычислительной машине, алгоритм должен использовать только те команды, которые известны вычислительной машине и результат действий которых строго определён. Конечность алгоритм должен завершаться за конечное число шагов. Массовость алгоритм должен быть применим к разным наборам входных данных. Другими словами, алгоритм должен быть пригоден для решения класса задач. Возвращаясь к примеру с квадратным уравнением, алгоритм подходит для решения всех квадратных уравнений, а не только одного или нескольких. Результативность алгоритм должен завершаться определенным результатом. Скажем, решением задачи, или выяснением отсутствия решений. Если алгоритм не приводит к результату, непонятно, зачем он вообще такой нужен.
Не всякий способ решения задачи является алгоритмом. Скажем, алгоритм подразумевает отсутствие выбора. Например, большинство кулинарных рецептов алгоритмами не являются, поскольку используют такие фразы как “соль добавить по вкусу”. Как следствие, нарушается требование детерминированности.
Не для каждой задача, для которой существует решение, существует так же и алгоритм решения. Например, задача распознавания изображений до сих пор в значительной мере остается не решенной, и уж точно не с помощью строгого алгоритма. Впрочем, использование нейросетей дает вполне неплохие результаты.
Обычно, для алгоритма существуют наборы допустимых входных данных. Было бы странно пытаться применить алгоритм решения уравнений для приготовления ужина, или наоборот.
Кроме того, ограничен так же и набор возможных действий исполнителя, поскольку если бы были допустимы любые действия, то среди них должно было бы быть так же и “недопустимое”.
Строгое определение алгоритма
Определение алгоритма, приведенное выше, не является строгим. Это создает некоторые трудности. В частности, с таким определением невозможно строго доказать, является ли данный класс задач решаемым при помощи алгоритма.
Оказывается, существует класс алгоритмически неразрешимых задач – задач, для которых невозможно составить алгоритм решения. Но чтобы строго доказать алгоритмическую неразрешимость, нужно для начала иметь строгое определение алгоритма.
В 20-30 годах XX века, над проблемой строгого определения алгоритма работали разные математики, в частности Алан Тьюринг, Эмиль Леон Пост, Андрей Андреевич Марков, Андрей Николаевич Колмогоров, Алонзо Чёрч и другие. Их работа в итоге привела к возникновению и развитию теории алгоритмов, теории исчислимости и различных подходов к исчислению, и, кстати, программированию в целом. Одним из результатов их работы стало появление нескольких строгих определений алгоритма, введенных различным образом, но эквивалентных друг другу.
Мы подробно остановимся на определении Тьюринга, и поверхностно разберем эквивалентные определения Поста, Чёрча и Маркова.
Машина Тьюринга
Для введения формального определения алгоритма, Тьюринг придумал и описал абстрактную вычислительную машину, называемую вычислительной машиной Тьюринга, или просто машиной Тьюринга.
Английский математик, логик, криптограф, возможно первый в мире “хакер”, стоял у истоков информатики и теории искуственного интеллекта. Внес существенный вклад в победу союзных войск во второй мировой войне.
В качестве входных данных для машины Тьюринга используются слова, составленные с помощью некоего алфавита, то есть, набора символов.
Результатом работы машины Тьюринга так же являются слова.
Слово, к которому применяется алгоритм, называется входным. Слово, которое получается в результате работы, выходным.
Набор слов, к которым применим алгоритм, называется областью применимости алгоритма.
Строго говоря, доказать, что любой объект может быть представлен в виде слов, составленных в каком-то алфавите, нельзя – для этого нам бы потребовалось строгое определение объекта. Однако, можно проверить, что любой наугад взятый алгоритм, работающий над объектами, можно преобразовать так, что он будет работать над словами, при этом суть алгоритма не изменится.
Описание машины Тьюринга
В состав машины Тьюринга входит неограниченная в обе стороны лента, разделенная на ячейки, и управляющее устройство (также называется головкой записи-чтения, или просто автомат), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
Хотя машина Тьюринга является абстрактной концепцией, достаточно просто представить себе подобную машину (правда, с конечной лентой), и даже существуют демонстрационные машины в таком роде:
Алгоритм для машины Тьюринга удобно представлять в виде таблицы: столбцы таблицы соответствуют текущему (наблюдаемому) символу на ленте, строки – текущему состоянию автомата, а в ячейках записывается команда, которую должен выполнить автомат.
Команда, в свою очередь, может иметь следующую структуру:
\[ a_k \left\lbrace \begin
Пример
Составим алгоритм для машины Тьюринга, который прибавит к входному слову, представляющему собой десятичное число, 1.
Будем считать, что в начальном состоянии автомат находится слева от входного слова.
Тогда, описательно, алгоритм можно сформулировать следующим образом:
Условимся, что начальное состояние \(1\) – поиск начала входного слова, \(2\) – поиск конца входного слова, \(3\) – прибавление 1.
| \(_ | Λ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | ΛП1 | 0Н2 | 1Н2 | 2Н2 | 3Н2 | 4Н2 | 5Н2 | 6Н2 | 7Н2 | 8Н2 | 9Н2 |
| 2 | ΛЛ3 | 0П2 | 1П2 | 2П2 | 3П2 | 4П2 | 5П2 | 6П2 | 7П2 | 8П2 | 9П2 |
| 3 | 1Н0 | 1Н0 | 2Н0 | 3Н0 | 4Н0 | 5Н0 | 6Н0 | 7Н0 | 8Н0 | 9Н0 | 0Л3 |
Проследим работу этого алгоритма на примере. Первая строчка соответствует ленте, во второй обозначается положение автомата и его текущее состояние.
В состоянии 1, автомат находится над пустой ячейкой. Соответствующая команда из таблицы “ΛП1”, то есть, оставить ячейку пустой, переместиться вправо и остаться в состоянии 1:
Теперь автомат наблюдает значение “1”. Соотвествующая команда “1Н2”, то есть оставить в ячейке “1”, не перемещаться, и перейти в состояние “2”:
В состоянии “2”, автомат наблюдает значение “1”. Соответствующая команда “1П2”, то есть оставить “1”, переместиться вправо и остаться в состоянии “2”:
Аналогично, команда для состояния “2” и символа “9” – “9П2”:
Наконец, в состоянии 2 автомат наблюдает пустой символ. Команда “ΛЛ3”:
Теперь, в состоянии 3 и наблюдая символ “9”, автомат выполняет команду “0Л3”:
Наконец, выполняется команда “2Н0”:
Состояние “0” – состояние остановки. Работа алгоритма завершена.
Формальное описание
Математически, машину Тьюринга можно описать следующим образом:
Ключевым в теории алгоритмов является тезис Тьюринга.
В вольной формулировке, тезис Тьюринга формулируется следующим образом:
Тезис Тьюринга для любой алгоритмически разрешимой задачи, существует решающая эту задачу машина Тьюринга. иначе, для любого алгоритма существует эквивалентная ему машина Тьюринга.
Тезис Тьюринга позволяет говорить об алгоритмах, пользуясь достаточно простым математическим аппаратом. Более того, сама по себе машина Тьюринга является универсальным исполнительным устройством, и сама возможность создания такой воображаемой машины стала поводом говорить о создании универсальной вычислительной техники.
Альтернативные определения алгоритма
Кроме машины Тьюринга, существует несколько независимых определений, эквивалентных определению Тьюринга.
В частности, определение через машину Поста, через лямбда-исчисление Чёрча, нормальный алгоритм Маркова.
Рассмотрим эти способы.
Машина Поста
Через год после Тьюринга, американский математик Эмиль Леон Пост независимо предложил другую абстрактную универсальную вычислительную машину, которая является некоторым упрощением по сравнению с машиной Тьюринга.
Машина Поста оперирует двузначным алфавитом, и внутреннее состояние автомата заменяется на строку программы.
В остальном, машина Поста аналогична машине Тьюринга: есть автомат, и есть бесконечная лента с ячейками.
Машина Поста может выполнять следующие команды:
Так же машина Поста имеет несколько запрещенных команд:
Подобные события приводят к аварийному завершению работы.
Для написания программ для машины поста можно использовать следующие обозначения:
Эта программа сотрет первую метку (1), находящуюся справа от начального положения автомата, и остановит автомат в ячейке слева от нее.
По большому счету, машина Поста является предшественником императивных языков программирования, например, C, Fortran и пр.
Машина Поста является эквивалентной машине Тьюринга. Другими словами, для любой программы для машины Тьюринга, можно записать эквивалентную программу для машины Поста, и наоборот.
Одним из важных следствий этой эквивалентности является то, что любой алфавит можно свести к двоичному коду.
Аналогично тезису Тьюринга, существует так же и тезис Поста.
Тезис Поста всякий алгоритм представим в виде машины Поста.
Нормальный алгоритм Маркова
Нормальные алгоритмы Маркова предназначены для применения к словам в различных алфавитах.
Определение всякого нормального алгоритма состоит из двух частей:
Сам алгоритм применяется к словам, то есть последовательностям символов алфавита.
При этом предполагается, что вспомогательные символы \(\to\) и \(\to\cdot\) не принадлежат алфавиту алгоритма.
Процесс применения нормального алгоритма к произвольному слову \(V\) представляет собой следующую последовательность действий:
Любой нормальный алгоритм эквивалентен некоторой машине Тьюринга, и наоборот – любая машина Тьюринга эквивалентна некоторому нормальному алгоритму.
Аналог тезиса Тьюринга для нормальных алгоритмов принято называть принципом нормализации.
Пример
Данный алгоритм преобразует двоичные числа в “единичные” (в которых записью целого неотрицательного числа N является строка из N палочек). Например, двоичное число 101 преобразуется в 5 палочек: |||||.
Рекурсивные функции
Систему, эквивалентную машине Тьюринга, можно построить на основе математических функций. Для этого, нам требуется ввести следующие классы функций:
Последний класс будет совпадать с классом вычислимых по Тьюрингу функций (то есть функций, для вычисления которых можно построить алгоритм для машины Тьюринга).
Определение алгоритма через рекурсивные функции по сути лежит в основе лямбда-исчисления, и на его основе строится подход функционального программирования.
Примитивно рекурсивные функции
Класс примитивно рекурсивных функций содержит базовые функции и все функции, получающиеся из базовых посредством операторов подстановки и примитивной рекурсии.
К базовым функциям относятся:
Для конструирования остальных функций класса используются операторы:
Частично рекурсивные функции
Класс частично рекурсивных функций включает примитивно рекурсивные функции, и, плюс к этому, все функции, которые получаются из примитивно рекурсивных с помощью оператора минимизации аргумента:
Оператор минимизации аргумента
\[ h(x_1,\ldots,x_
В то время как примитивно рекурсивные функции всегда вычислимы, частично рекурсивные функции при некоторых значениях аргументов могут быть не определены.
Более строго частично рекурсивные функции следовало бы называть “частично определенные рекурсивные функции”, поскольку они определены только на части возможных значений аргументов.
Общерекурсивные функции
Общерекурсивные функции – это подкласс всех частично рекурсивных функций, которые определены для любых значений аргументов. Задача определения того, является ли данная частично рекурсивная функция общерекурсивной является алгоритмически неразрешимой. Это подводит нас к теме теории вычислимости и проблеме останова.
Теория вычислимости и проблема останова
Наше воображение в целом допускает существование неразрешимых задач, то есть задач, для решения которых невозможно составить алгоритм.
Исследованием таких задач занимается теория вычислимости.
Примерами алгоритмически неразрешимых задач являются проблема останова и проблема распознавания выводимости. Рассмотрим их более подробно.
Проблема останова является алгоритмически неразрешимой. Докажем это.
Пусть существует универсальный алгоритм, решающий проблему останова. Рассмотрим тогда класс алгоритмов, обрабатывающий тексты описания алгоритмов.
Более общей формулировкой проблемы останова является проблема определения выводимости.
Проблема распознавания выводимости
Пусть определены некий алфавит, слова (формулы) этого алфавита, и система формальных преобразований над словами этого алфавита (т.е. построено логическое исчисление)
Существует ли для любых двух слов \(R\) и \(S\) дедуктивная цепочка, ведущая от \(R\) к \(S\) в рамках данного логического исчисления?
В 1936 году Алонзо Чёрч доказал теорему Чёрча.
Теорема Чёрча Проблема распознавания выводимости алгоритмически неразрешима.
Чёрч использовал для доказательства формализм лямбда-исчисления. В 1937 независимо от него ту же теорему доказал Тьюринг, используя формализм машины Тьюринга.
Поскольку все определения алгоритмов эквиваленты друг другу, существует система понятий, не связанная с конкретным определением алгоритма, и оперирует понятием вычислимой функции.
Вычислимая функция функция, для вычисления которой можно составить алгоритм.
Существуют задачи, в которых связь между входными и выходными данными невозможно описать с помощью алгоритма. Такие функции являются невычислимыми.
Пример невычислимой функции
Деление на машине тьюринга пример
Абстрактные вычислительные машины
Материал взят с ресурса Планета информатики
То есть, всякий интуитивный алгоритм может быть реализован с помощью некоторой машины Тьюринга.
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой. Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
Можно усложнить программу. Допустим, головка располагается не обязательно над первым, а над любым символом слова. Тогда программа для данной машины Тьюринга может быть такой (а могла бы быть и другой):
Здесь происходит сдвиг головки влево до тех пор, пока она не окажется над пустым символом. После этого машина переходит в состояние Q2 (команды которого совпадают с командами Q1 предыдущей программы).
Материал взят с ресурса Планета информатики
Решение этой задачи аналогично рассмотренному выше примеру.
Задача 4 (усложнение задачи 3)
Те клетки, в которые машина Тьюринга никогда не попадает, оставляем пустыми.
Решение этой задачи обычно вызывает у школьников затруднение. При разборе решения этой задачи можно пойти, например, следующим путем.
Рассмотрите со школьниками следующие варианты входных слов и попросите их сформулировать, что должна делать машина Тьюринга, каков внешний вид выходного слова, чем с точки зрения машины Тьюринга эти варианты различаются:
Рассмотрим следующие варианты входных слов:
Однако, как ни странно, решение этой задачи вызывает большие трудности. Очень часто ученики строят машину Тьюринга, которая выполняет циклические действия: последовательно пододвигают правые n штрихов к левым.
В этом случае их программа выглядит следующим образом:
На примере этой задачи четко видно, как часто дети пытаются решить задачу уже знакомыми способами. Мне кажется, что, предлагая ученикам задачи на составление машин Тьюринга, мы развиваем способность к нахождению необычных решений, развиваем способность творчески думать!
Эта задача кажется школьникам достаточно легкой, но трудности возникают с остановом машины Тьюринга. Ниже приведен один из возможных вариантов машины Тьюринга для этой задачи.
Идея решения (условие останова). На ленте есть два исходных массива штрихов.
Опишем сначала состояния машины Тьюринга, которые необходимы для решения нашей задачи, а затем составим программу-таблицу.
При решении этой задачи следует обратить внимание на правильное выписывание алфавита:
Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:
После программы запуска возможны варианты: