Частично рекурсивные функции

[nbyte]

Здравствуйте.
Помогите разобраться с понятием частично рекурсивных функции.
Пытался по всякому разобраться с этим понятием, но вижу что безуспешно. (Ну просто не понимаю и всё)
Может тут найдутся люди которые смогут более менее элементарно объяснить что это такое вообще и как говорится с чем это всё едят (зачем это всё нужно и где может пригодится).
Попробую описать, что именно мне не понятно.

Допустим с примитивно рекурсивным классом функции у меня более менее сформировалось понятие что это такое.
Я понимаю его как - класс где функции состоят
(1) Из простейших функций
(2) Из функции созданных из простейших преминя к ним рекурсию
(3) Из (1) и (2) при помощи оператора суперпозиции.

А с частично рекурсивными у меня никак не выходит понять, потому-что не понимаю до конца что такое оператор минимизации.
Понял только что при помощи него можно найти минимальное значение последнего аргумента при заданном наборе аргументов, но зачем это нужно я так и не понял.
И как-то можно найти при помоши него обратную функцию, я тоже никак не понял.
Интуитивно вроду-бы понимаю что он нужен для того чтобы можно было составить класс функции которые не обладают биекцией, но точно понять не могу.

Вообще у меня такой тупик с изучением теории алгоритмов, что даже трудно объяснить что именно мне непонятно. Запутался сильно, поймите меня правильно.
Буду благорен если кто-то хоть как-то поможет.

[nbyte]

Ну не понимаю почему некто не пишет.
Могу по новому проблему описать если нужно.
Возможно что-то плохо, неформально написал.

от модератора AD:
1. Потому что тут у нас не чат, а форум. (!) Нет, серьёзно.
Категорически запрещается искусственно "поднимать" свою тему с помощью неинформативных сообщений.
Удалил парочку предыдущих.
2. Потому что в Москве час ночи, а дальше - больше.

[Профессор Снэйп]

Слишком много мусора придётся разгребать у Вас в голове. Никто не хочет даже за это браться

По каким книгам Вы это изучаете? Может, можно будет просто литературу получше посоветовать, из которой Вы больше поймёте.

-- Чт фев 04, 2010 09:26:28 --

nbyte в сообщении #285173 писал(а):

Допустим с примитивно рекурсивным классом функции у меня более менее сформировалось понятие что это такое.
Я понимаю его как - класс где функции состоят
(1) Из простейших функций
(2) Из функции созданных из простейших преминя к ним рекурсию
(3) Из (1) и (2) при помощи оператора суперпозиции.

Начнём с того, что это неправильно

[nbyte]

Цитата:

По каким книгам Вы это изучаете? Может, можно будет просто литературу получше посоветовать, из которой Вы больше поймёте.

Да нет, мне просто что-то не доходит.
Пробовал по разным книгам понять.

Цитата:

Начнём с того, что это неправильно

A тут всё не правильно, или только часть?

[Профессор Снэйп]

Вот если какие-то функции получаются суперпозициями из простейших, а потом другая функция получается примитивной рекурсией из этих суперпозиций, эта другая функция будет примитивно рекурсивной или нет?

[nbyte]

Вроде-бы да.

Потому-что, суперпозиция из двух простейших ф-ций будет функция обладающая примитивной рекурсией. Например если рассматривать машину Тьюринга, то выполнение суперпозии будет выглядить по следующему правилу: сначала выполняется первая функция, когда автомат переходит в конечное состояиние, то начинает выполнятся вторая функция, после чего автомат переходит в конечное состояние.

А если применить оператор примитивной рекурсии к примитивно рекурсивной функции, то получится рекурсивная функция.

Я так это понимаю. Незнаю, насколько правильно.

[Профессор Снэйп]

nbyte в сообщении #285781 писал(а):

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

Бессмысленное сочетание слов! Функция не может обладать или не обладать примитивной рекурсией.

Примитивная рекурсия --- это способ задания новых функций из уже имеющихся. Правильный термин --- "примитивно рекурсивная функция", это функция, которую можно задать из простейших применением конечного числа операторов примитивной рекурсии и суперпозиции. Выражайтесь грамотно!

nbyte в сообщении #285781 писал(а):

сначала выполняется первая функция

Функция не может "выполняться", опять бессмысленное сочетание слов. В подобных случаях обычно говорят, что функции "вычисляются".

nbyte в сообщении #285781 писал(а):

А если применить оператор примитивной рекурсии к примитивно рекурсивной функции, то получится рекурсивная функция.

То ничерта не получится. К одной функции применять оператор примитивной рекурсии нельзя, нужны две.

А если применить оператор примитивной рекурсии к двум примитивно рекурсивным функциям, то получится опять примитивно рекурсивная функция. Хотя, конечно, каждая примитивно рекурсивная функция является рекурсивной.

nbyte в сообщении #285781 писал(а):

Я так это понимаю. Незнаю, насколько правильно.

Думаю, что неправильно.

Примитивно рекурсивная функция --- это функция, которая получается из простейших применением любого конечного числа операторов суперпозиции и примитивной рекурсии, в любой последовательности.

Давайте для начала остановимся здесь. Покажите, что сумма и произведение --- примитивно рекурсивные функции.

[nbyte]

Цитата:

Давайте для начала остановимся здесь. Покажите, что сумма и произведение --- примитивно рекурсивные функции.

Я тут точно не знаю, как правильно доказать. Только интуитивно понимаю.

Если взять сумму, то будет $S(f(x), g(x))$, тогда если $f(x), g(x)$ рекурсивные, то вычисля значения этих функций мы подставим их в функцию $S(x,y)$, которая тоже является рекурсивной в качестве аргументов, то тогда снова получим примитивно-рекурсивную функцию.

Если взять умножение, то это тоже самое что и сумма, только выполняется много раз.

[Профессор Снэйп]

nbyte в сообщении #285889 писал(а):

Только интуитивно понимаю.

Плохо понимаете!

Я не знаю, что посоветовать, кроме поступления в приличный университет и прослушивания там курса теории алгоритмов.

Попробуйте прочитать здесь, стр. 51 - 64. Может, лучше поймёте.

[nbyte]

А, нашел я эти два доказательства.
В принципе, в этом учебнике написано, что-то похожее как и в других учебниках.
Сами определения я вроде-бы понимаю и задачи решать умею. Но саму сущность я так и не смог постичь.

Мне нужно это всё глубоко понять, так на экзамене у меня может быть, что нужно доказать например

Цитата:

Определение
Для множества всех n-аргументных частично-рекурсивных функций, существует $\widetildeD^{n + 1}}({x_0},{x_1},...,{x_n})$

Цитата:

Доказательство
У любой частично-рекурсивной функции график есть рекурсивно счетное множество, так как совпадает с $\overline{sg}(|f(x_1,...,x_n)-y|-1)$ областью определения.
Следовательно, какой-бы нибыла функция $f(x_1,...,x_n)$, существует такая примитивно-рекурсивная функция $g(x_1,...,x_n,y,z)$, что $(x_1,...,x_n,y,z) \in A$ тогда и только тогда, когда существет такой $z$, что $g(x_1,...,x_n,y,z)=0$.

Например мне непонятно, что означает формула
$\overline{sg}(|f(x_1,...,x_n)-y|-1)$

[Профессор Снэйп]

nbyte в сообщении #286014 писал(а):

Например мне непонятно, что означает формула
$\overline{sg}(|f(x_1,...,x_n)-y|-1)$

А что здесь может быть непонятно? Обычная суперпозиция функций. Функция $\overline{\mathrm{sg}}$ определяется так:

$$ \overline{\mathrm{sg}}(x) = \begin{cases} 1, &x=0 \\ 0, &x>0 \end{cases} $$

Соответственно,

$$ \overline{\mathrm{sg}}(|f(x_1,\ldots,x_n)-y|-1) = \begin{cases} 1, &f(x_1, \ldots, x_n) = y \pm 1 \\ \text{не определено}, &f(x_1,\ldots,x_n) = y \\ 0, &\text{иначе} \end{cases} $$

Вторая строчка возникает из-за того, что при равенстве $f(x_1,\ldots,x_n) = y$ аргумент $\overline{\mathrm{sg}}$ оказывается отрицательным. Если неопределённость нежелательна, нужно воткнуть ещё один модуль (допускаю возможность, что в источнике, который Вы цитируете, допущена опечатка).

nbyte в сообщении #286014 писал(а):

Но саму сущность я так и не смог постичь.

Не знаю, чем Вам помочь. Увы

Чувствую, что с Вами нужно заниматься довольно много времени, и "вживую". Найдите хорошего репетитора. Если Вы в Новосибирске, напишите в личку, может, смогу помочь.

-- Пн фев 08, 2010 08:39:43 --

P. S. Процитированное доказательство какое-то бредовое. Начиная с терминов (нет термина "рекурсивно счётное", есть термин "рекурсивно перечислимое") и заканчивая замечанием про область определения. Предполагаю, что имелось в виду следующее:

Цитата:

График частично рекурсивной функции является рекурсивно перечислимым множеством, так как совпадает с областью определения функции $\overline{\mathrm{sg}}(|f(x_1,\ldots,x_n)-y|)$, где

$$ \overline{\mathrm{sg}}(x) = \begin{cases} 1, &x=0 \\ \text{не определено}, &x>0 \end{cases} $$

Функция $\overline{\mathrm{sg}}$ обычно задаётся так, как я написал выше, но допускаю, что бывает и нестандартное задание. Посмотрите, как она точно определялась в том источнике, который Вы цитируете.

Далее используется то, что каждое рекурсивно перечислимое множество есть проекция примитивно рекурсивного, это как раз понятно...

-- Пн фев 08, 2010 08:41:24 --

nbyte в сообщении #286014 писал(а):

Мне нужно это всё глубоко понять, так на экзамене у меня может быть, что нужно доказать например...

Вас на экзамене просят доказывать определения??? О ужас, летящий на крыльях ночи!!!