Новое доказательство теоремы об экспоненциально диофантовом представлении перечислимых предикатов

Приведено основанное на новых идеях доказательство известной теоремы Дейвиса–Патнама–Робинсон о существовании у каждого перечислимого предиката экспоненциального диофантова представления. Исходным является задание перечислимого предиката с помощью машины Тьюринга, арифметизация работы которой дает сразу чисто экзистенциальную формулу. Новое доказательство может оказаться более удобным для изложения в курсе теории алгорифмов, ибо оно использует меньше сведений из теории чисел. Библ. 23 назв.