Основы теории алгоритмов
Основы теории алгоритмов
1000.02.01;МТ.01;1Множество простых чисел является
рекурсивным и перечислимым
только рекурсивным
замкнутым
только перечислимым
Основы теории алгоритмов
1000.02.01;МТ.01;1Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется
временным ресурсом
геделевским номером
характеристической
длиной программы
Основы теории алгоритмов
1000.02.01;МТ.01;1Если множество не является множеством значений никакой функции, то оно
нерекурсивно и неперечислимо
рекурсивно, но не перечислимо
нерекурсивно, но рекурсивно перечислимо
рекурсивно, и не перечислимо
Основы теории алгоритмов
1000.02.01;МТ.01;1Установление соответствия между элементарными высказываниями формальной теории и содержательными высказываниями некоторой предметной области называется
интерпретацией теории
порождающей грамматикой
эффективной процедурой
классом функторов
Основы теории алгоритмов
1000.02.01;МТ.01;1Любая неразрешимая алгоритмическая проблема дает пример множества
невычислимого
неперечислимого
неразрешимого
несчетного
Основы теории алгоритмов
1000.02.01;МТ.01;1Если
, то функция
в рекуррентной формуле равна


m!
m+1
m+n+1
m(n+1)
Основы теории алгоритмов
1000.02.01;МТ.01;1Функция
является

частично вычислимой
рекурсивной
общерекурсивной
вычислимой
Основы теории алгоритмов
1000.02.01;МТ.01;1Функция, равная единице тогда и только тогда, когда предикат истинен, называется
характеристической
частично рекурсивной
примитивно вычислимой
вычислимой
Основы теории алгоритмов
1000.02.01;МТ.01;1Множество номеров самоприменимых машин Тьюринга
неперечислимо, но разрешимо
рекурсивно перечислимо и разрешимо
рекурсивно перечислимо, но не разрешимо
ни перечислимо, ни разрешимо
Основы теории алгоритмов
1000.02.01;МТ.01;1Существует команд машины Тьюринга
3 типа
2 типа
4 типа
8 типов
Основы теории алгоритмов
1000.02.01;МТ.01;1Осмысленные конечные последовательности символов из алфавита L называются
словарем
командами
утверждениями
программой
Основы теории алгоритмов
1000.02.01;МТ.01;1Множество доказуемых утверждений формальной системы арифметики
открыто
замкнуто
разрешимо
неразрешимо
Основы теории алгоритмов
1000.02.01;МТ.01;1Множество, если оно является множеством значений некоторой вычислимой функции, называется
эффективным
рекурсивно перечислимым
разрешимым
вычислимым
Основы теории алгоритмов
1000.02.01;МТ.01;1Если
и рекурсия проводится по переменной
, то функция
равна




m+y
1
m+x
Основы теории алгоритмов
1000.02.01;МТ.01;1Пусть R - рекурсивность, а P - рекурсивная перечислимость. Тогда




Основы теории алгоритмов
1000.02.01;МТ.01;1Множество натуральных чисел является
рекурсивным и перечислимым
только перечислимым
простейшим
только рекурсивным
Основы теории алгоритмов
1000.02.01;МТ.01;1Если A рекурсивно, а B - рекурсивно перечислимо, то _____ рекурсивно




Основы теории алгоритмов
1000.02.01;МТ.01;1w-непротиворечивая формальная система является
полной
неполной
разрешимой
истинной
Основы теории алгоритмов
1000.02.01;МТ.01;1Выражением называется
исходная ситуация
набор команд
внутреннее состояние
конечная последовательность символов
Основы теории алгоритмов
1000.02.01;МТ.01;1Множество составных чисел является
только перечислимым
рекурсивным и перечислимым
только рекурсивным
порождающим
Основы теории алгоритмов
1000.02.01;МТ.01;1Функция является примитивно рекурсивной, если она получается из набора исходных функций с помощью оператора: 1) рекурсии; 2) ограниченной минимизации; 3) подстановки - из перечисленного
1 и 2
1
1 и 3
1, 2 и 3
Основы теории алгоритмов
1000.02.01;МТ.01;1Утверждение арифметики Пеано называется неразрешенным, если оно
и его отрицание опровержимы
и его отрицание w-противоречивы
истинно, но недоказуемо
противоречит системе аксиом
Основы теории алгоритмов
1000.02.01;МТ.01;1Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру
К. Гёдель
А. Тьюринг
А. Марков
Д. Гильберт
Основы теории алгоритмов
1000.02.01;МТ.01;1Частично вычислимая функция
это частный случай вычислимой
вычисляется с ограниченной точностью
может быть продолжена до вычислимой
не везде совпадает с вычислимой
Основы теории алгоритмов
1000.02.01;МТ.01;1Теория алгоритмов является частью
теории чисел
математической логики
математического анализа
численных методов
Основы теории алгоритмов
1000.02.01;МТ.01;1Выражение
является

машиной Тьюринга
командой
исходной ситуацией
элементом алфавита
Основы теории алгоритмов
1000.02.01;МТ.01;1Теорема Геделя о неполноте арифметики поколебала оптимистические надежды Гильберта на полное решение вопросов оснований математики с помощью
машины Тьюринга
конструктивисткой теории
нормализации алгоритмов
аксиоматического метода
Основы теории алгоритмов
1000.02.01;МТ.01;1Каждая п.р.ф имеет число номеров
бесконечное
небольшое
ограниченное
индивидуальное
Основы теории алгоритмов
1000.02.01;МТ.01;1Всякая вычислимая функция является вычислимой по Тьюрингу согласно
теореме Гёделя
тезису Чёрча
лемме Тьюринга
теореме Поста
Основы теории алгоритмов
1000.02.01;МТ.01;1Если
и рекурсия проводится по переменной
, то функция
равна



0
1


Основы теории алгоритмов
1000.02.01;МТ.01;1Машина Тьюринга есть совокупность компонент
трех
пяти
двух
четырех
Основы теории алгоритмов
1000.02.01;МТ.01;1В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s недоказуемо; 2) Øs доказуемо - из перечисленного
2
1
1 и 2
ни 1, ни 2
Основы теории алгоритмов
1000.02.01;МТ.01;1Если множество рекурсивно, то оно является ______ всюду определенной вычислимой функции
множеством значений и областью определения
только множеством значений
ни множеством значений, ни областью определения
только областью определения
Основы теории алгоритмов
1000.02.01;МТ.01;1Множество номеров несамоприменимых машин Тьюринга
рекурсивно
рекурсивно перечислимо
неперечислимо
неразрешимо
Основы теории алгоритмов
1000.02.01;МТ.01;1Формализованный язык для однозначной записи алгоритмов называется
автоматным языком
регулярным языком
алгоритмическим языком
метаязыком языком
Основы теории алгоритмов
1000.02.01;МТ.01;1Множество, если его характеристический предикат является вычислимым, называется
рекурсивным
рекурсивно перечислимым
эффективным
вычислимым
Основы теории алгоритмов
1000.02.01;МТ.01;1Теорема, связывающая рекурсивности множества с рекурсивной перечислимостью этого множества и его дополнения, называется теоремой
Поста
Гёделя
Клини
Тьюринга
Основы теории алгоритмов
1000.02.01;МТ.01;1Лента машины Тьюринга
может быть многомерной
считывается в обе стороны
должна быть только одномерной
не содержит результаты вычислений