| dbo:abstract
|
- Les funcions recursives primitives es defineixen usant com a operacions principals la recursió i la composició i formen un subconjunt estricte de les funcions recursives, que són les funcions computables. El terme el va proposar originalment en Rózsa Péter. En Teoria de la computabilitat, les funcions recursives primitives són una classe de funcions que formen un bloc important per la formalització completa de la computabilitat. Aquestes funcions també són importants en Teoria de la demostració. Moltes de les funcions estudiades a Teoria de nombres i les aproximacions a les funcions de valor real són recursives primitives. Per exemple, la suma, divisió, factorial, exponencial i l'n-èsim primer són funcions recursives primitives. De fet, és difícil definir una funció que sigui recursiva però que no es pugui definir amb recursió primitiva. El conjunt de funcions recursives primitives es coneix com a en Complexitat computacional. Tota funció recursiva primitiva és una funció recursiva general. (ca)
- Primitivně rekurzivní funkce (PRF) je v teorii vyčíslitelnosti v jistém smyslu „jednoduchá“ funkce. Jejím rozšířením je částečně rekurzivní funkce (ČRF). (cs)
- Primitiv-rekursive Funktionen sind totale Funktionen, die aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitive) Rekursion gebildet werden können. Die primitive Rekursion lässt sich auf Richard Dedekinds 126. Theorem in Was sind und was sollen die Zahlen? (1888) zurückführen. Die primitiv rekursive Arithmetik geht auf Thoralf Skolem (1923) zurück. Der Begriff primitiv-rekursive Funktion wurde von der ungarischen Mathematikerin Rózsa Péter geprägt. Primitiv-rekursive Funktionen spielen in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine Rolle. Sie treten im Zusammenhang mit der Explikation des Berechenbarkeitsbegriffs auf. Alle primitiv-rekursiven Funktionen sind im intuitiven Sinn berechenbar. Sie schöpfen aber nicht alle intuitiv berechenbaren Funktionen aus, Beispiele dafür sind die Ackermannfunktion und die Sudanfunktion, welche beide berechenbar, aber nicht primitiv-rekursiv sind. Eine vollständige Erfassung des Berechenbarkeitsbegriffs gelingt erst durch die µ-rekursiven Funktionen. Für primitiv-rekursive Funktionen ist es möglich, ein Komplexitätsmaß zu definieren, d. h., es kann die Dauer der Berechnung eines ihrer Funktionswerte vorab ermittelt werden. Die Klasse der primitiv-rekursiven Funktionen und die der LOOP-berechenbaren (vgl. LOOP-Programm) Funktionen sind äquivalent. (de)
- En teoría de la computabilidad, la recursión primitiva permite definir una clase de funciones que forman un importante paso en la formalización de la noción de computabilidad. Se definen usando como principales operaciones la recursión y composición de funciones y forman un subconjunto estricto de las funciones recursivas, que son precisamente las funciones computables. Las funciones recursivas se definen agregándole a la recursión primitiva el operador de búsqueda no acotada que permite definir funciones parciales. Muchas de las funciones normalmente estudiadas en teoría de los números, y las aproximaciones a las funciones de valor real utilizan la recursión primitiva. Como ejemplo de ellas se tiene la suma, la división, el factorial, el enésimo primo, etc. De hecho, no es fácil definir una función que sea recursiva pero que no se pueda definir con recursión primitiva. (es)
- En théorie de la calculabilité, une fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas primitifs de récursion et de composition. Ces fonctions constituent un sous-ensemble strict des fonctions récursives. (fr)
- In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its time complexity is bounded above by a primitive recursive function of the input size. It is hence not that easy to devise a computable function that is not primitive recursive; some examples are shown in section below. The set of primitive recursive functions is known as PR in computational complexity theory. (en)
- Nella teoria della calcolabilità, le funzioni ricorsive primitive sono una classe di funzioni che possono essere definite applicando un numero finito di volte la ricorsione e la composizione a partire da particolari funzioni base (funzioni zero, funzione successore e funzioni selettive o proiettive) e costituiscono un passo fondamentale nella costruzione di una completa formalizzazione della calcolabilità. Le funzioni ricorsive primitive sono un sottoinsieme stretto delle funzioni ricorsive (queste ultime corrispondono esattamente alle funzioni calcolabili). La classe più ampia delle funzioni ricorsive è definita aggiungendo la possibilità di avere funzioni parziali e introducendo un operatore di ricerca non limitato. Molte delle funzioni solitamente studiate nella teoria dei numeri, e le approssimazioni di funzioni a valori reali, sono primitive ricorsive, come l'addizione, la divisione, il fattoriale, l'esponenziale, la ricerca dell'ennesimo numero primo, e molte altre (Brainerd and Landweber, 1974). Infatti è difficile progettare una funzione che sia ricorsiva totale ma non primitiva ricorsiva, anche se se ne conoscono alcune, come la funzione di Ackermann. Perciò studiando questo particolare tipo di funzioni è possibile scoprire proprietà che hanno conseguenza di ampia portata. Le funzioni ricorsive primitive possono essere calcolate dalle macchine che terminano sempre, mentre le funzioni ricorsive richiedono sistemi con la stessa potenza di calcolo delle macchine di Turing. (it)
- 계산 가능성 이론에서 원시 재귀 함수(영어: primitive recursive function)은 원시 재귀와 합성 연산으로 정의되는 함수이다. 원시 재귀 함수의 클래스는 μ-재귀 함수의 클래스의 부분집합이며, μ-재귀 함수와는 달리 전역적(total)이다. 원시 재귀 함수의 클래스는 PR로 표기되며, 이는 R의 일부이다. (ko)
- 原始再帰関数（げんしさいきかんすう、英: Primitive Recursive Function）とは、原始再帰と合成で定義される関数であり、再帰関数（計算可能関数）の部分集合である。原始帰納的関数とも。 再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。 数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている（の節を参照）。 計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。 原始再帰関数のクラスとは、while文を使用せずに計算できる（すなわちfor文のみで計算可能な）関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。 (ja)
- In de theoretische informatica vormen de primitief recursieve functies een klasse van totale, berekenbare functies. De klasse is gedefinieerd als de kleinste klasse van functies die de basisfuncties (constante functies, opvolgerfunctie en projectie) bevat, en afgesloten is onder compositie en primitieve recursie. Alle primitief recursieve functies zijn totaal en berekenbaar, maar er bestaan totale en berekenbare functies die niet primitief recursief zijn, zoals de Ackermannfunctie. Als we de klasse van primitief recursieve functies ook onder minimalisering afsluiten, ontstaat de klasse van μ-recursieve functies, die wel precies met de berekenbare functies overeenkomt. (nl)
- As funções recursivas primitivas são definidas através do uso da recursão primitiva e da Composição como operações centrais. Na teoria computacional, funções recursivas primitivas são uma classe de funções que formam um importante bloco de construção importante no caminho para chegar à total formalização da computabilidade. Essas funções são de grande importância para a teoria da prova. Muitas das funções que normalmente são estudadas na teoria dos números, são recursivas primitivas. Por exemplo: adição, divisão, fatorial e exponenciação são todas recursivas primitivas. (pt)
- Рекурсивні функції — клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій. У зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу, в математичній логіці, основах математики та кібернетиці, як ефективно обчислювані функції. Тільки такі функції можна обчислювати на електронних обчислювальних машинах та інших цифрових пристроях. При введенні класу ефективно обчислюваних функцій природним чином виникає питання уточнення конструктивних об'єктів, на яких визначено ці функції. Клас всіх таких об'єктів широкий. В той же час, з допомогою методу , запропонованого австрійським математиком Куртом Геделем, всі такі об'єкти легко зводяться до натуральних чисел. Тому рекурсивні функції було введено як функції, що визначені на множині натуральних чисел і набувають значення з тієї ж множини натуральних чисел. Перенесення понять і методів вироблених в теорії рекурсивних функцій на функції визначені на складніших конструктивних областях (множини слів деякого алфавіту, формул деякої теорії, графів тощо) не створює принципових ускладнень. (uk)
- 在可计算性理论中，原始递归函数（英語：primitive recursive functions）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。 通常在数论中研究的很多函数，近似于实数值函数，比如加法、除法、阶乘、指数，找到第 n 个素数等等是原始递归的（Brainerd and Landweber, 1974）。实际上，很难设计不是原始递归的函数，尽管某些函数是已知的(比如阿克曼函数)。所以，通过研究它们，我们能发现有广泛影响的结论的那些性质。 原始递归函数可以用总是停机的图灵机计算，而递归函数需要图灵完全系统。 原始递归函数的集合在计算复杂性理论中叫做PR。 (zh)
- Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций:
* ;
* ;
* . Последние совпадают с классом вычислимых по Тьюрингу функций. Определения этих трёх классов сильно связаны. Они были введены Куртом Гёделем с целью формализации понятия вычислимости. Множество частично рекурсивных функций включает в себя множество общерекурсивных функций, а общерекурсивные функции включают в себя примитивно рекурсивные функции. Частично рекурсивные функции иногда называют просто рекурсивными функциями. (ru)
|
| rdfs:comment
|
- Primitivně rekurzivní funkce (PRF) je v teorii vyčíslitelnosti v jistém smyslu „jednoduchá“ funkce. Jejím rozšířením je částečně rekurzivní funkce (ČRF). (cs)
- En théorie de la calculabilité, une fonction récursive primitive est une fonction construite à partir de la fonction nulle, de la fonction successeur, des fonctions projections et des schémas primitifs de récursion et de composition. Ces fonctions constituent un sous-ensemble strict des fonctions récursives. (fr)
- 계산 가능성 이론에서 원시 재귀 함수(영어: primitive recursive function)은 원시 재귀와 합성 연산으로 정의되는 함수이다. 원시 재귀 함수의 클래스는 μ-재귀 함수의 클래스의 부분집합이며, μ-재귀 함수와는 달리 전역적(total)이다. 원시 재귀 함수의 클래스는 PR로 표기되며, 이는 R의 일부이다. (ko)
- 原始再帰関数（げんしさいきかんすう、英: Primitive Recursive Function）とは、原始再帰と合成で定義される関数であり、再帰関数（計算可能関数）の部分集合である。原始帰納的関数とも。 再帰理論において原始再帰関数は、計算可能性の完全形式化のための重要な要素となる関数のクラスの1つである。このような関数は証明論においても重要である。 数論が扱う関数の多くや、実数を値とする関数の近似は原始再帰的であり、加法、除法、階乗、指数、n 番目の素数を求める関数などがある (Brainerd and Landweber, 1974年)。実際、原始再帰的でない関数を考案するのは難しいが、いくつかの例が知られている（の節を参照）。 計算複雑性理論では、原始再帰関数の集合をPRと呼ぶ。 原始再帰関数のクラスとは、while文を使用せずに計算できる（すなわちfor文のみで計算可能な）関数のクラスと一致する。原始再帰関数のクラスはグジェゴルチク階層と呼ばれる階層に分類される。 (ja)
- In de theoretische informatica vormen de primitief recursieve functies een klasse van totale, berekenbare functies. De klasse is gedefinieerd als de kleinste klasse van functies die de basisfuncties (constante functies, opvolgerfunctie en projectie) bevat, en afgesloten is onder compositie en primitieve recursie. Alle primitief recursieve functies zijn totaal en berekenbaar, maar er bestaan totale en berekenbare functies die niet primitief recursief zijn, zoals de Ackermannfunctie. Als we de klasse van primitief recursieve functies ook onder minimalisering afsluiten, ontstaat de klasse van μ-recursieve functies, die wel precies met de berekenbare functies overeenkomt. (nl)
- As funções recursivas primitivas são definidas através do uso da recursão primitiva e da Composição como operações centrais. Na teoria computacional, funções recursivas primitivas são uma classe de funções que formam um importante bloco de construção importante no caminho para chegar à total formalização da computabilidade. Essas funções são de grande importância para a teoria da prova. Muitas das funções que normalmente são estudadas na teoria dos números, são recursivas primitivas. Por exemplo: adição, divisão, fatorial e exponenciação são todas recursivas primitivas. (pt)
- 在可计算性理论中，原始递归函数（英語：primitive recursive functions）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。 通常在数论中研究的很多函数，近似于实数值函数，比如加法、除法、阶乘、指数，找到第 n 个素数等等是原始递归的（Brainerd and Landweber, 1974）。实际上，很难设计不是原始递归的函数，尽管某些函数是已知的(比如阿克曼函数)。所以，通过研究它们，我们能发现有广泛影响的结论的那些性质。 原始递归函数可以用总是停机的图灵机计算，而递归函数需要图灵完全系统。 原始递归函数的集合在计算复杂性理论中叫做PR。 (zh)
- Термин рекурсивная функция в теории вычислимости используется для обозначения трёх классов функций:
* ;
* ;
* . Последние совпадают с классом вычислимых по Тьюрингу функций. Определения этих трёх классов сильно связаны. Они были введены Куртом Гёделем с целью формализации понятия вычислимости. Множество частично рекурсивных функций включает в себя множество общерекурсивных функций, а общерекурсивные функции включают в себя примитивно рекурсивные функции. Частично рекурсивные функции иногда называют просто рекурсивными функциями. (ru)
- Les funcions recursives primitives es defineixen usant com a operacions principals la recursió i la composició i formen un subconjunt estricte de les funcions recursives, que són les funcions computables. El terme el va proposar originalment en Rózsa Péter. En Teoria de la computabilitat, les funcions recursives primitives són una classe de funcions que formen un bloc important per la formalització completa de la computabilitat. Aquestes funcions també són importants en Teoria de la demostració. Tota funció recursiva primitiva és una funció recursiva general. (ca)
- En teoría de la computabilidad, la recursión primitiva permite definir una clase de funciones que forman un importante paso en la formalización de la noción de computabilidad. Se definen usando como principales operaciones la recursión y composición de funciones y forman un subconjunto estricto de las funciones recursivas, que son precisamente las funciones computables. Las funciones recursivas se definen agregándole a la recursión primitiva el operador de búsqueda no acotada que permite definir funciones parciales. (es)
- Primitiv-rekursive Funktionen sind totale Funktionen, die aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgefunktion) durch Komposition und (primitive) Rekursion gebildet werden können. Die primitive Rekursion lässt sich auf Richard Dedekinds 126. Theorem in Was sind und was sollen die Zahlen? (1888) zurückführen. Die primitiv rekursive Arithmetik geht auf Thoralf Skolem (1923) zurück. Der Begriff primitiv-rekursive Funktion wurde von der ungarischen Mathematikerin Rózsa Péter geprägt. Primitiv-rekursive Funktionen spielen in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine Rolle. Sie treten im Zusammenhang mit der Explikation des Berechenbarkeitsbegriffs auf. (de)
- In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The set of primitive recursive functions is known as PR in computational complexity theory. (en)
- Nella teoria della calcolabilità, le funzioni ricorsive primitive sono una classe di funzioni che possono essere definite applicando un numero finito di volte la ricorsione e la composizione a partire da particolari funzioni base (funzioni zero, funzione successore e funzioni selettive o proiettive) e costituiscono un passo fondamentale nella costruzione di una completa formalizzazione della calcolabilità. (it)
- Рекурсивні функції — клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій. У зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу, в математичній логіці, основах математики та кібернетиці, як ефективно обчислювані функції. Тільки такі функції можна обчислювати на електронних обчислювальних машинах та інших цифрових пристроях. (uk)
|
