Основы теории алгоритмов. Часть 1

Множество простых чисел является

• рекурсивным и перечислимым
• только рекурсивным
• замкнутым
• только перечислимым

Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется

• временным ресурсом
• геделевским номером
• характеристической
• длиной программы

Функция вычисляется по формуле

Если множество не является множеством значений никакой функции, то оно

• нерекурсивно и неперечислимо
• рекурсивно, но не перечислимо
• нерекурсивно, но рекурсивно перечислимо
• рекурсивно, и не перечислимо

Если и рекурсия проводится по , то функция равна

• x+z
• 0

Установление соответствия между элементарными высказываниями формальной теории и содержательными высказываниями некоторой предметной области называется

• интерпретацией теории
• порождающей грамматикой
• эффективной процедурой
• классом функторов

Любая неразрешимая алгоритмическая проблема дает пример множества

• невычислимого
• неперечислимого
• неразрешимого
• несчетного

Если , то функция в рекуррентной формуле равна

• m!
• m+1
• m+n+1
• m(n+1)

Функция является

• частично вычислимой
• рекурсивной
• общерекурсивной
• вычислимой

Функция, равная единице тогда и только тогда, когда предикат истинен, называется

• характеристической
• частично рекурсивной
• примитивно вычислимой
• вычислимой

Множество номеров самоприменимых машин Тьюринга

• неперечислимо, но разрешимо
• рекурсивно перечислимо и разрешимо
• рекурсивно перечислимо, но не разрешимо
• ни перечислимо, ни разрешимо

Существует команд машины Тьюринга

• 3 типа
• 2 типа
• 4 типа
• 8 типов

Осмысленные конечные последовательности символов из алфавита L называются

• словарем
• командами
• утверждениями
• программой

Утверждение формально записывается как

Множество доказуемых утверждений формальной системы арифметики

• открыто
• замкнуто
• разрешимо
• неразрешимо

Геделевский номер, равный , имеет функция

Множество, если оно является множеством значений некоторой вычислимой функции, называется

• эффективным
• рекурсивно перечислимым
• разрешимым
• вычислимым

Если и рекурсия проводится по переменной , то функция равна

• m+y
• 1
• m+x

Пусть R — рекурсивность, а P — рекурсивная перечислимость. Тогда

Множество натуральных чисел является

• рекурсивным и перечислимым
• только перечислимым
• простейшим
• только рекурсивным

Если A рекурсивно, а B — рекурсивно перечислимо, то _____ рекурсивно

w-непротиворечивая формальная система является

• полной
• неполной
• разрешимой
• истинной

Выражением называется

• исходная ситуация
• набор команд
• внутреннее состояние
• конечная последовательность символов

Множество составных чисел является

• только перечислимым
• рекурсивным и перечислимым
• только рекурсивным
• порождающим

Функция является примитивно рекурсивной, если она получается из набора исходных функций с помощью оператора: 1) рекурсии; 2) ограниченной минимизации; 3) подстановки — из перечисленного

• 1 и 2
• 1
• 1 и 3
• 1, 2 и 3

Утверждение арифметики Пеано называется неразрешенным, если оно

• и его отрицание опровержимы
• и его отрицание w-противоречивы
• истинно, но недоказуемо
• противоречит системе аксиом

Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру

• К. Гёдель
• А. Тьюринг
• А. Марков
• Д. Гильберт

Частично вычислимая функция

• это частный случай вычислимой
• вычисляется с ограниченной точностью
• может быть продолжена до вычислимой
• не везде совпадает с вычислимой

Теория алгоритмов является частью

• теории чисел
• математической логики
• математического анализа
• численных методов

Выражение является

• машиной Тьюринга
• командой
• исходной ситуацией
• элементом алфавита

Теорема Геделя о неполноте арифметики поколебала оптимистические надежды Гильберта на полное решение вопросов оснований математики с помощью

• машины Тьюринга
• конструктивисткой теории
• нормализации алгоритмов
• аксиоматического метода

Каждая п.р.ф имеет число номеров

• бесконечное
• небольшое
• ограниченное
• индивидуальное

Всякая вычислимая функция является вычислимой по Тьюрингу согласно

• теореме Гёделя
• тезису Чёрча
• лемме Тьюринга
• теореме Поста

Функция имеет гёделевский номер, равный

• 19
• 13
• 3
• 9

Если и рекурсия проводится по переменной , то функция равна

• 0
• 1

Машина Тьюринга есть совокупность компонент

• трех
• пяти
• двух
• четырех

В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s недоказуемо; 2) Øs доказуемо — из перечисленного

• 2
• 1
• 1 и 2
• ни 1, ни 2

Если и рекурсия проводится по , то функция равна

Если множество рекурсивно, то оно является ______ всюду определенной вычислимой функции

• множеством значений и областью определения
• только множеством значений
• ни множеством значений, ни областью определения
• только областью определения

Если и рекурсия проводится по , то функция равна

• 1
• 0

Множество номеров несамоприменимых машин Тьюринга

• рекурсивно
• рекурсивно перечислимо
• неперечислимо
• неразрешимо

Функция имеет гёделевский номер, равный

• 5
• 4
• 1
• 2

Если , то функция в рекуррентной формуле равна

• m+1
• sin(πn)

Функция равна

• xyz
• x+y
• 3
• x+y+z

Формализованный язык для однозначной записи алгоритмов называется

• автоматным языком
• регулярным языком
• алгоритмическим языком
• метаязыком языком

Множество, если его характеристический предикат является вычислимым, называется

• рекурсивным
• рекурсивно перечислимым
• эффективным
• вычислимым

Геделевский номер, равный 23, имеет функция

• S(S(x))

Усеченная разность равна

• 5
• 3
• 0
• -3

Теорема, связывающая рекурсивности множества с рекурсивной перечислимостью этого множества и его дополнения, называется теоремой

• Поста
• Гёделя
• Клини
• Тьюринга

Лента машины Тьюринга

• может быть многомерной
• считывается в обе стороны
• должна быть только одномерной
• не содержит результаты вычислений