Сохраню тут мое сообщение с dxdy.ru, и там есть его окончание.
Раздел 1. Предварительная информация о диофантовых множествах и т.п.
Чтоб опираться на единую базу, я привожу необходимые определения и теоремы с их нумерацией из книги В.И.Игошин «Теория алгоритмов: Учебное пособие». ISBN 978-5-16-005205-2 (это издание из серии «Высшее образование», есть книга с таким же названием этого автора, но для среднего проф. образования).
Раздел 10.1. Десятая проблема Гильберта, Подраздел «Диофантовы множества и их связь с перечислимыми множествами».
Определение 1. Пусть
Определение 2. Перечислимые множества - это такие, которые могут быть порождены некоторым алгоритмом, или которые являются множеством значений некоторых вычислимых функций.
Приведу для справки и некоторые более базовые определения, на которые опирались изложенные выше определения:
Раздел 5.1 Нумерация алгоритмов и вычислимых функций, Подраздел «Вычислимые функции».
Определение 3. Область значений функции
Определение 4. Функция
Следующее определение соответствует Википедии (Статья «Класс NP») - оно эквивалентно определению через недетерминированную машину Тьюринга, но удобней для наших целей.
Определение 5. Язык L называется принадлежащим классу
Слово
При заданных соответствующих предикате
Проблема равенства
Если говорить технически (опираясь на тезис Чёрча), то вопрос состоит в поиске алгоритма, на вход которому подается текст соответствующего алгоритма
Две следующих теоремы и их номера переписаны из книги В.И.Игошин «Теория алгоритмов: Учебное пособие» (о ней сказано в начале сообщения). Раздел 10.1. Десятая проблема Гильберта, Подраздел «Диофантовы множества и их связь с перечислимыми множествами».
Теорема 10.1.1. Всякое диофантово множество является перечислимым множеством.
Теорема 10.1.2. Пусть
Это значит, что вместо любого алгоритма мы можем получить точно те же значения что и этот алгоритм (и никаких иных значений) из некоторого диофантова уравнения
Последняя теорема позволила элементарно решить Десятую проблему Гильберта (Теорема 10.1.3. в упомянутой только что книге) о неразрешимости диофантовых уравнений. Метод доказательства:
1. Строится алгоритм
1-а. Вычисляет произвольный заданный ему алгоритм, зависящий от одной переменной
1-б. Выдает в качестве своего результат только тот результат заданного ему алгоритма на заданном
2. Порожденное алгоритмом
3. Соответственно множеству
4. Это уравнение неразрешимо в силу п.2.
5. Если бы диофантовы уравнения были разрешимы, то подставляя произвольное число в
6. п.5 невозможен в силу п.4, поэтому диофантовы уравнения в общем случае неразрешимы.
Теорему 10.1.2 доказал Ю.В. Матиясевич, а базу для доказательства заложила группа американских математиков Р.Робинсон, Х.Путнам, Дж. Робинсон, М.Дэвис. Они свели задачу к доказательству диофантовости отношения
(продолжение - в следующей записи)