Мартін Девіс

Слова Поста надихнули студента Мартіна Девіса на пошук доказів нерозв'язності десятої проблеми. Девіс перейшов від її формулювання в цілих числах до більш природного для теорії алгоритмів формулювання в натуральних числах. Це дві різні задачі, проте кожна з них зводиться до іншої. У 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}}.}$

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