Операція примітивної рекурсії

Опера́ція приміти́вної реку́рсії — двомісна операція, широко вживана в теорії рекурсивних функцій. Пара рекурсивних функцій: перша функція від $\!m+2$ змінних $\!h(x_{1},...,x_{m+1},\ x_{m+2})$ , а інша функція від $\!m$ змінних $\!g(x_{1},...,x_{m})$ , утворює функцію від $\!m+1$ змінних $\!f(x_{1},...,x_{m+1})$ за такою схемою:

\!f(x_{1},...,x_{m},\ 0)=g(x_{1},...,x_{m})

\!f(x_{1},...,x_{m},\ n+1)=h(x_{1},...,x_{m},\ n,\ f(x_{1},...,x_{m},\ n))

Див. також

Рекурсивна функція

Джерела

Енциклопедія кібернетики : у 2 т. / за ред. В. М. Глушкова. — Київ : Гол. ред. Української радянської енциклопедії, 1973. т. 2, ст. 129.
Jensen, Ronald B.; Karp, Carol (1971). Primitive recursive set functions. Axiomatic Set Theory. Proc. Sympos. Pure Math. XIII, Part I. Providence, R.I.: Amer. Math. Soc. с. 143–176. ISBN 9780821802458. MR 0281602.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.