Хоакин Наварро: Том 37. Женщины-математики. От Гипатии до Эмми Нётер

* * *

НЕМНОГО ТЬЮРИНГА

При решении проблем разрешимости и вычислимости, а также логических задач обычно используются машины Тьюринга. Эти машины, придуманные английским ученым Аланом Тьюрингом (1912–1954), в действительности представляют собой идеальные математические абстракции вычислительных машин с бесконечной памятью. Представьте себе ящик с входным и выходным отверстиями, через которые проходит бумажная лента, разделенная на прямоугольные ячейки. В каждой ячейке записана цифра — 0 или 1. В крышке ящика есть смотровое отверстие, через которое в любой момент можно увидеть, какая цифра записана в ячейку. На каждом шаге цифру в ячейке можно заменить на 0 или 1. Аналогично, можно определить, куда следует переместить считывающее устройство на следующем шаге: влево или вправо. Новая записанная цифра и новое состояние машины зависят от текущего состояния машины, а следующий шаг (и следующее состояние) указаны в программе, записанной в управляющем устройстве. Программы различных машин Тьюринга отличаются. Прекратит ли машина работу, зависит оттого, что указано в программе. Может показаться, что от столь простого устройства не стоит ждать многого, однако потенциал машины Тьюринга огромен.

Простейшая схема работы машины Тьюринга.

Далее приведены три определения, тесно связанные с работами Джулии Робинсон и диофантовыми уравнениями. Они приводятся отдельно, так как используются в рассуждениях, самих по себе достаточно сложных.

— Перечислимое множество (по историческим причинам также называется рекурсивно перечислимым): множество целых чисел Lназывается перечислимым, если существует машина Тьюринга такая, что если ввести в нее целое число, она остановится на 1, если указанное число принадлежит LЕсли указанное целое число не принадлежит L, машина может остановиться на 0 или не остановиться никогда.

— Вычислимое множество: множество Сназывается вычислимым, если существует программа машины Тьюринга такая, что для любого введенного целого числа машина останавливается на 1, если это число принадлежит С, в противном случае — на 0. Чуть менее понятное, но эквивалентное определение вычислимого множества таково: множество Сназывается вычислимым тогда и только тогда, когда Си его дополнение С ― являются перечислимыми. Очевидно, что любое вычислимое множество является перечислимым, но не наоборот.

— Диофантово множество: множество целых чисел Dназывается диофантовым, если его можно определить с помощью многочлена Р ( x 1 , x 2 , x t ) от переменных d, t, x 1, x 2…., x t>= 1 с целыми коэффициентами такого, что Робращается в ноль при присвоении целых значений x 1, x 2…., x tтогда и только тогда, когда dравно одному из элементов множества D.

Алан Тьюринг.

* * *

Всего годом позже в игру вступила Джулия Робинсон: ей удалось упростить задачу и устранить неудобные начальные условия, описанные Дэвис и Патнем. Ситуация была такова: если возможно множество вида JR, то десятая проблема Гильберта будет решена. Достаточно найти диофантово уравнение с определенными решениями, возрастающими экспоненциально, но это уравнение ускользало от математиков. Открытие было совершено в 1970 году, спустя почти 30 лет поисков. Юный математик Юрий Матиясевич из Советского Союза представил колоссальную систему диофантовых уравнений:

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

Матиясевич получил приведенные выше десять уравнений не случайно: он использовал в работе весьма остроумные методы. Ключевую идею математик заимствовал из теоремы, доказанной в 1942 году и затерянной на страницах третьего издания старенькой книжечки под названием «Числа Фибоначчи» советского математика Николая Воробьева. Для десяти приведенных выше уравнений выполняется равенство v = F 2 м , где F i— i -e число Фибоначчи. Интересно, что эта теорема приводится только в третьем издании книги Воробьева и отсутствует в первых двух.