Машина тьюринга как работает программа

nbspРассмотрим один из вариантов указанной машины, которая носит название машины Тьюринга.
nbsp1. Внешний алфавит, то есть конечное множество символов (A =begin a_, a_,a_, . a_ end). В этом алфавите в виде слова кодируется та информация, которая подается в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово.
nbsp3. Бесконечная в обе стороны лента (внешняя память машины). Она разбита на клетки. В каждую клетку может быть записана только одна буква. Пустую клетку будем обозначать символом (a_).
nbspКаждое сведение, хранящееся на ленте, изображается конечным набором символов (букв) внешнего алфавита, отличного от (a_). К началу работы машины на ленту подается начальное сведение (начальная информация). В этом случае управляющая головка, как правило, находится у крайнего левого знака с указанием начального состояния (q_) (рис. 1) (начальная конфигурация).

Машина Тьюринга. Принцип работы компьютера

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

nbspОчевидно, следующие конфигурации имеют вид:

nbspОсновная гипотеза теории алгоритмов

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

Источник: primat.org

Наследие Тьюринга: машина, тест и полнота

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

Что такое машина Тьюринга

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

Машина Тьюринга. Введение. Понятие машины тьюринга. Решение задачи

Это бесконечная лента, не имеющая ни начала, ни конца, поделённая на ячейки. Для работы с ней мы используем некое управляющее устройство (автомат), для визуализации выбрана каретка. В каждый момент времени она имеет состояние qj и считывает содержимое ячейки ai. О том, что происходит в остальной части ленты, каретка не знает, соответственно оперировать она может только текущими данными. Всего возможно три типа действий, зависящий от этой композиции:

• выполнить сдвиг на соседнюю ячейку;
• записать в текущую новое содержимое;
• изменить состояния.

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

Множества A = и Q = являются конечными, a0 – символ пустой ячейки, q1 – начальное состояние, q0 – пассивное состояния, условие выхода машины из цикла.

Создадим таблицу для реализации алгоритма Тьюринга:

Символами _Л, _П, _Н обозначим направление движения автомата – соответственно сдвиг «влево», «вправо» или неподвижное положение.

Пусть наша лента выглядит так:

Начальное положение – крайняя правая ячейка, остановка – в пустой клетке. Догадались как она будет выглядеть после завершения алгоритма?

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

Зачем это программисту

Машина Тьюринга позволяет размять мозги и взглянуть на решение задачи иначе. В конечном счёте, с той же целью следует познакомиться с:

• нормальным алгоритмом Маркова;
• лямбда-вычислениями;
• языком программирования Brainfuck.

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

Полнота по Тьюрингу

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

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

Тест по Тьюрингу

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

Такой тест на долгие годы предопределил развитие ИИ – программы вроде Элизы или PARRY строились именно на копировании человеческого поведения машиной. Уже позднее, когда стало понятно, что путь тупиковый, вектор развития был сдвинут в сторону изучения механизмов интеллекта. Однако до сих пор тема «способна ли мыслить машина» лежит в основе многих тестов, романов и кинофильмов.

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

Источник: gb.ru

Алгоритмы: машины Тьюринга

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

Основные определения

Рассматриваемая в этом разделе модель алгоритмов была предложена английским математиком Тьюрингом в 1937 г. еще до создания современных компьютеров 1 Аналогичная модель вычислений была примерно в то же время определена Е. Постом. Поэтому иногда такие машины называют машинами Тьюринга-Поста Он исходил из общей идеи моделирования работы вычислителя, оперирующего в соответствии с некоторым строгим предписанием. В машине Тьюринга расчленение процесса вычисления на элементарные шаги доведено в известном смысле до предела. Элементарным действием является замена одного символа в ячейке на другой и перемещение к соседней ячейке. При таком подходе процесс вычисления значительно удлиняется, но зато логическая структура процесса сильно упрощается и приобретает удобный для теоретического исследования вид.

внешнего алфавита машины , a_, dots ,a_ >» />. Головка машины представляет конечный автомат , который в каждый момент времени находится в одном из внутренних состояний Q =0,q1. , qn > . На каждом шаге головка в зависимости от своего внутреннего состояния и символа в ячейке, которую она наблюдает, изменяет свое внутреннее состояние и содержимое наблюдаемой ячейки и может сдвинуться на одну ячейку вправо или влево либо остаться на месте.

Дадим более формальное определение .

Определение 9.1. Машина Тьюринга — это система вида

включающая следующие компоненты:

• Q =0,q1. ,qn > — внутренний алфавит (алфавит состояний);
• — внешний алфавит (алфавит ленты );
• P — программа машины, в которой для каждой пары имеется (одна!) команда вида

задает сдвиг головки вправо, влево или на месте;

— начальное состояние;

— заключительное состояние.

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

Будем говорить, что некоторый символ стирается, если он заменяется на пустой. Два слова из будем считать равными, если они совпадают после отбрасывания всех пустых символов слева и справа. Например,

, но .

Как и для конечных автоматов, программу P можно задавать с помощью таблицы размера n x m , строки которой соответствуют состояниям из Q , а столбцы — символам из входного алфавита в которой на пересечении строки qi и столбца aj стоит тройка qk al C — правая часть команды qi aj -> qk al C .

Определение 9.2. Назовем конфигурацией м.Т. в некоторый момент времени слово K= wл qi aj wп , где — слово на ленте левее текушего положения головки , qi — внутреннее состояние в данный момент, aj — символ, обозреваемый головкой , — слово на ленте правее текушего положения головки .

Будем считать, что слово wл aj wп содержит все значащие символы на ленте . Поэтому, с точностью до описанного выше равенства слов, конфигурация определена однозначно. В частности, если

, т.е. пусто, то левее положения головки все ячейки пусты, а если , то правее положения головки все ячейки пусты.

Начальная конфигурация — это конфигурация вида q0w , т.е. в начальный момент времени головка в состоянии q0 обозревает первый символ входного слова w . < it Заключительная >конфигурация — это конфигурация вида w1 qf w2 , в которой машина находится в заключительном состоянии qf .

Определение 9.3. Скажем, что конфигурация K= w1 qi aj w2 м.Т . за один шаг (такт) переходит в конфигурацию , если в программе имеется команда qi aj -> qk al C и при этом,

• если С=Н, то w1 ‘ =w1, w2 ‘ =w2 и aj ‘ >=al;
• если С=Л, то w1=w1 ‘ a, aj ‘ >=a, w2 ‘ =al w2 (если то );
• если С=П, то w₂=aw₂ ‘ , a_{j ‘ >=a, w1} ‘ =w₁ a_l (если будет означать, что конфигурация K за n шагов переходит в K ‘ . (Если из контекста ясно, о какой машине идет речь, то индекс будем опускать).

  
  Рис. 9.1. Выполнение команды q3 0 -> q5 1 П

  Например, ситуации, представленной на рис.9.1 слева соответствует конфигурация . Предположим, что программа P содержит команду q30 -> q51 П . Тогда после выполнения этой команды K перейдет за один шаг в конфигурацию

  , показанную на этом рисунке справа. Следовательно, .

  Определение 9.4. Вычисление м.Т . на входе w — это конечная или бесконечная последовательность конфигураций такая, что K0=q0w — начальная конфигурация . Эта последовательность конечна, когда ее последняя конфигурация Kn= v1 qf v2 — заключительная. В этом случае вычисление назовем результативным, а слово v = v1 v2 — его результатом на входе w (всегда будем предполагать, что v не содержит пустых символов слева и справа).

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

  Скажем, что две м.Т . и эквивалентны, если они вычисляют одинаковые функции.

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

  Определение 9.6. Скажем, что м.Т . вычисляет частичную арифметическую функцию f: N k -> N , если для любого набора чисел (x1,x2, . ,xk) , на котором f определена, существует результативное вычисление на входе с результатом , а если , то вычисление на соответствующем входе бесконечно.

  Аналогичное определение можно дать и для других спосбов кодирования чисел (двоичного, десятичного и др.). Ниже мы покажем, что класс вычислимых функций не зависит от выбора одного из таких кодирований.

  Источник: intuit.ru