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

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

Номер 1

Функция  m=f(n),   вычислима, если существует алгоритм A(f):

Ответ:

(1) останавливающийся и печатающий m=f(n)

(2) преобразующий число n в число n+1 для любого m

(3) преобразующий число n в число n+m для любого m

Номер 2

Функция m=f(n),   вычислима, если существует алгоритм A(f):

Ответ:

(1) останавливающийся для неопределенного f(n)

(2) не останавливающийся для неопределенного f(n)

(3) не останавливающийся для определенного f(n)

Номер 3

Функция m=f(n),   вычислима, если существует алгоритм A(f):

Ответ:

(1) останавливающийся для определенного f(n)

(2) не останавливающийся для неопределенного f(n)

(3) вычисляющий цифры m

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

Номер 1

Вычислима функция:

Ответ:

(1) f(n)=sin(n)

(2) f(n)=sign(x+n)

(3) f(n)=n+1

Номер 2

Вычислима функция:

Ответ:

(1) f(n)=cos(n)

(2) f(n)=n sign(n+x)

(3) f(n)=n-1

Номер 3

Не вычислима функция:

Ответ:

(1) f(n)=1

(2) f(n)=sign(n+1)

(3) f(n)=n

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

Номер 1

Множество X из N разрешимо, если существует алгоритм:

Ответ:

(1) определения, принадлежит ли math

множеству X

(2) вычисления math

по заданному math

(3) поиска наибольшего n

Номер 2

Характеристическая функция множества X:

Ответ:

(1)

(2)

(3)

Номер 3

Множество натуральных чисел X разрешимо, если:

Ответ:

(1) вычислима math

для

(2) вычислима math

для

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

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

Номер 1

Множество натуральных чисел X перечислимо, если оно:

Ответ:

(1) перечисляется по некоторому алгоритму

(2) сортируемо алгоритмом обменами

(3) счетно

Номер 2

Множество перечислимо, если:

Ответ:

(1) оно есть область определения вычислимой функции

(2) оно состоит только из натуральных чисел

(3) его характеристическая функция имеет значение 0

Номер 3

Множество перечислимо, если оно:

Ответ:

(1) есть область значений вычислимой функции

(2) содержит область значений вычислимой функции

(3) совершенно

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

Номер 1

Пересечение перечислимых множеств - всегда:

Ответ:

(1) перечислимо

(2) перечислимо или неопределенно

(3) пусто

Номер 2

Объединение перечислимых множеств А и В всегда перечислимо:

Ответ:

(1) для конечных А и В

(2) для всех таких А и В

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

Номер 3

Декартово произведение перечислимых множеств А и В перечислимо:

Ответ:

(1) если math

(2) всегда

(3) или неопределенно всегда

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

Номер 1

Перечислимо всякое множество, если оно:

Ответ:

(1) разрешимо

(2) есть подмножество N

(3) равномощно N

Номер 2

Теорема Поста:

Ответ:

(1) разрешимые множества перечислимы со своими дополнениями

(2) перечислимые множества разрешимы со своими дополнениями

(3) либо само множество, либо его дополнение всегда перечислимо

Номер 3

Множество X из N перечислимо тогда и только тогда, когда:

Ответ:

(1) X - проекция некоторого разрешимого множества

(2) Y - множество натуральных чисел

(3) верно и а), и б)

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

Номер 1

Функция перечислима тогда и только тогда, когда

Ответ:

(1) ее график перечислим

(2) ее график - множество изолированных точек

(3) ее график совпадает с проекцией графика на N

Номер 2

Образ множества X для частичной функции f(n) - это:

Ответ:

(1)

(2)

(3)

Номер 3

Прообраз множества X для частичной функции f(n) - это:

Ответ:

(1)

(2)

(3)

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

Номер 1

Верно утверждение для множества диафантовых уравнений:

Ответ:

(1) перечислимо, если разрешимы уравнения

(2) перечислимо, если они неразрешимы

(3) всегда перечислимо

Номер 2

Всякое бесконечное перечислимое множество:

Ответ:

(1) содержит разрешимое множество

(2) разрешимо

(3) неразрешимо

Номер 3

Множество всех показателей n, для которых существует целое решение уравнения xⁿ+yⁿ=zⁿ всегда:

Ответ:

(1) перечислимо

(2) пусто

(3) совпадает с N

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