2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Помогите показать примитивную рекурсивность
Сообщение13.12.2009, 11:15 
Задание:
Показать примитивную рекурсивность функции:
$f(x,y)=
\left\{ \begin{array}{ll}
3,&2\le y\le 6\\
x+1,&\mbox{иначе}
\end{array} \right.
$
переписал эту функцию в виде:
$f(x,y)=3p(g(y))+(x+1)g(y)$
, где
$p(x)=
\left\{ \begin{array}{ll}
1,&x=0\\
0,&x>1
\end{array} \right.
$

$g(x)=
\left\{ \begin{array}{ll}
1,&y<2\mbox{ или }y>6\\
0,&\mbox{иначе}
\end{array} \right.
$
так как сумма примитивно рекурсивных функций есть примитивная рекурсивная функция, то нужно показать что функции $p(x)$ и $g(x)$ - примитивно рекурсивны.
док-во, что p(x) примитивно рекурсивна:
$p(0)=1$
$p(x+1)=O(p(x))$
Подскажите как показать, что $g(x)$ - примитивно рекурсивна?
или сама идея решения неверна? :(

 
 
 
 Re: Помогите показать примитивную рекурсивность
Сообщение13.12.2009, 13:53 
Аватара пользователя
Dresk в сообщении #270878 писал(а):
как показать, что g(x)- примитивно рекурсивна?

$$
g(x) = p\big((x \mathop{\frac{.}{\phantom{ii}}} 1) \cdot (7 \mathop{\frac{.}{\phantom{ii}}} x)\big)
$$

 
 
 
 Re: Помогите показать примитивную рекурсивность
Сообщение15.12.2009, 10:18 
большое спасибо за подсказку!
очень помогло!

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group