alt text

задан 2 Мар 16:05

10|600 символов нужно символов осталось
0

Рассмотрим функцию $%\phi(x,y)$%, заданную схемой рекурсии:

$%\phi(x,0)=1$%

$%\phi(x,y+1)=\phi(x,y)\cdot|g(x)-h(y)|$%

При этом строится примитивно-рекурсивная функция $%\phi(x,y)=|(g(x)-h(0))(g(x)-h(1)\ldots(g(x)-h(y-1))|$%. Далее рекурсией по $%x$% строим функцию $%\psi(x,y)$%, полагая

$%\psi(0,y)=1$%

$%\psi(x+1,y)=\psi(x,y)\cdot\phi(x,y)$%

Если есть требование вести рекурсию по последней переменной, то можно переставить переменные, но этот момент не принципиален.

В итоге получается, что $%\psi(x,y)$% равно модулю произведения разностей вида $%g(i)-h(j)$% при $%0\le i < x$% и $%0\le j < y$%. При этом $%\psi(y+1,y+1)$% равно нулю, если $%g(i)=h(j)$% для некоторых $%0\le i,j\le y$%, и положительна в противном случае. Остаётся подставить эту функцию в $%\overline{\rm sg}$%, которая равна 1 в нуле и равна 0 для остальных значений аргумента.

ссылка

отвечен 2 Мар 16:58

@falcao, спасибо большое!

(2 Мар 19:20) Flexibility

@falcao, уточню в последнем абзаце вы писали, что "При этом ψ(y+1,y+1) равно нулю..." точно ли ψ(y+1,y+1), а не ψ(x+1,y+1)?

(3 Мар 16:41) Flexibility

@EXODUS: это не опечатка. Обратите внимание, что в условии фигурирует один параметр-ограничение для значений обеих переменных. Они там <=y, то есть строго меньше y+1. Поэтому такое число на оба места и подставляем.

(3 Мар 18:51) falcao

@falcao, точно все верно. Спасибо!

(3 Мар 19:11) Flexibility
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×3,355
×199
×124

задан
2 Мар 16:05

показан
151 раз

обновлен
3 Мар 19:11

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru