Том 37. Женщины-математики. От Гипатии до Эмми Нётер (Наварро) - страница 77
В 1950 году Джулия Робинсон, применив некоторые свойства уравнения Пелля, не смогла доказать, что определенное числовое множество, которое мы обозначим JR в честь Джулии Робинсон (его нельзя построить, но можно определить в терминах общей арифметики), является диофантовым (см. врезку, посвященную Алану Тьюрингу), но не вычислимым. Множество JR обладало некоторыми интересными свойствами — в частности, его элементы возрастали по экспоненциальному закону.
Доказать указанное свойство не удалось, однако эта гипотеза с высокой вероятностью считалась истинной. Далее будем называть эту гипотезу гипотезой JR. В 1959 году Мартин Дэвис и Хилари Патнем доказали, что при определенных условиях из гипотезы JR следует очень важный результат: любое рекурсивно перечислимое множество является диофантовым. Если выполняются начальные условия и гипотеза JR, то десятую проблему Гильберта можно считать решенной, и ответ на нее будет отрицательным.
* * *
НЕМНОГО ТЬЮРИНГА
При решении проблем разрешимости и вычислимости, а также логических задач обычно используются машины Тьюринга. Эти машины, придуманные английским ученым Аланом Тьюрингом (1912–1954), в действительности представляют собой идеальные математические абстракции вычислительных машин с бесконечной памятью. Представьте себе ящик с входным и выходным отверстиями, через которые проходит бумажная лента, разделенная на прямоугольные ячейки. В каждой ячейке записана цифра — 0 или 1. В крышке ящика есть смотровое отверстие, через которое в любой момент можно увидеть, какая цифра записана в ячейку. На каждом шаге цифру в ячейке можно заменить на 0 или 1. Аналогично, можно определить, куда следует переместить считывающее устройство на следующем шаге: влево или вправо. Новая записанная цифра и новое состояние машины зависят от текущего состояния машины, а следующий шаг (и следующее состояние) указаны в программе, записанной в управляющем устройстве. Программы различных машин Тьюринга отличаются. Прекратит ли машина работу, зависит оттого, что указано в программе. Может показаться, что от столь простого устройства не стоит ждать многого, однако потенциал машины Тьюринга огромен.
Простейшая схема работы машины Тьюринга.
Далее приведены три определения, тесно связанные с работами Джулии Робинсон и диофантовыми уравнениями. Они приводятся отдельно, так как используются в рассуждениях, самих по себе достаточно сложных.