Утверждение "Всякое исчисление, порождающее формулы арифметики либо не адекватно, либо неполно" - это:
Множество всех истинных арифметических формул без параметров:
Множество всех истинных арифметических формул без параметров:
Инструкция "находясь в состоянии s и читая символ x, перейти в состояние p, напечатать символ y и сдвинуться вправо" порождает правило:
Арифметическое множество m-сводимо к множеству всех истинных арифметических формул без параметров:
Множество X из N разрешимо, если существует алгоритм:
Множество X - эффективно бесконечное, если алгоритм конструирования по любому n различных элементов из X:
Иммунное множество - это множество:
Среди перечислимых множеств множество, к которому m-сводится любое перечислимое множество X:
По любой вычислимой функции можно указать: