Задание (стр. 2 )

*****

Укажите связь между примитивной рекурсивностью и общерекурсивностью.

A) Каждая общерекурсивная функция является примитивно рекурсивной

B) Примитивная рекурсивность равносильна общерекурсивности

C) Каждая примитивно рекурсивная функция является общерекурсивной

D) Примитивно рекурсивная функция не является общерекурсивной

E) Всюду определенная общерекурсивная функция примитивно рекурсивна

*****

Пусть какая-нибудь примитивно рекурсивная функция и - произвольное примитивно рекурсивное множество натуральных чисел. Определите частично рекурсивную функцию :

A)

B)

C)

D)

E)

*****

Сформулируйте теорему Поста

A) Если какое-нибудь множество А рекурсивно перечислимо и его дополнение A' также рекурсивно перечислимо, то множества А и А' рекурсивны

B) Если какое-нибудь множество А рекурсивно перечислимо, то и его дополнение A' также рекурсивно перечислимо

C) Если какое-нибудь множество А рекурсивно перечислимо и его дополнение A' не рекурсивно перечислимо, то множества А и А' рекурсивны

D) Если какое-нибудь множество А рекурсивно перечислимо, то множества А и А' рекурсивны

E) Если какое-нибудь множество А рекурсивно перечислимо, то его дополнение A' рекурсивно

*****

Дайте определение рекурсивно перечислимого множества:

A) Множество чисел А называется рекурсивно перечислимым, если существует двуместная примитивно рекурсивная функция f(a,x) такая, что уравнение f(a,x)=0 имеет решение xA

B) Множество чисел А называется рекурсивно перечислимым, если существует двуместная частично рекурсивная функция f(a,x) такая, что уравнение f(a,x)=0 имеет решение x тогда и только тогда, когда aA

C) Множество чисел А называется рекурсивно перечислимым, если существует двуместная примитивно рекурсивная функция f(a,x) такая, что уравнение f(a,x)=1 имеет решение x тогда и только тогда, когда aA

D) Множество чисел А называется рекурсивно перечислимым, если существует двуместная примитивно рекурсивная функция f(a,x) такая, что уравнение f(a,x)=0 имеет решение x тогда и только тогда, когда aA

E) Множество чисел А называется рекурсивно перечислимым, если существует двуместная примитивно рекурсивная функция f(a,x) такая, что уравнение f(a,x)=0 имеет решение x тогда и только тогда, когда aA

*****

Дайте определение частично рекурсивного множества:

A) Множество называется частично рекурсивным, если существует частично рекурсивная функция

B) Множество называется частично рекурсивным, если примитивно рекурсивна

C) Множество называется частично рекурсивным, если примитивно рекурсивна

D) Множество называется частично рекурсивным, если частично рекурсивна

E) Множество называется частично рекурсивным, если частично рекурсивна

*****

Укажите связь между примитивной рекурсивностью и частичной рекурсивностью множества:

A) Каждое частично рекурсивное множество является примитивно рекурсивным

B) Каждое примитивно рекурсивное множество является частично рекурсивным

C) Множество чисел примитивно рекурсивно тогда и только тогда, когда оно частично рекурсивно

D) Примитивно рекурсивное множество не является частично рекурсивным

E) Примитивно рекурсивное множество является всюду определенным частично рекурсивным

*****

Дайте определение общерекурсивных функций:

A) Всюду определенные частично рекурсивные функции называются общерекурсивными функциями

B) Если область определения функции из X в Y совпадает с множеством X, то функция называется общерекурсивной

C) Пусть задана система каких-то частичных функций. Функция f называется общерекурсивной относительно , если f можно получить из функций системы и простейших функций , , конечным числом операций подстановки, примитивной рекурсии и минимизации

D) Всюду определенные примитивно рекурсивные функции называются общерекурсивными функциями

E) Всюду определенные функции называются общерекурсивными функциями

*****

Укажите связь между примитивной рекурсивностью и рекурсивной перечислимостью множества:

A) Каждое рекурсивно перечислимое множество примитивно рекурсивно

B) Множество чисел примитивно рекурсивно тогда и только тогда, когда оно рекурсивно перечислимо

C) Примитивно рекурсивное множество не рекурсивно перечислимо

D) Рекурсивно перечислимое множество не примитивно рекурсивно

E) Каждое примитивно рекурсивное множество рекурсивно перечислимо

*****

Сформулируйте теорему о мажорируемых неявных функциях:

A) Пусть , такие примитивно рекурсивные функции, что уравнение для каждых, имеет по меньшей мере одно решение и для любых . Тогда функция также примитивно рекурсивна

B) Пусть , такие примитивно рекурсивные функции, что уравнение для каждых, имеет по меньшей мере одно решение и для любых . Тогда функция также примитивно рекурсивна

C) Пусть , такие примитивно рекурсивные функции, что уравнение для каждых, имеет по меньшей мере одно решение и для любых . Тогда функция также примитивно рекурсивна

D) Функция f возникающая из всюду определенных функций и вспомогательных функций, удовлетворяющих условиям , с помощью возвратной рекурсии, может быть получена из тех же функций,и простейших функций операциями подстановки и примитивной рекурсии

E) Функция f возникающая из всюду определенных функций и вспомогательных функций, удовлетворяющих условиям , с помощью возвратной рекурсии, может быть получена из тех же функций, операциями подстановки и примитивной рекурсии

*****

Укажите функцию Гёделя:

A) Г(x,y)=rest(r(x),1+(y+1)l(x))

B) Г(x, y)=rest(l(x),(y+1)r(x))

C) Г(x, y)=rest(r(x),1+(y+1)r(x))

D) Г(x, y)=rest(l(x),1+(y+1)r(x))

E) Г(x, y)=rest(l(x),yr(x))

*****

Дайте определение функции, вычислимой по Тьюрингу:

A) Частичная числовая функция называется вычислимой (по Тьюрингу), если существует машина Тьюринга , такая, что если f() определено, то (k())=k(f()).

B) Частичная числовая функция называется вычислимой (по Тьюрингу), если существует машина Тьюринга , такая, что если f() не определено, то либо (k()) не является кодом никакого числа из N, либо машина не применима к слову k().

C) Частичная числовая функция называется вычислимой (по Тьюрингу), если существует машина Тьюринга , обладающая следующими свойствами: 1) если f() определено, то (k())=k(f()); 2) если f() не определено, то либо (k()) не является кодом никакого числа из N, либо машина не применима к слову k().

D) Частичная числовая функция называется вычислимой (по Тьюрингу), если существует машина Тьюринга , обладающая следующими свойствами: 1) если f() не определено, то (k())=k(f()); 2) если f() определено, то либо (k()) не является кодом никакого числа из N, либо машина не применима к слову k().

E) Частичная числовая функция называется вычислимой (по Тьюрингу), если существует машина Тьюринга , обладающая следующими свойствами: 1) если f() определено, то (k())=f(); 2) если f() не определено, то либо (k()) не является кодом никакого числа из N, либо машина не применима к слову k().

*****

Укажите к какому слову Р не применима машина Тьюринга Т, задаваемая программой П. Предполагается, что – начальное состояние, - заключительное и в начальный момент головка машины обозревает самую левую единицу на ленте.

A) P = 1110011

B) P = 1110111

C) P = 1001011

D) P = 1001

E) P = 10001

*****

Укажите частично рекурсивную, но не примитивно рекурсивную функцию:

A)

B)

C)

D)

E)

*****

Найдите номер пары (7,9).

A) 143

B) 259

C) 160

D) 157

E) 148

*****

Найдите номер пары (4,6).

A) 59

B) 259

C) 16

D) 157

E) 48

*****

Найдите номер пары (6,4).

A) 61

B) 59

C) 60

D) 57

E) 48

*****

Найдите пару с номером 100.

A) (9,4)

B) (5,9)

C) (6,0)

D) (7,4)

E) (4,8)

*****

Найдите пару с номером 61.

A) (6,4)

B) (5,9)

C) (6,0)

D) (7,4)

E) (4,8)

*****

Найдите пару с номером 59.

A) (4,6)

B) (5,9)

C) (6,0)

D) (7,4)

E) (4,8)

*****

По какой формуле находят номер пары (x,y)?