Что можно и что невозможно делать с диофантовыми проблемами

В настоящем обзоре приводятся различные теоремы (полученные в основном специалистами по математической логике и теории алгоритмов), устанавливающие невозможность алгоритмов для решения тех или иных диофантовых проблем. Техника, развитая для получения таких “отрицательных” результатов, зачастую позволяет доказать и много “положительных” теорем о возможности сформулировать диофантовы проблемы со специальными свойствами. В этом обзоре приведен также ряд вопросов, остающихся открытыми.