ТЬЮРИНГА МАШИНА

— математическое понятие, введенное как формальное уточнение интуитивного понятия алгоритма. Названо по имени англ. матем. А. Тьюринга (1912—54), который ввел его в 1936. Аналогичную концепцию машины позднее и независимо от Тьюринга ввел амер. математик Э. Пост (1897— 1954).

В каждой Т. м. есть следующие три части: 1) неограниченная в обе стороны лента, разделенная на ячейки; 2) управляющее устройство (УУ); 3) головка (Г).

Схема машины Тьюринга.

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

Совокупность сведений о состоянии УУ и записи на ленте машины (с указанием обозреваемой ячейки) наз. конфигурацией Т. м. Работа Т. м. состоит из тактов, в каждом из которых выполняется преобразование конфигурации, в которой Т. м. находится в данный момент времени в конфигурацию, в которой машина будет находиться в момент Это преобразование зависит только от состояния УУ и содержимого обозреваемой ячейки в момент t и заключается: а) в изменении состояния в некоторое состояние в замене буквы записанной в обозреваемой ячейке, некоторой буквой в сдвигании Г на одну ячейку влево или вправо (Г может и не сдвигаться). Такое преобразование наз. командой Т. м. Символически его записывают в виде где R — одна из букв Л, П, Н (буквой Л обозначают сдвиг влево, П — сдвиг вправо, Н — отсутствие сдвига).

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

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

слова в алфавите 22. Выделим во мн-ве Q некоторое (начальное) состояние Если Р — слово в алфавите то через обозначим конфигурацию следующего вида: на ленте записано слово обозревает первую слева непустую ячейку, УУ находится в состоянии Конфигурацию внда назовем начальной. Говорят, что Т. м. ЭЛ вычисляет словарную ф-цию если для любого слова Р работа машины над конфигурацией заканчивается в том и только в том случае, когда определена на Р и в конце работы на ленте записано слово .

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

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

Универсальная Т. м. V работает следующим образом: в начальный момент на ленту записывают код программы Т. м. и код исходной конфигурации К, на которой должна работать. Машина V работает над такой конфигурацией подобно человеку, который, зная программу , может такт за тактом выполнять работу над К, отыскивая каждый раз в программе ту команду, которую нужно выполнить в этом такте (U может делать это, учитывая все, что было сказано выше о кодировании программ и конфигураций). При этом, одному такту работы соответствуют несколько тактов машины U, которые ей нужны для отыскания и выполнения той команды, которую должна выполнить .

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

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

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

Приведем еще несколько утверждений, связанных с понятием моделирования: а) любую Т. м. можно моделировать на Т. м. с двумя состояниями, и существует Т. которую нельзя моделировать на Т. м. с одним состоянием; б) любую Т. м. можно моделировать на Т. м. с двумя символами внешнего алфавита; в) любую Т. м. можно моделировать на Т. м. с лентой, неограниченной только в одну сторону (считается, что Г такой машины не сходит с ленты, т. е. машина «чувствует», когда ее Г обозревает крайнюю ячейку).

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

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

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

Машины 2-го типа представляют собой естественные обобщения Т. м. и могут отличаться от них числом лент, головок и т. д. Рассмотрим некоторые из них. 1) Многоголовочные Т. м. Каждая из Г такой машины обозревает некоторую ячейку ленты. Работа машины заключается в изменении состояния УУ, содержимого каких-нибудь из обозреваемых ячеек (возможно, всех) и передвижения некоторых Г (возможно, всех) на одну ячейку влево или вправо (разные Г могут сдвигаться в разные стороны). Кроме того, должна быть предусмотрена однозначность записи в обозреваемые ячейки, когда несколько Г обозревают одну и ту же ячейку. 2) Многоленточные Т. м. На каждой ленте находится одна или несколько головок. Работа многоленточной машины зависит от содержимого всех обозреваемых ячеек на всех лентах и аналогична работе многоголовочной Т. м. 3) В Т. м. с многомерной лентой команды машины сохраняют прежний вид (добавляется только возможность сдвигов Г в нескольких направлениях). Любая из этих трех машин может быть моделирована на Т. м. обычного вида (с одной одномерной лентой и одной Г).

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

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

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

Если снабдить машину со входом еще и выходным каналом, по которому в некоторые моменты времени может выдавать символы из алфавита Д, та можно использовать для вычисления операторов, отображающих бесконечные последовательности бука из 2 в бесконечные последовательности букв из А (см. Поведение автоматов). Машины со входом под названием Т. м. с оракулом используют в другой ситуации для уточнения понятия сводимости одних алгоритм, проблем к другим (для уточнения понятия относительных вычислений предикатов и ф-ций). В этом случае работу машины со входом интерпретируют следующим образом. Фиксируют некоторое подмножество Q мн-ва состояний машины (т. н. «вопросительные состояния»), некоторый подалфавит В внешнего алфавита А и стандартный способ выделения слова в алфавите из конфигурации машины (напр., удалением из конфигурации всех принадлежащих R); наконец фиксируют некоторую ф-цию О (т. н. оракул), отображающую любое слово в алфавите R в непустой входной символ, машины .

Всякий раз, когда находится не в вопросительном состоянии, на вход поступает пустой символ. Если же машина приходит в состояние , то да вход поступает непустой символ который является значением , где Р — слово, получаемое с помощью из конфигурации, в которой машина находится в данный момент. Если при этом вычисляет некоторую ф-цию то говорят, что сводится к О. Описанная концепция вычислений с оракулом применима только в случае, когда оракул — ф-ция с конечным мн-вом значений (напр., предикат). Для общего случая, когда О — произвольная функция, которая отображает слова в алфавите R на слова в алфавите 2, возможно аналогичное, но технически более сложное описание.

Лит.: Трахтенброт Б. А. Алгоритмы и машинное решение задач. М., 1960; Мальцев А. И. Алгоритмы и рекурсивные функции. М., 1965 [библиогр. с. 375—3811; Клини С. К. Математическая логика. Пер. с англ. М., 1973 [библиогр. с. 451—465]; Эббинхауз Г. Д. [и др.]. Машины Тьюринга и рекурсивные функции. Пер. с нем. М., 1972.

М. К. Валуев.