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

Множество простых чисел является
рекурсивным и перечислимым
только рекурсивным
замкнутым
только перечислимым
Функция, определяемая как число шагов в вычислении машиной Тьюринга, называется
временным ресурсом
геделевским номером
характеристической
длиной программы
Функция 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
Теорема, связывающая рекурсивности множества с рекурсивной перечислимостью этого множества и его дополнения, называется теоремой
Поста
Гёделя
Клини
Тьюринга
Лента машины Тьюринга
может быть многомерной
считывается в обе стороны
должна быть только одномерной
не содержит результаты вычислений