Основы теории вычислимых функций

Упражнение 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) x_i = a mod b(i+1) + 1

(2) x_i = a mod b(i+1)

(3) x_i = a mod bi + 1

Номер 2

При любом n любое множество из класса :

Ответ:

(1) арифметично

(2) пусто

(3) универсально

Номер 3

При любом n любое множество из класса :

Ответ:

(1) не арифметично

(2) арифметично

(3) пусто

Упражнение 4:

Номер 1

Любое арифметичное множество может лежать в классе:

Ответ:

(1)

(2)

(3) универсальном

Номер 2

Арифметическое множество m-сводимо к множеству всех истинных арифметических формул без параметров:

Ответ:

(1) всегда

(2) только для math

(3) только для math

Номер 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) десятая проблема Гильберта

Основы теории вычислимых функций - тест 10