Основы теории алгоритмов

Множество простых чисел является
рекурсивным и перечислимым
только рекурсивным
замкнутым
только перечислимым
Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется
временным ресурсом
геделевским номером
характеристической
длиной программы
Функция image038.gif, текст вопроса Основы теории алгоритмоввычисляется по формуле
image042.gif, текст ответа Основы теории алгоритмов
image040.gif, текст ответа Основы теории алгоритмов
image039.gif, текст ответа Основы теории алгоритмов
image041.gif, текст ответа Основы теории алгоритмов
Если множество не является множеством значений никакой функции, то оно
нерекурсивно и неперечислимо
рекурсивно, но не перечислимо
нерекурсивно, но рекурсивно перечислимо
рекурсивно, и не перечислимо
Если image048.gif, текст вопроса Основы теории алгоритмови рекурсия проводится по image012.gif, текст вопроса Основы теории алгоритмов, то функция image049.gif, текст вопроса Основы теории алгоритмовравна
image050.gif, текст ответа Основы теории алгоритмов
x+z
0
image051.gif, текст ответа Основы теории алгоритмов
Установление соответствия между элементарными высказываниями формальной теории и содержательными высказываниями некоторой предметной области называется
интерпретацией теории
порождающей грамматикой
эффективной процедурой
классом функторов
Любая неразрешимая алгоритмическая проблема дает пример множества
невычислимого
неперечислимого
неразрешимого
несчетного
Если image009.gif, текст вопроса Основы теории алгоритмов, то функция image002.gif, текст вопроса Основы теории алгоритмовв рекуррентной формуле равна
m!
m+1
m+n+1
m(n+1)
Функция image098.gif, текст вопроса Основы теории алгоритмовявляется
частично вычислимой
рекурсивной
общерекурсивной
вычислимой
Функция, равная единице тогда и только тогда, когда предикат истинен, называется
характеристической
частично рекурсивной
примитивно вычислимой
вычислимой
Множество номеров самоприменимых машин Тьюринга
неперечислимо, но разрешимо
рекурсивно перечислимо и разрешимо
рекурсивно перечислимо, но не разрешимо
ни перечислимо, ни разрешимо
Существует команд машины Тьюринга
3 типа
2 типа
4 типа
8 типов
Осмысленные конечные последовательности символов из алфавита L называются
словарем
командами
утверждениями
программой
Утверждение image076.gif, текст вопроса Основы теории алгоритмовформально записывается как
image078.gif, текст ответа Основы теории алгоритмов
image079.gif, текст ответа Основы теории алгоритмов
image077.gif, текст ответа Основы теории алгоритмов
image080.gif, текст ответа Основы теории алгоритмов
Множество доказуемых утверждений формальной системы арифметики
открыто
замкнуто
разрешимо
неразрешимо
Геделевский номер, равный image072.gif, текст вопроса Основы теории алгоритмов, имеет функция
image017.gif, текст ответа Основы теории алгоритмов
image074.gif, текст ответа Основы теории алгоритмов
image075.gif, текст ответа Основы теории алгоритмов
image073.gif, текст ответа Основы теории алгоритмов
Множество, если оно является множеством значений некоторой вычислимой функции, называется
эффективным
рекурсивно перечислимым
разрешимым
вычислимым
Если image011.gif, текст вопроса Основы теории алгоритмови рекурсия проводится по переменной image012.gif, текст вопроса Основы теории алгоритмов, то функция image016.gif, текст вопроса Основы теории алгоритмовравна
image017.gif, текст ответа Основы теории алгоритмов
m+y
1
m+x
Пусть R - рекурсивность, а P - рекурсивная перечислимость. Тогда
image034.gif, текст ответа Основы теории алгоритмов
image035.gif, текст ответа Основы теории алгоритмов
image033.gif, текст ответа Основы теории алгоритмов
image032.gif, текст ответа Основы теории алгоритмов
Множество натуральных чисел является
рекурсивным и перечислимым
только перечислимым
простейшим
только рекурсивным
Если A рекурсивно, а B - рекурсивно перечислимо, то _____ рекурсивно
image029.gif, текст ответа Основы теории алгоритмов
image036.gif, текст ответа Основы теории алгоритмов
image031.gif, текст ответа Основы теории алгоритмов
image037.gif, текст ответа Основы теории алгоритмов
w-непротиворечивая формальная система является
полной
неполной
разрешимой
истинной
Выражением называется
исходная ситуация
набор команд
внутреннее состояние
конечная последовательность символов
Множество составных чисел является
только перечислимым
рекурсивным и перечислимым
только рекурсивным
порождающим
Функция является примитивно рекурсивной, если она получается из набора исходных функций с помощью оператора: 1) рекурсии; 2) ограниченной минимизации; 3) подстановки - из перечисленного
1 и 2
1
1 и 3
1, 2 и 3
Утверждение арифметики Пеано называется неразрешенным, если оно
и его отрицание опровержимы
и его отрицание w-противоречивы
истинно, но недоказуемо
противоречит системе аксиом
Показал возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру
К. Гёдель
А. Тьюринг
А. Марков
Д. Гильберт
Частично вычислимая функция
это частный случай вычислимой
вычисляется с ограниченной точностью
может быть продолжена до вычислимой
не везде совпадает с вычислимой
Теория алгоритмов является частью
теории чисел
математической логики
математического анализа
численных методов
Выражение image099.gif, текст вопроса Основы теории алгоритмовявляется
машиной Тьюринга
командой
исходной ситуацией
элементом алфавита
Теорема Геделя о неполноте арифметики поколебала оптимистические надежды Гильберта на полное решение вопросов оснований математики с помощью
машины Тьюринга
конструктивисткой теории
нормализации алгоритмов
аксиоматического метода
Каждая п.р.ф имеет число номеров
бесконечное
небольшое
ограниченное
индивидуальное
Всякая вычислимая функция является вычислимой по Тьюрингу согласно
теореме Гёделя
тезису Чёрча
лемме Тьюринга
теореме Поста
Функция image067.gif, текст вопроса Основы теории алгоритмовимеет гёделевский номер, равный
19
13
3
9
Если image011.gif, текст вопроса Основы теории алгоритмови рекурсия проводится по переменной image012.gif, текст вопроса Основы теории алгоритмов, то функция image013.gif, текст вопроса Основы теории алгоритмовравна
0
1
image015.gif, текст ответа Основы теории алгоритмов
image014.gif, текст ответа Основы теории алгоритмов
Машина Тьюринга есть совокупность компонент
трех
пяти
двух
четырех
В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s недоказуемо; 2) Øs доказуемо - из перечисленного
2
1
1 и 2
ни 1, ни 2
Если image062.gif, текст вопроса Основы теории алгоритмови рекурсия проводится по image012.gif, текст вопроса Основы теории алгоритмов, то функция image013.gif, текст вопроса Основы теории алгоритмовравна
image044.gif, текст ответа Основы теории алгоритмов
image015.gif, текст ответа Основы теории алгоритмов
image063.gif, текст ответа Основы теории алгоритмов
image043.gif, текст ответа Основы теории алгоритмов
Если множество рекурсивно, то оно является ______ всюду определенной вычислимой функции
множеством значений и областью определения
только множеством значений
ни множеством значений, ни областью определения
только областью определения
Если image055.gif, текст вопроса Основы теории алгоритмови рекурсия проводится по image015.gif, текст вопроса Основы теории алгоритмов, то функцияimage019.gif, текст вопроса Основы теории алгоритмов равна
image056.gif, текст ответа Основы теории алгоритмов
image012.gif, текст ответа Основы теории алгоритмов
1
0
Множество номеров несамоприменимых машин Тьюринга
рекурсивно
рекурсивно перечислимо
неперечислимо
неразрешимо
Функция image066.gif, текст вопроса Основы теории алгоритмовимеет гёделевский номер, равный
5
4
1
2
Если image006.gif, текст вопроса Основы теории алгоритмов, то функция image002.gif, текст вопроса Основы теории алгоритмовв рекуррентной формуле равна
m+1
image007.gif, текст ответа Основы теории алгоритмов
image008.gif, текст ответа Основы теории алгоритмов
sin(πn)
Функция image047.gif, текст вопроса Основы теории алгоритмовравна
xyz
x+y
3
x+y+z
Формализованный язык для однозначной записи алгоритмов называется
автоматным языком
регулярным языком
алгоритмическим языком
метаязыком языком
Множество, если его характеристический предикат является вычислимым, называется
рекурсивным
рекурсивно перечислимым
эффективным
вычислимым
Геделевский номер, равный 23, имеет функция
image070.gif, текст ответа Основы теории алгоритмов
image071.gif, текст ответа Основы теории алгоритмов
image069.gif, текст ответа Основы теории алгоритмов
S(S(x))
Усеченная разность image054.gif, текст вопроса Основы теории алгоритмовравна
5
3
0
-3
Теорема, связывающая рекурсивности множества с рекурсивной перечислимостью этого множества и его дополнения, называется теоремой
Поста
Гёделя
Клини
Тьюринга
Лента машины Тьюринга
может быть многомерной
считывается в обе стороны
должна быть только одномерной
не содержит результаты вычислений