Машина Тьюринга

Electronic philosophical encyclopedia article
share the uri

Машина Тьюринга: определение

Машина Тьюринга – абстрактная математическая модель вычислительной машины.

История. Статья Тьюринга 1936 года

Весной 1935 Тьюринг прослушал курс лекций по основаниям математики М. Ньюмана. В завершение курса были подробно рассмотрены сформулированные Д. Гильбертом на международном конгрессе 1928 года проблемы установления непротиворечивости, полноты и разрешимости аксиоматических теорий математики. Также была рассмотрена доказанная К. Гёделем в 1931 теорема о неполноте, из которой следовал отрицательный ответ на вопрос о возможности доказательства непротиворечивости и полноты достаточно богатых математических теорий. Однако все еще сохранялась надежда, что может существовать универсальный метод, который позволял бы по любому математическому утверждению в языке логики предикатов первого порядка установить, является оно доказуемым или нет. Это была остававшаяся открытой проблема разрешимости (Entscheidungsproblem). Именно она и привлекла внимание Тьюринга.

В результате напряженной работы в конце 1935 – начале 1936 г. Тьюринг построил строгую логико-математическую модель того, что неформально можно описать как вычисление посредством механически детерминированного процесса. С помощью этой модели он доказал, что проблема разрешимости не имеет решения. Статья с подробным изложением полученных результатов была написана в апреле 1936 [Turing, 1936–1937], а опубликована в двух частях 30 ноября и 23 декабря 1936 [Copeland, 2004].

Одновременно с Тьюрингом над этой же проблемой работал американский логик А. Чёрч. Средствами специально построенного λ-исчисления он доказал, что неразрешимые проблемы существуют [Church, 1936b] и связал это с поставленной Гильбертом проблемой разрешения [Church, 1936a]. Тьюринг узнал о работах Чёрча лишь в мае 1936 и в дополнении к своей статье, написанном в августе 1936, показал эквивалентность предложенного им понятия вычислимости и вычислимости в терминах λ-исчисления. Когда публикация Тьюринга вышла в свет, именно Чёрч первым ввел в научный обиход термин «машина Тьюринга» [Church, 1937].

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

  1. Была предложена строгая формализация того, что ранее на интуитивном уровне именовалось «вычислением с финитными средствами». Была построена математическая модель абстрактного устройства, способного производить различные вычисления, что дало толчок развитию теории вычислимости как новой математической дисциплины.

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

  3. Тьюринг доказал неразрешимость проблемы остановки (halt problem), суть которой заключается в том, чтобы по описанию произвольной вычислительной машины (алгоритма) определить, завершится когда-нибудь производимый ею процесс вычисления или нет. Было показано, что неразрешимые математические проблемы существуют и конкретный их пример – проблема остановки. Была доказана неразрешимость проблемы появления на рабочей ленте конкретной машины Тьюринга конкретного символа (printing problem). Еще одно следствие существования неразрешимых проблем, открытых Тьюрингом, заключается в том, что не существует универсального метода, который позволял бы по произвольной программе проверить, действительно ли она производит именно те вычисления, для которых была составлена?

  4. Был предложен ряд аргументов в пользу того, что позже было названо «тезисом Тьюринга». Суть его заключалась в утверждении, что машины Тьюринга являются адекватной формализацией любых вычислений с финитными средствами, которые способен выполнить человек. Ранее Клини и Чёрч уже высказали предположения, что их формализации вычислимых функций средствами общерекурсивных функций и λ-исчисления адекватно представляют класс всех эффективно вычислимых функций, однако Гёдель не посчитал представленные аргументы достаточно убедительными и только после публикации Тьюринга согласился принять то, что в будущем получило название «тезиса Чёрча – Тьюринга».

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

Church A. A Note on the Entscheidungsproblem // The Journal of Symbolic Logic. 1936a. Vol. 1. No. 1. P. 40–41.

Church A. An Unsolvable Problem of Elementary Number Theory // American Journal of Mathematics. 1936b. Vol. 58. No. 2. P. 345–363.

Church A. Review // The Journal of Symbolic Logic. 1937. Vol. 2. No. 1. P. 42–43.

Copeland J. Computable Numbers: A Guide // The Essential Turing / Ed. by B. Jack Copeland. Oxford; N. Y., 2004. P. 5–57.

Hodges A. Alan Turing: The Enigma. L.; N. Y., 1983.

Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936–1937. Vol. 42. P. 230–265.

Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction // Proceedings of the London Mathematical Society – London Mathematical Society. 1938. Vol. S2-43. Iss. 6. P. 544–546.

Машина Тьюринга: принципы устройства

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

  • стереть что-то из того, что написано на странице;

  • написать что-то на странице;

  • перевернуть страницу блокнота вперед;

  • перевернуть страницу блокнота назад.

После каждого из этих действий внутреннее состояние вычислителя может измениться.

Действия вычислителя связаны с определенным внутренним состоянием, которое после каждого действия может измениться. При этом внутренние состояния не имеют ничего общего с психологией человека-вычислителя, это просто готовность выполнять другие действия, и потому они могут считаться всего лишь некоторыми маркёрами. Например, при умножении чисел столбиком мы умножаем первое число последовательно на десятичные разряды второго числа и записываем это с отступом, а потом суммируем полученные числа. Для того, чтобы перейти к суммированию, вычислитель должен изменить свое внутреннее состояние, сказав себе: «А теперь я буду суммировать».

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

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

После такого уточнения все возможные элементарные действия человека-вычислителя можно описать четырьмя видами правил. Обозначим множество используемых символов посредством = {s0,…,sn}, где s0 – выделенный пустой символ (аналог пробела в современных текстовых редакторах), а множество возможных внутренних состояний – посредством = {q0,…,qm}. Четыре вида правил следующие:

  • qi,sj → E,qh;

  • qi,s0 → Psk,qh;

  • qi,sj → R,qh;

  • qi,sj → L,qh.

Смысл первого правила заключается в том, что если вычислитель находится в состоянии qi и текущая клетка ленты содержит символ sj, то он стирает его (заменяет на пустой символ s0), изменяя внутреннее состояние на qh.

Смысл второго правила заключается в том, что если вычислитель находится в состоянии qi и текущая клетка ленты содержит пустой символ s0, то он печатает символ sk, изменяя внутреннее состояние на qh.

Смысл третьего правила заключается в том, что если вычислитель находится в состоянии qi и текущая клетка ленты содержит символ sj, то он смещает фокус внимания на одну клетку вправо и изменяет внутреннее состояние на qh. Аналогично для четвертого правила, но в этом случае смещение происходит на оду клетку влево.

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

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

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

Image1

Для описания машины достаточно следующих формальных параметров:

  • исходного конечного алфавита символов = {s0,…,sn};

  • конечного набора ярлыков внутренних состояний = {q0,…,qm};

  • четырех действий: стереть (E), напечатать (P), перейти к правой ячейке (R) и перейти к левой ячейке (L);

  • конечного набора правил;

  • состояния ленты – конечного набора ее ячеек с написанными в них символами.

Вычисление начинается с того, что в начальном состоянии q0 машина сканирует самую левую ячейку с данными, записанными на ленте. Если данных нет, а такое возможно, то вычисление начинается со сканирования выделенной пустой ячейки. Вычисление заканчивается, когда для текущего внутреннего состояния машины qi и сканируемого в текущей ячейке символа sj нет ни одного правила, левая часть которого имела бы вид qi,sj  Результатом вычисления является содержимое ячеек ленты после остановки машины. Таким образом, мы получаем простое и в то же время строгое математическое уточнение понятия вычисления.

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

Пример 1.

  • Алфавит символов: S={s0,0}.

  • Внутренние состояния: Q={q0}.

  • Правила:

    • q0,s0 → P0,q0

Эта машина, в начальном состоянии ленты которой все ячейки пусты, напечатает символ “0” и остановится.

Если к набору ее правил добавить еще одно “q0,0  R,q0”, то она, никогда не останавливаясь, будет печатать бесконечную последовательность символов “0”.

Пример 2.

  • Алфавит символов: S={s0, 0, 1}.

  • Внутренние состояния: Q={q0, q1}.

  • Правила:

    • q0,s→ P0,q0

    • q0,0 → R,q1

    • q1,s→ P1,q1

Эта машина, в начальном состоянии ленты которой все ячейки пусты, напечатает в двух последовательных ячейках символы “0” и “1” и остановится.

Если к набору ее правил добавить еще одно “q1,1  R,q0”, то она, никогда не останавливаясь, будет печатать бесконечную последовательность символов “0” и “1”.

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

Для простоты число n на входе вычисления будем представлять с помощью n+1 символов “1”, записанных последовательно в соседних ячейках. Если число n равно 0, то оно записывается одним символом “1”.

Результат вычисления функции fM определим следующим образом:

fM(n)={числосимволов“1”наленте,есливычислениезавершаетсянеопределено,есливычислениенезавершается}

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

Пример 3.

  • Алфавит символов: S={s0, 1}.

  • Внутренние состояния: Q={q0, q1}.

  • Правила:

    • q0,1 → R,q0

Если в начальном состоянии ленты этой машины записаны подряд n символов “1”, то она последовательно проходит через них, доходит до первой пустой ячейки и останавливается. В соответствии с нашим соглашением о функциях это будет означать, что данная машина M вычисляет функцию fM(n)=n+1.

Если к набору правил добавить еще одно “q0,s P1,q1”, то машина последовательно проходит через все ячейки с “1”, доходит до первой пустой ячейки, печатает в ней символ “1” и останавливается. В соответствии с нашим соглашением о функциях это будет означать, что машина M вычисляет функцию fM(n)=n+2.

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

Copeland J. Computable Numbers: A Guide // The Essential Turing / Ed. by B. Jack Copeland. Oxford; N. Y., 2004. P. 5–57.

Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936–1937. Vol. 42. P. 230–265.

Клини С.К. Введение в метаматематику. М., 1957.

Мендельсон Э. Введение в математическую логику. М., 1976.

Эббинхауз Г.Д., Якобс К., Ман Ф.К., Хермес Г. Машины Тьюринга и рекурсивные функции. М., 1972.

Универсальная машина Тьюринга

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

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

Тьюринг показал, как с помощью конечного набора символов алфавита можно закодировать любую машину M, т.е. используемый ею набор символов, набор внутренних состояний и список правил. Обозначим закодированную машину M как (M) , пусть машина M в применении ко входным данным n вычисляет функцию fM(n) . Тьюринг не просто высказал идею, а показал, как определить такую машину U, что, если на ее рабочей ленте размещен код (M) и данные n, то она сначала распознает код (M) , затем распознает входные данные n, и начинает применять к ним уже не свои правила, а правила машины M. Таким образом она вычисляет функцию fU((M),n) , результат которой совпадает с результатом вычисления функции fM(n) , т.е. fU((M),n)=fM(n) .

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

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

Hodges A. Alan Turing and the Turing Machine // The Universal Turing Machine. A Half-Century Survey / Ed. by R. Herken. Hamburg; Berlin, 1988. P. 3–16.

Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936–1937. Vol. 42. P. 230–265.

Тезис Тьюринга

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

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

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

В-третьих, он также показал, как с произвольной точностью до любого знака после запятой можно вычислить любые числа, являющиеся корнями алгебраических уравнений, числа e и π, являющиеся пределами последовательностей e=1+1+1/2!+1/3!+1/5!  и π=4×(11/3+1/5) , и др.

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

Уже после публикации работы Тьюринга были проведены дополнительные исследования, призванные подтвердить или опровергнуть данный тезис. Вместо машины Тьюринга с бесконечной лентой в обе стороны были проанализированы машины с бесконечной лентой лишь в одну сторону. Оказалось, что такое ограничение не приводит к изменению множества вычислимых функций. Были проанализированы машины Тьюринга с несколькими сканирующими, считывающими и печатающими головками. Множество вычислимых функций не изменилось. Были рассмотрены варианты с несколькими лентами и различными по величине наборами символов, но результат остался прежним. С тех пор были предложены другие подходы к аксиоматизации эффективно вычислимых функций. Наиболее известны нормальные алгорифмы Маркова [Марков, Нагорный, 1984] и машины с неограниченными регистрами [Катленд, 1983]. Было доказано, что и для них множество вычислимых функций совпадает с множеством функций, вычислимых на машинах Тьюринга. Более подробно тезис Тьюринга и аргументы в его пользу анализируются в работе [Клини, 1957, c. 317-342].

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

Copeland J. Computable Numbers: A Guide // The Essential Turing / Ed. by B. Jack Copeland. Oxford; N. Y., 2004. P. 5–57.

Turing A.M. Computability and λ-definability // The Journal of Symbolic Logic. 1937. Vol. 2. No. 4. P. 153–163.

Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936–1937. Vol. 42. P. 230–265.

Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М., 1983.

Клини С.К. Введение в метаматематику. М., 1957.

Марков А.А., Нагорный Н.М. Теория алгорифмов. М., 1984.

Проблема остановки и проблема разрешимости

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

Формально проблема остановки – это ответ на вопрос о существовании характеристической функции, задаваемой следующими условиями:

fS((M),x)={1,еслиfM(x)определена0,еслиfM(x)неопределена}

Если машина M в применении ко входным данным x останавливается, т.е. значение функции fM(x)  определено, то значением функции fS((M),x) является 1. В противном случае, если машина M в применении ко входным данным x никогда не завершает процесс вычисления, то значением функции fS((M),x)  является 0.

Допустим, что характеристическая функция fS(x,y) вычислима, т.е. существует машина S, которая ее вычисляет. Тогда мы можем определить машину D, которая будет вычислять функцию fD(x) по следующему правилу:

fD(x)={1,еслиfS(x,x)=0неопределена,еслиfS(x,x)=1}

Это приводит к противоречию, если применить машину D к ее собственному закодированному описанию (D) .

fD((D))=1fS((D),(D))=0fD((D))неопределена

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

Тьюринг показал также, что не существует вычислимой характеристической функции, которая по произвольной машине и произвольному набору исходных данных распознавала бы, печатает ли она в ходе вычисления на ленте конкретный символ, например “0”. Если бы такая вычислимая характеристическая функция существовала, то существовала бы вычислимая характеристическая функция и для проблемы остановки. А поскольку такой функции нет, то нет вычислимой характеристической функции и для появления на рабочей ленте конкретного символа (printing problem).

В 11 параграфе статьи Тьюринга дается ответ на вопрос о проблеме разрешимости для математики.

Для этого в языке логики предикатов первого порядка он определяет формулу Un(m), смысл которой заключается в том, что машина m на некотором шаге вычисления печатает на рабочей ленте символ “0”. Затем он показывает, что формула Un(m) доказуема в логике предикатов первого порядка, если и только если машина m на некотором шаге вычисления печатает на рабочей ленте символ “0”. Если бы существовал метод, которые позволял бы по каждой формуле определить, доказуема она или нет, то проблема появления на рабочей ленте символа “0” была бы разрешима вопреки ранее доказанной теореме. Отсюда следует, что не существует такой машины, которая могла бы по произвольной формуле языка первого порядка определить, доказуема она или нет. Таким образом, была окончательно опровергнута уверенность Гильберта в том, что в математике нет непознаваемого (Ignorabimus) [Гильберт, 1969, c. 22].

Copeland J. Computable Numbers: A Guide // The Essential Turing / Ed. by B. Jack Copeland. Oxford; N. Y., 2004. P. 5–57.

Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936–1937. Vol. 42. P. 230–265.

 

Гильберт Д. Математические проблемы // Проблемы Гильберта / Под ред. П.С. Александрова. М., 1969. С. 11–64.

Church A. A Note on the Entscheidungsproblem // The Journal of Symbolic Logic. 1936a. Vol. 1. No. 1. P. 40–41.

Church A. An Unsolvable Problem of Elementary Number Theory // American Journal of Mathematics. 1936b. Vol. 58. No. 2. P. 345–363.

Church A. Review // The Journal of Symbolic Logic. 1937. Vol. 2. No. 1. P. 42–43.

Copeland J. Computable Numbers: A Guide // The Essential Turing / Ed. by B. Jack Copeland. Oxford; N. Y., 2004. P. 5–57.

Hodges A. Alan Turing and the Turing Machine // The Universal Turing Machine. A Half-Century Survey / Ed. by R. Herken. Hamburg; Berlin, 1988. P. 3–16.

Hodges A. Alan Turing: The Enigma. L.; N. Y., 1983.

Turing A.M. Computability and λ-definability // The Journal of Symbolic Logic. 1937. Vol. 2. No. 4. P. 153–163.

Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem // Proceedings of the London Mathematical Society. 1936–1937. Vol. 42. P. 230–265.

Turing A.M. On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction // Proceedings of the London Mathematical Society – London Mathematical Society. 1938. Vol. S2-43. Iss. 6. P. 544–546.

 

Гильберт Д. Математические проблемы // Проблемы Гильберта / Под ред. П.С. Александрова. М., 1969. С. 11–64.

Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М., 1983.

Клини С.К. Введение в метаматематику. М., 1957.

Марков А.А., Нагорный Н.М. Теория алгорифмов. М., 1984.

Мендельсон Э. Введение в математическую логику. М., 1976.

Эббинхауз Г.Д., Якобс К., Ман Ф.К., Хермес Г. Машины Тьюринга и рекурсивные функции. М., 1972.

Шалак В.И.