База ответов ИНТУИТ

Основы теории вычислимых функций

<<- Назад к вопросам

Утверждение "Любой алгоритм, перечисляющий множество формул арифметики порождает некоторую ложную формулу, либо не порождает некоторой истинной формулы" - это:

(Отметьте один правильный вариант ответа.)

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