8.2. Нумерация кортежей.

1. Канторова нумерация.

Рассмотрим двумерные кортежи < 0, 0>, < 0, 1>, < 1, 0> и т.д.

Cantor (a, b) = ((a + b)² + 3a + b)/2.

2. Геделево кодирование.

Рассмотрим произвольный кортеж < a₁, … , a_n > и взаимно простые числа b₁, …, b_n , причем a_i < b_i. Известна теорема об остатках чисел, представляемых в виде пары чисел. По этой теореме существует число a, такое что a_i = rem(a, b_i). Тогда для кодирования любого кортежа достаточно иметь a, b и n переменных в кортеже. В теореме рекурсий кодировки нужны для того, чтобы избавиться от нескольких переменных и перейти к одной.

Пример.

Рассмотрим полином 9(m² + 7v²)² + 7( r² + 7s²)² = 2.

Тривиальное решение очевидно: m = r = 1, v = s = 0.

Существует также нетривиальное решение  числа длиной 18 и 20 знаков.

Определение.

Уравнение

U(Aⁿ, k, ^w) = 0 (1)

называется универсальным уравнением, если для произвольного диафантова уравнения

D(Aⁿ, X^m) = 0 (2)

можно указать такое k^D, что уравнение (2) разрешимо относительно X^m в точности при тех же значениях параметра Aⁿ, при которых уравнение

U(Aⁿ, k^D, ^w) = 0 (3)

разрешимо относительно ^w,

или

уравнение (3) является диафантовым представления множества (2), т.е. по любому уравнению можно найти число, которое, будучи подставлено в универсальное уравнение, дает то же диафантово множество.

Теорема 8.3.

Универсальное диафантово уравнение существует.

• Доказательство не приводится, но оно существует. 

Теорема 8.4.

Существует диафантово множество с недиафантовым дополнением.

• Рассмотрим универсальное диафантово уравнение U₁(a, a, X^m) = 0. Это уравнение задает некоторое диафантово множество ₁.

Пусть ₁  диафантово дополнение _1. Тогда существует его представление в виде полинома. Следовательно, существует k^D, который его кодирует.

Рассмотрим множество, определяемое уравнением U(k^D, k^D, X^m) = 0 (1). Разрешимо ли это уравнение?

1. Если оно разрешимо, то k^D ₁, но в то же время k ₁. ( Т.к. уравнения такого вида задают ₁).

2. Если оно неразрешимо, то k₁, но и k₁.

Значит, ₁  недиафантово.

Определение.

Уравнение U₀(k, ^m) = U₁(, k ^m) - это универсальное диафантово уравнение, но без параметров.

₀ = { t | U(t, ^m) = 0 } – диафантово множество.

₀ - это множество кодов уравнений без параметров, имеющих решения.

Утверждение.

₀ - не диафантово.

10-ая проблема Гильберта.

Проблема “x  ₀” - неразрешима.

1) По любому диафантову уравнению можно построить либо МНР, либо машину Тьюринга, которая останавливается () и выдает кортеж  a₁, .. a_n  тогда и только тогда, когда (1) разрешимо относительно X^m.

Эта функция вычислима ( С), т.е. любое диафантово множество является полуразрешимым (по Тьюрингу или на МНР).

2) Любое полуразрешимое по Тьюрингу множество является диафантовым.

Иначе: для любой машины Тьюринга (М), полуразрешающей некое множество, можно эффективно построить диафантово уравнение

D_M (p,Xⁿ) = 0 (2)

так, что если p – код некой конфигурации, то (2) разрешимо относительно Xⁿ тогда и только тогда, когда М, начав работу в этой конфигурации, останавливается через конечное число шагов.

 Конфигурацию мы можем запомнить в одном числе и пошаговое исполнение записать в виде полинома. 

Теорема 8.5. Матиясевича.

Все полуразрешимые (рекурсивно перечислимые) множества натуральных чисел диафантовы.

 без доказательства 

₀ – не диафантово  неразрешимо  “ x  ₀ “ неразрешимо.

Следствие.

Множество натуральных чисел является рекурсивно перечислимым тогда и только тогда, когда оно является множеством неотрицательных значений некоторого многочлена p(Xⁿ) c целыми коэффициентами и Xⁿ  Nⁿ.

Следствие.

Cуществует универсальный многочлен U₁(a, k, Xⁿ ) такой, что для любого рекурсивно перечислимого множества A  k_A : a  A   Xⁿ [U ₁(a, k_A, Xⁿ) = 0]

Следствие.

Cуществует универсальный многочлен V₁( k, Xⁿ) такой, что для любого рекурсивно перечислимого множества A  k_A : A является множеством натуральных значений многочлена V₁( k_A, Xⁿ) , Xⁿ  Nⁿ ( или Zⁿ).

Проблему “a  W_a” можно заменить на диафантово определение множества, а если “a  W_a” неразрешима, то множество недиафантово.

8.3. Разрешимость в рациональных числах.

Проблема распознавания наличия рациональных решений произвольных диафантовых уравнений и проблема распознавания наличия решений в однородных диафантовых уравнениях в целых числах эквивалентны.

Если n=1  p(x) = 0, корень должен быть делителем свободного члена. Перебираем все делители как корни , следовательно, знаем, существует решение или нет , значит, задача разрешима.

Теорема ( следствие из теоремы Штурма).

1) Cуществует эффективная процедура вычисления числа вещественных корней многочлена с целыми коэффициентами.

2) Предикат “ P(X) имеет корень на [a,b]” разрешим ,

a, b и все коэффициенты  Q.

Обобщение (теорема Тарского).

Предикат “D(x₁ , …x_m)=0 c вещественными x₁ , …x_m” разрешим.

Теорема 8.6.

1) Пусть F₀ – класс функций от нескольких переменных, который можно построить с помощью суперпозиции из 1, +, , *, sin.

Утверждение.

Не существует способа узнать, разрешимо ли в вещественных числах :

 Ф  F₀ Ф(X^m) = 0 (в Q)

2) Добавив в список функций еще и abs, получим, что проблема “Ф=0” неразрешима.

3) Если взять 1, +, -, /, sin : не существует способа, который по  Ф  F₀ определял бы сходимость интеграла

4) По системе диафантовых уравнений общего вида задача о существовании единственного решения на интервале [0,1] неразрешима.

Глава II . Эффективные алгоритмы

Введение.

0.1. Критерии оценки алгоритмов.

Чаще всего для оценки алгоритмов используют порядок роста необходимых для решения задачи времени и емкости памяти при увеличении входных данных.

Определение.

С каждой конкретной задачей связывается некоторое число, называемое ее размером, которое выражает меру количества входных данных.

Например, размером задачи умножения матриц может быть наибольший размер матриц-сомножителей. Размером задачи о графах может быть число ребер данного графа.

Емкость - S(n) интересно поведение при n  .

Время - T(n)

Определение.

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

Определение.

Поведение временной сложности в пределе при увеличении размера задачи называется асимптотической временной сложностью. Сложность имеет смысл с точностью до константы.

Аналогично определяются емкостная сложность и асимптотическая емкостная сложность.

Именно асимптотическая сложность алгоритма определяет размер задач, которые можно решить этим алгоритмом.

Определение.

Если алгоритм обрабатывает входы размера n за время cn², где c - некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n²) (читается “порядка n² ”).

Точнее, неотрицательная функция g(n) есть O(f(n)), если существует такая постоянная c, что

g(n)  cf(n) для всех, кроме конечного (возможно, пустого) множества, неотрицательных значений n.

Важно, что используются натуральные числа.

Часто встречаются значения сложности log₂ n, n, n log₂ n, n^k , 2ⁿ;

Для определения времени и памяти вводится вычислительная модель , которая должна быть адекватна реальной ЭВМ.