Изменения

Пусть дано множество <tex>M</tex> натуральных чисел и нужно найти алгоритм, который по каждому натуральному <tex>n</tex> определяет, принадлежит это <tex>n</tex> множеству <tex>M</tex> или нет.Такой алгоритм существует тогда и только тогда, когда множество <tex>M</tex> разрешимо. Для отрицательного решения десятой проблемы Гильберта достаточно было доказать диофантовость каждого перечислимого множества, то есть по каждому перечислимому множеству <tex>M</tex> уметь строить такое диофантово уравнение, <tex>P(y,x_1...x_k)=0</tex>, которое имело бы натуральные решения <tex>x_1...x_k</tex> для всех <tex>y</tex>, принадлежащих <tex>M</tex> и только для таких <tex>y</tex>. Тогда, взяв в качестве <tex>M</tex> перечислимое, но неразрешимое множество, можно было бы получить, что для соответствующего уравнения <tex>P(y,x_1...x_k)=0</tex> нет общего алгоритма, который по каждому натуральному <tex>y</tex> давал бы ответ на вопрос о существовании у этого уравнения натуральных решений. Если бы этот алгоритм существовал, то можно было бы за конечное число шагов узнать, имеет ли уравнение <tex>P(0,x_1...x_k)=0</tex> решение, то есть принадлежит ли число <tex>0</tex> множеству <tex>M</tex>, имеет ли уравнение <tex>P(1,x_1...x_k)=0</tex> решение и так далее. Получилось бы, что существует алгоритм, который по каждому натуральному <tex>y</tex> за конечное число шагов определяет, принадлежит <tex>y</tex> множеству <tex>M</tex> или нет. Тогда, в соответствии с тезисом Черча, множество <tex>M</tex> было бы разрешимым.