Т. А. Сливина математическая логика и теория алгоритмов

Теорема 3. Существует перечислимое, но неразрешимое множество натуральных чисел.
Для доказательства теоремы, как это следует из теоремы Поста, достаточно привести пример такого множества натуральных чисел U, которое само было бы перечислимым, а его дополнение CU перечислимым не было.
Пусть М₀, M₁, M₂, ... – эффективное перечисление всех перечислимых множеств натуральных чисел, т.е. такое перечисление, что по любому пN можно восстановить само множество М.
Рассмотрим теперь алгоритм А, который последовательно перечисляет все элементы множества U. На шаге с номером (т,п) этот алгоритм вычисляет элемент с номером т множества М_n, и если этот элемент совпадает с n, то он относит его в множество U, т.е. пU  п  М_п .
Отсюда ясно, что множество CU отличается от любого перечислимого множества хотя бы одним элементом, т.к. CU состоит из всех таких элементов п, что nM_п . Поэтому CU не является перечислимым. Следовательно, согласно теореме Поста U не разрешимо.
Доказанная теорема фактически включает в себя в неявном виде теорему Гёделя о неполноте формальной арифметики, приведенную ранее без доказательства.


§ 3. Уточнение понятия алгоритма

В истории математики накопилось много случаев длительных и часто безрезультатных поисков тех или иных алгоритмов. При этом естественно возникало сомнение в существовании алгоритма.

Одним из ярких примеров такого случая является история решения десятой проблемы Д. Гильберта.
В 1900 году на втором международном математическом конгрессе в Париже немецкий математик Давид Гильберт огласил список 23 трудных проблем, на важность решения которых он обращал внимание математической общественности. Среди них была и следующая 10-ая проблема Гильберта: требуется выработать алгоритм, позволяющий для любого диофантова уравнения выяснить, имеет ли оно целочисленное решение.
Рассмотрим всевозможные диофантовы уравнения, т.е. уравнения вида Р = 0, где Р является многочленом с целочисленными коэффициентами. Такими будут, например, уравнения:
х² + у² - 2хz = 0,
10x⁵ + 7x² + 5 = 0,
из которых первое с тремя неизвестными, а второе с одним неизвестным. В общем случае рассматривают уравнения с любым числом неизвестных. Такие уравнения могут иметь целочисленные решения, а могут и не иметь.
Так, уравнение х²+у²-2xz=0 имеет бесконечное множество целочисленных решений, а уравнение 10x⁵ + 7x² + 5 = 0 таких решений не имеет.
Для частного случая диофантова уравнения с одним неизвестным давно известен алгоритм, позволяющий найти все его целочисленные решения. Установлено, что если уравнение

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

1. 
   Найти все делители числа a_n: d₁, d₂, ,.., d_n .
   
2. 
   Вычислить Р_п(х) для каждого из делителей числа а.
   

3) Если при некотором i из совокупности 1,2,...,k P_n(d_i ) ⁼0, то d_i - корень уравнения. Если при всех i = l,2,...,k P_n(d_i )  0, то уравнение не имеет целочисленных решений.
Поиски решения десятой проблемы Гильберта привлекли внимание многих математиков и длились около 70 лет. Только в 1968 году молодым математиком Ю. Матиясевичем было доказано, что нет алгоритма, дающего решение поставленной задачи.
Интуитивное определение алгоритма хотя и не строгое, но настолько ясное, что не дает оснований для сомнений в тех случаях, когда речь идет о найденном алгоритме решения конкретной задачи.
Положение существенно меняется, когда возникает алгоритмическая проблема, решение которой не найдено, и требуется установить, имеет ли она решение.
Действительно, в этом случае нужно либо доказать существование алгоритма, либо доказать его отсутствие.
В первом случае достаточно дать описание фактического процесса, решающего задачу. В этом случае достаточно и интуитивного понятия алгоритма, чтобы удостовериться в том, что описанный процесс есть алгоритм.
Во втором случае нужно доказать несуществование алгоритма, а для этого нужно точно знать, что такое алгоритм. Между тем для общего понятия алгоритма точного определения до тридцатых годов XX века не было, и поэтому выработка такого определения стала одной из важных задач современной математики. При формулировке этого определения пришлось преодолеть многие трудности.
Во-первых, такое определение должно было правильно отражать сущность интуитивного определения алгоритма.
Во-вторых, оно должно было быть совершенным с точки зрения формальной точности.
И наконец, различные исследователи этой проблемы исходили из разных технических и логических соображений, и вследствие этого было выработано несколько определений алгоритма. Однако со временем выяснилось, что все эти определения равносильны, т.е. определяют одно и то же понятие. Это и есть современное понятие алгоритма.
В подходах к определению понятия алгоритма можно выделить три основных направления.
Первое направление связано с уточнением понятия эффективно вычислимой функции. Этим занимались А. Черч, К. Гедель, С. Клини. В результате был выделен класс так называемых частично рекурсивных функций, имеющих строгое математическое определение. Анализ идей, приведших к этому классу функций, дал им возможность высказать гипотезу о том, что класс эффективно вычислимых функций совпадает с классом частично рекурсивных функций.
Второе направление связано с машинной математикой. Здесь сущность понятия алгоритма раскрывается путем рассмотрения процессов, осуществляемых в машине. Впервые это было сделано Тьюрингом, который предложил самую общую и вместе с тем самую простую концепцию вычислительной машины. Ее описание было дано Тьюрингом в 1937 году. При этом Тьюринг исходил лишь из общей идеи работы машины как работы вычислителя, оперирующего в соответствии с некоторым строгим предписанием.
Третье направление связано с понятием нормальных алгоритмов, введенным и разработанным российским математиком А. А. Марковым.