Основы теории алгоритмов
Конечному автомату соответствует грамматика, порождающая
машину Тьюринга
регулярный язык
язык программирования
словарь машины
Временные или пространственные характеристики процесса вычисления называются
интерпретацией системы
представлением системы
классом сложности
вычислительными ресурсами
Если A и B - рекурсивные множества, то рекурсивны также множества I. II. III.
только I и III
только I и II
только II
I, II и III
Функция является: 1) частично вычислимой; 2) примитивно рекурсивной; 3) частично рекурсивной
1 и 3
1
2 и 3
1 и 2
Язык, на котором описывается другой язык, называется
автоматным языком
метаязыком
формальной системой
формулой языка Ъ
Челночный алгоритм является алгоритмом
марковским
регулярным
дискретным
нелинейным
Существуют три основных класса фраз: имена, предложения и
функторы
кванторы
предикаты
дизъюнкты
Функция, вычисляемая некоторой машиной Тьюринга с входным и выходным алфавитами, называется
обратной
вычислимой
характеристической
рекурсивной
Фразы, соединяемые функтором, называются
предложениями
формульными
регулярными
аргументами
Средство для соединения фраз для преобразования других фраз называется
метаязыком
функтором
конъюнкцией
грамматикой
Множество ________ тогда и только тогда, когда оно является _______ некоторой вычислимой функции
перечислимо, областью определения
разрешимо, областью определения
перечислимо, множеством значений
разрешимо, множеством значений
Марковский алгоритм - это алгоритм
стохастический
нелинейный
недетерминированный
нормальный
Функция, полученная из вычислимой с помощью рекурсии, является
частично рекурсивной
дифференцируемой
примитивно рекурсивной
вычислимой
Множество всех истинных утверждений языка L является
разрешимым и перечислимым
разрешимым, но неперечислимым
неразрешимым и неперечислимым
неразрешимым, но перечислимым
Если множество неперечислимо, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции
может быть, может быть
не может быть, не может быть
не может быть, может быть
может быть, не может быть
Автомат, однократно считывающий входную строку слева направо, называется
дискретным
МП-автоматом
конечным
элементарным
Функция, вычислимая по Тьюрингу, является
частично рекурсивной
характеристической
общерекурсивной
примитивно рекурсивной
Полнота - это условие, что для любого утверждения s одно из утверждений s и Øs
истинно
ложно
опровержимо
доказуемо
Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым
должно быть
разъединено с
не может быть
может не быть
Идея использования рекурсии для решения задач, связанных с основаниями математики, предложена
Аль Хорезми
Гильбертом
Тьюрингом
Пеано
Формальная грамматика, позволяющая построить любую правильную цепочку символов, называется грамматикой
автоматной
порождающей
нормальной
регулярной
Не существует формальной системы арифметики, удовлетворяющей условиям полноты и противоречивости согласно
тезису Черча
теореме Геделя
теории Гильберта
теореме Поста
Внутренним алфавитом машины Тьюринга называется
множество команд машины
множество конфигураций машины
множеством состояний машины
символы, записанные на ленте
Способ видения объектов формальных систем как конкретных объектов при условии, что содержательные объекты сохраняют структуру формальных, называется
изоморфизмом системы
трансформацией системы
представлением системы
интерпретацией системы
Множество всевозможных осмысленных утверждений языка является
рекурсивно перечислимым
креативным
неперечислимым
рекурсивным
Не сохраняет примитивную рекурсивность оператор
сдвига
минимизации
рекурсии
подстановки
В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений
рекурсивно перечислимо
нерекурсивно
разрешимо
неперечислимо
Множество аксиом вместе с явным определением доказательства составляют
рекурсивное множество
формальную систему
теорию алгоритмов
машину Тьюринга
Множество истинных утверждений
не выводится из системы аксиом
выводится из системы аксиом
перечисляет все системы аксиом
носит название системы аксиом
Символы, которые машина Тьюринга читает и пишет на ленте, образуют
конфигурацию
выражения
команды
алфавит
В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s опровержимо; 2) Øs опровержимо
1 и 2
1
2
ни 1, ни 2
Команда машины Тьюринга состоит из элементарных действий
конечного числа
трех
любого числа
двух
Если множество нерекурсивно, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции
не может быть, может быть
может быть, не может быть
не может быть, не может быть
может быть, может быть
Всякое непустое ______ множество является _________ некоторой всюду определенной вычислимой функции
рекурсивное, областью определения
рекурсивно перечислимое, множеством значений
продуктивное, множеством значений
креативное, областью определения