Здравствуйте, GhostCoders, Вы писали:

GC>Интересно. То есть Матиясевич ссылается на доказательство Тьюринга при доказательстве невозможности решений диафантовых уравнений в общем виде?

Теорема уже была доказана для экспоненциальных диофантовых уравнений (которые помимо сложения и умножения, допускают ещё и возведение в степень, где показатель может содержать переменную). Матиясевич нашёл послединию недостающую часть, показав что даже вопрос о наличии решений для более узкого класса обычных диофантовых уравнений алгоритмически неразрешим. Я советую почитать его книгу, где он, начиная с математики школьного уровня, излагает теорию алгоритмов и диофантовых уравнений, и приводит полное доказательство неразрешимости 10-й проблемы Гильберта:

Ю. В. Матиясевич. Десятая проблема Гильберта. — М.: Наука: Физико-математическая литература, 1993. — (Математическая логика и основания математики; выпуск № 26). — ISBN 502014326X.