Помогите решить теорию алгоритмов...:(

[Marischa]

Нужно доказать примитивную рекурсивность предиката "x=y" .
Сначала нужно представить в виде функции, но как тут представишь?

[Xaositect]

И чему эта функция (характеристическая) по определению должна быть равна?

[Marischa]

Не знаю. Там написано I (x,y): "x=y". Наверное там должны быть 1 и 0, это же предикат...

[Xaositect]

Угу. И где должно быть 0, а где 1?

[Marischa]

если x=1, то у=1, а если х=0,то и у=0. Думаю так. А дальше?

[Xaositect]

Неа.
Давайте тогда сначала. Определение примитивно-рекурсивного предиката в книжке есть? Есть в нем слова "характеристическая функция"?

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

$\overline{\mathrm{sg}}((x \frac{\,.\,}{} y) + (y \frac{\,.\,}{} x))$

[Marischa]

да, там есть и эта характеристическая функция равна 0, если ложно, и 1, если истина. Теперь этот предикат я должна написать в виде функции каким-то образом, так?

[Xaositect]

Да, Вы должны выразить функцию $eq(x,y) = \begin{cases}1, x = y\\0, x\neq y\end{cases}$.
Что за Вас сделал Профессор Снейп.

[Marischa]

Всё равно не понимаю, а как дальше доказать, что каждая из этиз функций примитивно рекурсивна? С помощью базовых функций?

-- Сб окт 09, 2010 17:46:36 --

Т.е. 0 - это базовая примитивно рекурсивная функция. А f(x)=1 - надо доказать, через базовую S(x)=x+1 ?