Том 37. Женщины-математики. От Гипатии до Эмми Нётер (Наварро) - страница 78
— Перечислимое множество (по историческим причинам также называется рекурсивно перечислимым): множество целых чисел 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 число Фибоначчи. Интересно, что эта теорема приводится только в третьем издании книги Воробьева и отсутствует в первых двух.