Главная / Алгоритмы и дискретные структуры /
Основы теории вычислимых функций / Тест 10
Основы теории вычислимых функций - тест 10
Упражнение 1:
Номер 1
Работу всякой машины Тьюринга промоделировать другой машиной Тьюринга:
Ответ:
 (1) можно всегда 
 (2) нельзя всегда 
 (3) можно для не вычислимых функций 
Номер 2
Лента машины Тьюринга может быть:
Ответ:
 (1) бесконечной 
 (2) только конечной 
 (3) полубесконечной (бесконечной только в одну сторону) 
Номер 3
Стек - это:
Ответ:
 (1) структура данных 
 (2) структура команд 
 (3) устройство установки 
Упражнение 2:
Номер 1
Всякая функция, вычислимая программой с конечным числом переменных:
Ответ:
 (1) вычислима на машине Тьюринга 
 (2) не вычислима на машине Тьюринга 
 (3) тождественна единице 
Номер 2
График любой функции, вычислимой программой с конечным числом переменных:
Ответ:
 (1) является арифметическим множеством 
 (2) не является арифметическим множеством 
 (3) представляет прямую линию 
Номер 3
Для любого k
и последовательности b+1, 2b+2, 3b+1, …
(b<0
- некоторое целое):
Ответ:
 (1) попарно просты b
и числа b+1, 2b+2, 3b+1,…, kb+1
 
 (2) просты все числа b+1, 2b+2, 3b+1, …, kb+1
 
 (3) кратны попарно числа (k, b), (b+1, kb+1)
 
Упражнение 3:
Номер 1
Для любых можно найти такие числа a
и b
, что:
Ответ:
 (1) xi = a mod b(i+1) + 1
 
 (2) xi = a mod b(i+1)
 
 (3) xi = a mod bi + 1
 
Номер 2
При любом n
любое множество из класса :
Ответ:
 (1) арифметично 
 (2) пусто 
 (3) универсально 
Номер 3
При любом n
любое множество из класса :
Ответ:
 (1) не арифметично 
 (2) арифметично 
 (3) пусто 
Упражнение 4:
Номер 1
Любое арифметичное множество может лежать в классе:
Ответ:
 
(1)  
 
(2)  
 (3) универсальном 
Номер 2
Арифметическое множество m
-сводимо к множеству всех истинных арифметических формул без параметров:
Ответ:
 (1) всегда 
 
(2) только для
 
 
(3) только для
 
Номер 3
Множество всех истинных арифметических формул без параметров:
Ответ:
 (1) арифметично 
 (2) не арифметично 
 (3) универсально 
Упражнение 5:
Номер 1
Множество всех истинных арифметических формул без параметров:
Ответ:
 (1) не перечислимо 
 (2) перечислимо 
 (3) универсально 
Номер 2
Теорема Тарского:
Ответ:
 (1) множество арифметических истин не арифметично 
 (2) множество арифметических истин не перечислимо 
 (3) во множестве арифметических истин есть пустое 
Номер 3
Теорема Геделя:
Ответ:
 (1) множество арифметических истин не арифметично 
 (2) множество арифметических истин не перечислимо 
 (3) арифметика - перечислима 
Упражнение 6:
Номер 1
Утверждение "Всякое исчисление, порождающее формулы арифметики либо не адекватно, либо неполно" - это:
Ответ:
 (1) теорема Геделя 
 (2) теорема Черча 
 (3) тезис Тьюринга 
Номер 2
Утверждение "Любой алгоритм, перечисляющий множество формул арифметики порождает некоторую ложную формулу, либо не порождает некоторой истинной формулы" - это:
Ответ:
 (1) теорема о полноте Кантора 
 (2) теорема о неполноте Геделя 
 (3) теорема о существовании универсальной машины Тьюринга 
Номер 3
Если в одноместную формулу с номером n
подставить значение n
, то получим:
Ответ:
 (1) формулу без параметра 
 (2) истинное высказывание 
 (3) ложное высказывание 
Упражнение 7:
Номер 1
Множество доказательств:
Ответ:
 (1) разрешимо 
 (2) не разрешимо 
 (3) универсально 
Номер 2
Парадокс лжеца отражает утверждение:
Ответ:
 (1) данный вариант ответа неправильный 
 (2) данный вариант ответа правильный 
 (3) утверждение, высказанное в этом варианте - ложно 
Номер 3
Две программы A
, В
доказуемо различны, если:
Ответ:
 (1) есть вход с различными результатами А
и В
 
 (2) нет входа с различными результатами А
и В
 
 (3) верифицированы A
и В
 
Упражнение 8:
Номер 1
Программу А
со свойством "никакая программа В
не является доказуемо различной с А
":
Ответ:
 (1) можно построить 
 (2) нельзя построить 
 (3) можно верифицировать 
Номер 2
Непознаваемая программа:
Ответ:
 (1) существует 
 (2) не существует 
 (3) тестируема 
Номер 3
Утверждение: "Средствами формальной системы нельзя доказать ее непротиворечивость" - это:
Ответ:
 (1) первая теорема Геделя 
 (2) вторая теорема Геделя 
 (3) десятая проблема Гильберта