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

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

Номер 1

Нумерация множества X - это отображение:

Ответ:

(1) всюду определенное math

(2) частично определенное math

(3) заданное на множестве XхN

Номер 2

Если V(m,x)=U(s(m),x), m, x - любые, то U называется:

Ответ:

(1) определяющей функцией

(2) универсальной функцией

(3) главной универсальной функцией

Номер 3

Нумерация, соответствующая главной универсальной функции называется:

Ответ:

(1) геделевой

(2) тьюринговой

(3) постовской

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

Номер 1

Главная универсальная функция:

Ответ:

(1) не существует

(2) существует

(3) определена только для конечных множеств

Номер 2

Последовательность   вычислима, если:

Ответ:

(1) F(i, n)=f_i(n) - вычислима

(2) F(i,n)=E(f_i) х E(f_i) - вычислима

(3) f(i,n) - вычислима

Номер 3

Последовательность  вычислима, если существует:

Ответ:

(1) конечный ряд с_i, i=0, 1, …, n, c_i=f_i

(2) вычислимая f(i) , i=1,2,…

(3) вычислимые c_i, i=0,1,… , где c_i - номер f_i

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

Номер 1

Если нумерация является вычислимой, то последовательность

Ответ:

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

(2) конечна

(3) невычислима

Номер 2

Нумерация - вычислимая, если:

Ответ:

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

задает нумерацию

(2)

является счетным

(3) X=N

Номер 3

Универсальное перечислимое множество из N × N:

Ответ:

(1) не существует

(2) существует

(3) существует и несчетно

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

Номер 1

Различным операциям над множествами соответствуют:

Ответ:

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

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

(3) различные вычислимые функции

Номер 2

Композиция двух вычислимых функций является:

Ответ:

(1) вычислимой

(2) характеристической

(3) нелинейной

Номер 3

Всякая универсальная функция для класса вычислимых одноместных функций задает:

Ответ:

(1) нумерацию класса

(2) характеристическую функцию класса

(3) отношение эквивалентности

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

Номер 1

Нумерация - вычислима, если вычислима:

Ответ:

(1) универсальная функция

(2) область определения и область изменения

(3) только область определения

Номер 2

Термину "k - местная" удовлетворяет функция:

Ответ:

(1) f (1,2, ,.., k)

(2) f (x₁, x₂, …, x_k)

(3) f=k

Номер 3

Если функция f дает по номеру m функции другой номер s этой функции, то:

Ответ:

(1) f_m=f_s(m)

(2) f_s=f_m

(3) f_m(s)=f_s

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

Номер 1

Вычислимая функция трех аргументов, универсальная для класса вычислимых функций двух аргументов:

Ответ:

(1) существует

(2) не существует

(3) аддитивна

Номер 2

Если U -двухместная главная универсальная функция для класса вычислимых функций одного аргумента, то для всех p, q, x:

Ответ:

(1) U(c(p,q),x)=U(p,U(q,x))

(2) U(c(p),c(q),x)=U(p,U(q),x)

(3) U(c(p),q),x)=U(p)U(q,x))

Номер 3

Определению главной универсальной функции адекватно утверждение:

Ответ:

(1) существует транслятор с языка, для которого есть интерпретатор

(2) существует интерпретатор с любого компилятора

(3) не существует транслятора с языка, у которого есть интерпретатор

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

Номер 1

Вычислимые универсальные функции, не являющиеся главными:

Ответ:

(1) существуют

(2) не существуют

(3) обратимыми

Номер 2

По любому номеру любого вычислимого действительного числа, номер вычислимой функции десятичного его разложения:

Ответ:

(1) можно построить

(2) нельзя построить

(3) можно упростить

Номер 3

Для любого перечислимого множества X из декартового квадрата N существует вычислимая :

Ответ:

(1)

(2)

(3)

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

Номер 1

По программам функций f и g получить их композицию:

Ответ:

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

(2) алгоритмически можно

(3) можно лишь математически (теоретически)

Номер 2

Для описания свойств вычислимых функций, из перечисленных ниже наиболее подходит язык:

Ответ:

(1) Рефал

(2) Паскаль

(3) Бейсик

Номер 3

Верны утверждения:

Ответ:

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

(2) существует универсальное перечислимое подмножество декартова квадрата множества натуральных чисел

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

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