Лекция 4. Определимость перечислимых предикатов арифметическими $\Sigma_1$-формулами

Формулировка теоремы о $\Sigma_1$-определимости. Расширения сигнатуры с помощью $\Delta_0$-определений (в стандартной модели). $p$-ичное кодирование слов в конечном алфавите. Выразимость конкатенации. Кодирование машин Тьюринга и протоколов их вычислений. $\Sigma_1$-определимость предиката остановки данной машины Тьюринга.