WikiSort.ru - Не сортированное

Гипотеза Дэвиса

Слова Поста вдохновили студента Мартина Дэвиса на поиск доказательств неразрешимости десятой проблемы. Дэвис перешел от ее формулировки в целых числах к более естественной для теории алгоритмов формулировки в натуральных числах. Это две разные задачи, однако каждая из них сводится к другой. В 1953 году он опубликовал работу, в которой наметил путь решения десятой проблемы в натуральных числах.

Дэвис наравне с классическими диофантовыми уравнениями рассмотрел их параметрическую версию:

${\displaystyle P(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m})=0,}$

где многочлен ${\displaystyle P}$ с целыми коэффициентами можно разделить на две части — параметры ${\displaystyle a_{1},\ldots ,a_{n}}$ и переменные ${\displaystyle x_{1},\ldots ,x_{m}.}$ При одном наборе значений параметров уравнения может иметь решение, при другом решений может его не иметь. Дэвис выделил множество ${\displaystyle M}$ , которое содержит все наборы значений параметров (${\displaystyle n}$ ), при которых уравнение имеет решение:

${\displaystyle {\mathcal {h}}a_{1},\ldots ,a_{n}{\mathcal {i}}\in M\Longleftrightarrow \exists x_{1},\ldots ,x_{m}{\mathcal {f}}P(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m})=0{\mathcal {g}}.}$

Такую запись он назвал диофантовым представлением множества, а само множество также назвал диофантовым. Для доказательства неразрешимости десятой проблемы нужно было лишь показать диофантовость любого перечислимое множества, то есть показать возможность построения уравнения, которое имело бы натуральные корни ${\displaystyle x_{1},\ldots ,x_{m}}$ при ${\displaystyle {\mathcal {h}}a_{1},\ldots ,a_{n}{\mathcal {i}}}$ , принадлежащих к этому множеству: поскольку среди перечислимых множеств содержатся неразрешимые, то, взяв неразрешимое множество ${\displaystyle M}$ за основу, невозможно было бы получить общий метод, который бы ${\displaystyle n}$ определял, имеются ли в этом наборе уравнения натуральные корни. Все это привело Дэвиса к такой гипотезе:

Дэвис также сделал первый шаг — доказал, что любое перечислимое множество ${\displaystyle M}$ можно представить в виде:

${\displaystyle {\mathcal {h}}a_{1},\ldots ,a_{n}{\mathcal {i}}\in M\Longleftrightarrow \exists z\forall y<z\exists x_{1},\ldots ,x_{m}{\mathcal {f}}P(a_{1},\ldots ,a_{n},x_{1},\ldots ,x_{m},y,z)=0{\mathcal {g}}.}$

Это получило название «нормальная форма Дэвиса». Доказать свою гипотезу, избавившись от квантора всеобщности, ему на тот момент не удалось.