записать предикат, показать примитивную рекурсивность

[Marischa]

Помогите записать предикат в виде характеристической функции и доказать, что он примитивно рекурсивный.
Pr(x,y):"x и y взаимно просты "

1. Если они взаимно просты, то их НОД равен 1. А как дальше?

[maxmatem]

Как-то так$ \[ \phi (x) = sg|d(x) - 2| \]$, где $\[ d(x) = \sum\limits_{k = 1}^x {s\bar g} (rest(x;k)) \]$


Но наверное можно как-то по проще

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

maxmatem в сообщении #367778 писал(а):

Как-то так...

Что-то странное: в ответе должна быть функция от двух переменных, а у Вас от одной.

[maxmatem]

ой ! я же написал ф-ию, для предиката "х-простое число". Извеняюсь

[Maslov]

Marischa, вот здесь почитайте Петер Р. Рекурсивные функции (стр. 26-27).

[Marischa]

В учебнике Петера просто пишут про НОД, а у меня именно взаимно простые числа..

[Joker_vD]

Marischa
Два числа взаимно просты тогда и только тогда, когда их НОД равен 1.

[Marischa]

я это знаю! Но там, как то не так и не про то.

[Maslov]

(Оффтоп)

Marischa в сообщении #368505 писал(а):

В учебнике Петера

Фамилия не склоняется: Р.Петер -- женщина.

[Marischa]

Буду знать, и всё же задача от этого проще не становится.

[Maslov]

Marischa в сообщении #368551 писал(а):

задача от этого проще не становится.

А в чём конкретно проблема?
Какой предикат называется примитивно-рекурсивным?

[Marischa]

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

[Maslov]

Дайте, пожалуйста, определения двух понятий:
1. характеристической функции предиката
2. примитивно-рекурсивного предиката

[Marischa]

характеристическая функция - это функция, выражающая этот предикат, принимающая значения 1 или 0.
И вот если эта функция примитивно-рекурсивна, то и сам предикат примитивно-рекурсивен.

[Maslov]

Если нам заданы значения $x$ и $y$, в каком случая характеристическая функция Вашего предиката должна принимать значение 0, а в каком -- значение 1?