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

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

A) Частичная функ­ция называется частично рекурсивной относительно системы частичных функций , если может быть полу­чена из функций системы и простейших функций конечным числом операций подстановки, примитивной рекурсии и минимизации

B) Частичная функ­ция называется частично рекурсивной относительно системы частичных функций , если может быть полу­чена из функций системы конечным числом операций подстановки, примитивной рекурсии и минимизации

C) Частичная функ­ция называется частично рекурсивной относительно системы частичных функций , если может быть полу­чена из функций системы и простейших функций конечным числом операций подстановки, примитивной рекурсии

D) Частичная функ­ция называется частично рекурсивной относительно системы частичных функций , если может быть полу­чена из функций системы и простейших функций конечным числом операций примитивной рекурсии и минимизации

E) Частичная функ­ция называется частично рекурсивной относительно системы частичных функций , если может быть полу­чена из функций системы и простейших функций конечным числом операций подстановки, рекурсии и минимизации

*****

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

A) Частичной характеристиче­ской функцией множества А называется функция, равная 0 в точках множества А и 1 в точках, не при­надлежащих А

B) Частичной характеристиче­ской функцией множества А называется функция, равная 0 в точках множества А и не определенная в точках, не при­надлежащих А

C) Частичной характеристиче­ской функцией множества А называется функция, равная 1 в точках множества А и не определенная в точках, не при­надлежащих А

D) Частичной характеристиче­ской функцией множества А называется функция, равная 0 в точках, не при­надлежащих А и не определенная в точках, при­надлежащих А

E) Частичной характеристиче­ской функцией множества А называется функция, равная 0 в точках множества N и не определенная в точках, не при­надлежащих N

*****

Определите операцию суммирования:

A) Говорят, что n-местная функция f получается из n-местной функции g операцией суммирования, если

B) Говорят, что n-местная функция f получается из n-местной функции g операцией суммирования, если

C) Говорят, что (n+1)-местная функция f получается из n-местной функции g операцией суммирования, если

D) Говорят, что n-местная функция f получается из n-местной функции g операцией суммирования, если

E) Говорят, что n-местная функция f получается из n-местной функции g операцией суммирования, если

*****

Определите операцию мультиплицирования

A) Говорят, что n-местная функция f получается из n-местной функции g операцией мультиплицирования, если

B) Говорят, что (n+1)-местная функция f получается из n-местной функции g операцией мультиплицирования, если

C) Говорят, что n-местная функция f получается из n-местной функции g операцией мультиплицирования, если

D) Говорят, что n-местная функция f получается из (n+1)-местной функции g операцией мультиплицирования, если

E) Говорят, что n-местная функция f получается из n-местной функции g операцией мультиплицирования, если

*****

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

A)

B)

C)

D)

E)

*****

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

A) Частичной характеристиче­ской функцией множества А называется функция, равная 0 в точках множества А и 1 в точках, не при­надлежащих А

B) Частичной характеристиче­ской функцией множества А называется функция, равная 0 в точках множества А и не определенная в точках, не при­надлежащих А

C) Частичной характеристиче­ской функцией множества А называется функция, равная 1 в точках множества А и не определенная в точках, не при­надлежащих А

D) Частичной характеристиче­ской функцией множества А называется функция, равная 0 в точках, не при­надлежащих А и не определенная в точках, при­надлежащих А

E) Частичной характеристиче­ской функцией множества А называется функция, равная 0 в точках множества N и не определенная в точках, не при­надлежащих N

*****

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

A) Все частично рекурсивные функции примитивно рекурсивны.

B) Примитивная рекурсивность равносильна частичной рекурсивности.

C) Не всюду определенные примитивно рекурсивные функции частично рекурсивны.

D) Всюду определенные примитивно рекурсивные функции частично рекурсивны.

E) Все примитивно рекурсивные функции частично рекурсивны.

*****

Сформулируйте теорему о возвратной рекурсии:

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

B) Функция , возникающая из всюду определенных функций , и вспомогательных функций ,…, , удовлетворяющих условиям , (i=1,…,s), с помощью возвратной рекурсии, может быть получена из тех же функций , , операциями подстановки и примитивной рекурсии

C) Функция , возникающая из всюду определенных функций , и вспомогательных функций ,…, , удовлетворяющих условиям , (i=1,…,s), с помощью возвратной рекурсии, может быть получена из тех же функций , , и простейших функций , , операциями подстановки и примитивной рекурсии

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

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

*****

Сформулируйте теорему Робинсона:

A) Все примитивно рекурсивные функции могут быть получены из функций s(x)=x+1 и q(x)=x-[] конечным числом операций +, *, J

B) Все одноместные примитивно рекурсивные функции и только они могут быть получены из функций s(x)=x+1 и q(x)=x-[] конечным числом операций +, *, J

C) Все одноместные примитивно рекурсивные функции и только они могут быть получены из функций s(x)=x+1 и q(x)=x+[] конечным числом операций +, *, J

D) Все одноместные примитивно рекурсивные функции могут быть получены из функций s(x)=x+1 и q(x)=x-[] конечным числом операций +, *, J

E) Все одноместные примитивно рекурсивные функции и только они могут быть получены из функций s(x)=x+1 и q(x)=x-[] конечным числом операций +, *

*****

Определите операцию минимизации:

A) Пусть дана n-местная (n>=1) частичная числовая функция . Говорят, что функция получается операцией минимизации из функции , если - наименьшее натуральное значение y уравнения при фиксированных значениях

B) Пусть дана n-местная (n>=1) частичная числовая функция . Говорят, что функция получается операцией минимизации из функции , если - наибольшее натуральное значение y уравнения при фиксированных значениях

C) Пусть дана n-местная (n>=1) частичная числовая функция . Говорят, что функция получается операцией минимизации из функции , если - наименьшее натуральное значение y уравнения при фиксированных значениях

D) Пусть дана n-местная (n>=1) частичная числовая функция . Говорят, что функция получается операцией минимизации из функции , если - наименьшее натуральное значение y уравнения при фиксированных значениях

E) Пусть дана n-местная (n>=1) частичная числовая функция . Говорят, что функция получается операцией минимизации из функции , если - наименьшее натуральное значение y уравнения при фиксированных значениях

*****

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

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

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

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

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

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

*****

Определите кусочное задание функции:

A) Пусть заданы функции , i=1,…,s+1 и указаны какие-то условия , j=1,…,s , принимающие значения "истина" или "ложь" и никакие два не могут быть истинными одновременно. Функция, заданная схемой называется функцией, определенной кусочной схемой.

B) Пусть заданы функции , i=1,…,s+1 и указаны какие-то условия , j=1,…,s. Функция, заданная схемой называется функцией, определенной кусочной схемой;

C) Пусть заданы функции , i=1,…,s+1 и указаны какие-то условия , j=1,…,s , принимающие значения "истина" или "ложь" для любых . Функция, заданная схемой называется функцией, определенной кусочной схемой;

D) Пусть заданы функции , i=1,…,s+1 и указаны какие-то условия , j=1,…,s , принимающие значения "истина" или "ложь" для любых и никакие два не могут быть истинными одновременно. Функция, заданная схемой называется функцией, определенной кусочной схемой

E) Пусть заданы функции , i=1,…,s+1 и указаны какие-то условия , j=1,…,s , принимающие значения "истина" или "ложь" для любых и никакие два не могут быть истинными одновременно. Функция, заданная схемой называется функцией, определенной кусочной схемой;