Тени разума. В поисках науки о сознании

Диофантовыми называются полиномиальные уравнения с каким угодно количеством переменных, все коэффициенты и все решения которых должны быть целыми числами. (Целые числа — это числа, не имеющие дробной части, например: …, -3, -2, -1, 0, 1, 2, 3, 4, …. Первым такие уравнения систематизировал и изучил греческий математик Диофант в третьем веке нашей эры.) Ниже приводится пример системы диофантовых уравнений:

6 + 2x ²- y ³= 0, 5xy - z ²+ 6 = 0, ²- + 2x - y + z - 4 = 0

Вот еще один пример:

6 + 2x ²- y ³= 0, 5xy - z ²+ 6 = 0, ²- + 2x - y + z - 3 = 0.

Решением первой системы является, в частности, следующее:

= 1, x= l, у= 2, z= 4,

тогда как вторая система вообще не имеет решения (судя по первому уравнению, число у должно быть четным, судя по второму уравнению, число zтакже должно быть четным, однако это противоречит третьему уравнению, причем при любом , поскольку значение разности ² - — это всегда четное число, а число 3 нечетно). Задача, поставленная Гильбертом, заключалась в отыскании математической процедуры (или алгоритма), позволяющей определить, какие системы диофантовых уравнений имеют решения (наш первый пример), а какие нет (второй пример). Вспомним (см. §1.5). что алгоритм — это всего лишь вычислительная процедура, действие некоторой машины Тьюринга. Таким образом, решением десятой проблемы Гильберта является некая вычислительная процедура, позволяющая определить, когда система диофантовых уравнений имеет решение.

Десятая проблема Гильберта имеет очень важное историческое значение, поскольку, сформулировав ее, Гильберт поднял вопрос, который ранее не поднимался. Каков точный математический смыслсловосочетания «алгоритмическое решение для класса задач»? Если точно, то что это вообще такое — «алгоритм»? Именно этот вопрос привел в 1936 году Алана Тьюринга к его собственному определению понятия «алгоритм», основанному на изобретенных им машинах. Примерно в то же время другие математики (Черч, Клин, Гёдель, Пост и др.; см. [ 135]) предложили несколько иные процедуры. Как вскоре было показано, все эти процедуры оказались эквивалентными либо определению Тьюринга, либо определению Черча, хотя особый подход Тьюринга приобрел все же наибольшее влияние. (Только Тьюрингу пришла в голову идея специфической и всеобъемлющей алгоритмической машины, — названной универсальноймашиной Тьюринга, — которая способна самостоятельно выполнить абсолютно любоеалгоритмическое действие. Именно эта идея привела впоследствии к созданию концепции универсального компьютера, который сегодня так хорошо нам знаком.) Тьюрингу удалось показать, что существуют определенные классы задач, которые не имеюталгоритмического решения (в частности, «проблема остановки», о которой я расскажу ниже). Однако самой десятой проблеме Гильберта пришлось ждать своего решения до 1970 года, когда русский математик Юрий Матиясевич (представив доказательства, ставшие логическим завершением некоторых соображений, выдвинутых ранее американскими математиками Джулией Робинсон, Мартином Дэвисом и Хилари Патнэмом) показал невозможность создания компьютерной программы (или алгоритма), способной систематически определять, имеет ли решение та или иная система диофантовых уравнений. (См. [ 72] и [ 89], глава 6, где приводится весьма занимательное изложение этой истории.) Заметим, что в случае утвердительного ответа (т.е. когда система имеет-таки решение), этот факт, в принципе, можно констатировать с помощью особой компьютерной программы, которая самым тривиальным образом проверяет один за другим все возможные наборы целых чисел. Сколько-нибудь систематической обработке не поддается именно случай отсутствия решения. Можно, конечно, создать различные совокупности правил, которые корректно определяли бы, когда система не имеет решения (наподобие приведенного выше рассуждения с использованием четных и нечетных чисел, исключающего возможность решения второй системы), однако, как показывает теорема Матиясевича, список таких совокупностей никогдане будет полным.