| dbo:abstract
|
- Částečně rekurzivní funkce (ČRF) je termín, kterým se v teorii vyčíslitelnosti označují funkce v jistém smyslu „složitější“ než tzv. primitivně rekurzivní funkce (cs)
- En lògica matemàtica i computació, les funcions recursives o també conegudes com a funcions recursives-μ són una classe de funcions dels nombres naturals en els nombres naturals que són "computables" en un sentit intuïtiu. De fet, en teoria de la computabilitat es demostra que les funcions recursives són precisament les funcions que poden ser calculades amb el formalisme de còmput més general conegut com són les màquines de Turing. Les funcions recursives estan relacionades amb les funcions primitives recursives i la seva definició inductiva es construeix basant-se en les funcions primitives recursives. No tota funció recursiva és primitiva recursiva. L'exemple més conegut és la funció d'Ackermann. Existeixen altres equivalents quant a poder d'expressió, per exemple, el càlcul lambda i les cadenes de Markov. (ca)
- Στη μαθηματική λογική και την επιστήμη των υπολογιστών, οι μ-αναδρομικές συναρτήσεις είναι μια κατηγορία από φυσικούς αριθμούς σε φυσικούς αριθμούς που είναι "υπολογίσιμη" σε μια διαισθητική αίσθηση. Στην πραγματικότητα, στη θεωρία υπολογισιμότητας έχει αποδειχθεί ότι οι μ-αναδρομικές συναρτήσεις είναι ακριβώς οι συναρτήσεις που μπορούν να υπολογιστούν από μηχανές Τιούρινγκ. Οι μ-αναδρομικές συναρτήσεις συνδέονται στενά με , και ο επαγωγικός ορισμός τους (κάτω) βασίζεται σε αυτές τις πρωτόγονες αναδρομικές συναρτήσεις. Ωστόσο, κάθε μ-αναδρομική συνάρτηση δεν είναι μια πρωτόγονη αναδρομική συνάρτηση—το πιο διάσημο παράδειγμα είναι η . Άλλες ισοδύναμες κατηγορίες συναρτήσεων είναι οι και οι συναρτήσεις που μπορούν να υπολογιστούν από τους . Το σύνολο όλων των αναδρομικών συναρτήσεων είναι γνωστό ως R στην θεωρία υπολογιστικής πολυπλοκότητας . (el)
- En lógica matemática y computación, las funciones recursivas o también conocidas como funciones recursivas-μ son una clase de funciones de los números naturales en los números naturales que son «computables» en un sentido intuitivo. De hecho, en teoría de la computabilidad se demuestra que las funciones recursivas son precisamente las funciones que pueden ser calculadas con el formalismo de cómputo más general conocido como lo son las máquinas de Turing. Las funciones recursivas están relacionadas con las funciones primitivas recursivas y su se construye basándose en la de las funciones primitivas recursivas (estas se obtienen por medio de recursión primitiva y composición de ). No toda función recursiva es primitiva recursiva. El ejemplo más conocido es la función de Ackermann. Existen otros sistemas formales equivalentes en cuanto a poder de expresión, por ejemplo el Cálculo Lambda y las cadenas de Markov. (es)
- Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle (µ für griechisch μικρότατος ‚das kleinste‘). Nach der Church-Turing-These beschreibt sie die Menge aller Funktionen, die im intuitiven Sinn berechenbar sind. Eine wichtige echte Teilmenge der μ-rekursiven Funktionen sind die primitiv-rekursiven Funktionen. Die Klasse der μ-rekursiven Funktionen stimmt überein mit der Klasse der Turing-berechenbaren Funktionen sowie weiteren gleich mächtigen Berechenbarkeitsmodellen, wie dem Lambda-Kalkül, Registermaschinen und WHILE-Programmen. Die primitiv-rekursiven Funktionen sind aus einfachen Grundfunktionen (konstante 0-Funktion, Projektionen auf ein Argument und Nachfolgerfunktion) durch Komposition und primitive Rekursion aufgebaut. Dadurch erhält man immer totale Funktionen, also Funktionen im eigentlichen Sinn.Die μ-rekursiven Funktionen sind demgegenüber partielle Funktionen, die aus denselben Konstrukten und zusätzlich durch die Anwendung des μ-Operators gebildet werden können. Durch die Anwendung des μ-Operators wird Partialität eingeführt. Jedoch ist nicht jede μ-rekursive Funktion nicht-total. Beispielsweise sind alle primitiv-rekursiven Funktionen auch μ-rekursiv. Ein Beispiel für eine nicht primitiv-rekursive, totale, μ-rekursive Funktion ist die Ackermannfunktion. (de)
- In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function). In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines (this is one of the theorems that supports the Church–Turing thesis). The μ-recursive functions are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function is a primitive recursive function—the most famous example is the Ackermann function. Other equivalent classes of functions are the functions of lambda calculus and the functions that can be computed by Markov algorithms. The subset of all total recursive functions with values in {0,1} is known in computational complexity theory as the complexity class R. (en)
- En informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini. En fait, cela fait référence à deux concepts liés, mais distincts. En théorie de la calculabilité, la classe des fonctions récursives est une classe plus générale que celle des fonctions récursives primitives, mais plus restreinte que celle des fonctions semi-calculables (ou partielles récursives). En informatique, les fonctions récursives sont des fonctions dont le calcul nécessite d'invoquer la fonction elle-même, c'est-à-dire que dans ce deuxième cas, on insiste plutôt sur la façon dont le calcul est mis en œuvre que sur la classe de fonctions. (fr)
- Nella logica matematica e nell'informatica, le funzioni ricorsive sono una classe di funzioni dai numeri naturali ai numeri naturali che sono "calcolabili" in un qualche senso intuitivo. Infatti nella teoria della calcolabilità si mostra che le funzioni ricorsive corrispondono precisamente a quelle funzioni che possono essere calcolate tramite una macchina di Turing. Le funzioni ricorsive sono un sovrainsieme delle funzioni ricorsive primitive, ed infatti la loro definizione induttiva (come vedremo nel seguito) è costruita a partire da quella di queste ultime. Esistono quindi funzioni ricorsive che non sono anche ricorsive primitive, e l'esempio più noto è quello della funzione di Ackermann. Altre classi di funzioni equivalenti a quella delle funzioni ricorsive sono le e le funzioni che possono essere calcolate da un algoritmo di Markov. (it)
- In de theoretische informatica vormen de μ-recursieve functies een klasse van functies. De klasse is gedefinieerd als de klasse van functies die de basisfuncties bevat (de constante nulfunctie, de opvolgerfunctie en de projectiefuncties) en afgesloten is onder compositie, primitieve recursie en minimalisatie. De klasse van primitief recursieve functies vormen een onderklasse van de μ-recursieve functies. De μ-recursieve functies komen precies overeen met de berekenbare functies. (nl)
- 수리논리학 및 컴퓨터 과학에서 μ-재귀 함수(영어: μ-recursive function) 또는 간단히 재귀 함수란, 자연수에서 자연수로의 '계산가능한' 부분 함수이다. 재귀 이론에서는, μ-재귀 함수와 튜링 기계로 계산가능한 함수가 일치하는 것임이 알려져 있다. 유명한 예로 피보나치 수 등이 있다. μ-재귀 함수는 원시 재귀 함수와 밀접한 관련이 있으며, 그 재귀적(귀납적) 정의가 원시 재귀 함수에 기초하고 있다. 다만, μ재귀함수가 모두 원시 재귀 함수인 것은 아닌데, 그러한 예로 아커만 함수 등이 있다. 또 재귀함수와 일치하는 개념으로는, 람다 계산에서 쓰이는 재귀함수나 (Markov algorithms)으로 계산가능한 함수 등이 있다. 전역 μ-재귀 함수를 모은 클래스는 복잡도 클래스 R과 같다. 이는 PR을 포함한다. (ko)
- μ再帰関数（ミューさいきかんすう、英: μ-recursive function）または帰納的関数（きのうてきかんすう）とは、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数（原始帰納的関数）と密接な関連があり、その帰納的定義（後述）は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。 また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。 計算複雑性理論では、全再帰関数の集合をRと称する。 (ja)
- Funkcja rekurencyjna – funkcja która jest obliczalna za pomocą maszyny Turinga. Klasę tych funkcji definiuje się za pomocą mniejszej klasy funkcji pierwotnie rekurencyjnych: (pl)
- Em lógica matemática e ciência computacional, as funções μ-recursivas são uma classe de funções parciais de números naturais para números naturais que são “computáveis” num sentido intuitivo. De fato, na teoria da computação é mostrado que as funções μ-recursivas são precisamente as que podem ser computadas por máquinas de Turing. As funções μ-recursivas são intimamente relacionadas às funções recursivas primitivas, e sua definição indutiva se baseia nestas funções recursivas primitivas. No entanto, nem toda função μ-recursivas é uma função primitiva recursiva – o mais famoso exemplo é a função de Ackermann. Outras classes equivalentes de funções são as e as funções que podem ser computadas através dos algoritmos de Markov. O conjunto de todas as funções recursivas é conhecido como R (Complexidade R) na teoria da complexidade computacional. (pt)
- 在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关，而且递归函数的归纳定义（见下）建立在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。 其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。 所有递归函数的集合叫做。 (zh)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageInterLanguageLink
| |
| dbo:wikiPageLength
|
- 17790 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:b
|
- 1 (xsd:integer)
- 2 (xsd:integer)
- 3 (xsd:integer)
- 13 (xsd:integer)
- i (en)
- m (en)
- n (en)
- q (en)
|
| dbp:p
|
- 1 (xsd:integer)
- 3 (xsd:integer)
- 7 (xsd:integer)
- m (en)
- n (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- Částečně rekurzivní funkce (ČRF) je termín, kterým se v teorii vyčíslitelnosti označují funkce v jistém smyslu „složitější“ než tzv. primitivně rekurzivní funkce (cs)
- En informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini. En fait, cela fait référence à deux concepts liés, mais distincts. En théorie de la calculabilité, la classe des fonctions récursives est une classe plus générale que celle des fonctions récursives primitives, mais plus restreinte que celle des fonctions semi-calculables (ou partielles récursives). En informatique, les fonctions récursives sont des fonctions dont le calcul nécessite d'invoquer la fonction elle-même, c'est-à-dire que dans ce deuxième cas, on insiste plutôt sur la façon dont le calcul est mis en œuvre que sur la classe de fonctions. (fr)
- In de theoretische informatica vormen de μ-recursieve functies een klasse van functies. De klasse is gedefinieerd als de klasse van functies die de basisfuncties bevat (de constante nulfunctie, de opvolgerfunctie en de projectiefuncties) en afgesloten is onder compositie, primitieve recursie en minimalisatie. De klasse van primitief recursieve functies vormen een onderklasse van de μ-recursieve functies. De μ-recursieve functies komen precies overeen met de berekenbare functies. (nl)
- 수리논리학 및 컴퓨터 과학에서 μ-재귀 함수(영어: μ-recursive function) 또는 간단히 재귀 함수란, 자연수에서 자연수로의 '계산가능한' 부분 함수이다. 재귀 이론에서는, μ-재귀 함수와 튜링 기계로 계산가능한 함수가 일치하는 것임이 알려져 있다. 유명한 예로 피보나치 수 등이 있다. μ-재귀 함수는 원시 재귀 함수와 밀접한 관련이 있으며, 그 재귀적(귀납적) 정의가 원시 재귀 함수에 기초하고 있다. 다만, μ재귀함수가 모두 원시 재귀 함수인 것은 아닌데, 그러한 예로 아커만 함수 등이 있다. 또 재귀함수와 일치하는 개념으로는, 람다 계산에서 쓰이는 재귀함수나 (Markov algorithms)으로 계산가능한 함수 등이 있다. 전역 μ-재귀 함수를 모은 클래스는 복잡도 클래스 R과 같다. 이는 PR을 포함한다. (ko)
- μ再帰関数（ミューさいきかんすう、英: μ-recursive function）または帰納的関数（きのうてきかんすう）とは、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数（原始帰納的関数）と密接な関連があり、その帰納的定義（後述）は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。 また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。 計算複雑性理論では、全再帰関数の集合をRと称する。 (ja)
- Funkcja rekurencyjna – funkcja która jest obliczalna za pomocą maszyny Turinga. Klasę tych funkcji definiuje się za pomocą mniejszej klasy funkcji pierwotnie rekurencyjnych: (pl)
- 在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关，而且递归函数的归纳定义（见下）建立在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。 其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。 所有递归函数的集合叫做。 (zh)
- En lògica matemàtica i computació, les funcions recursives o també conegudes com a funcions recursives-μ són una classe de funcions dels nombres naturals en els nombres naturals que són "computables" en un sentit intuïtiu. De fet, en teoria de la computabilitat es demostra que les funcions recursives són precisament les funcions que poden ser calculades amb el formalisme de còmput més general conegut com són les màquines de Turing. Les funcions recursives estan relacionades amb les funcions primitives recursives i la seva definició inductiva es construeix basant-se en les funcions primitives recursives. No tota funció recursiva és primitiva recursiva. L'exemple més conegut és la funció d'Ackermann. (ca)
- Στη μαθηματική λογική και την επιστήμη των υπολογιστών, οι μ-αναδρομικές συναρτήσεις είναι μια κατηγορία από φυσικούς αριθμούς σε φυσικούς αριθμούς που είναι "υπολογίσιμη" σε μια διαισθητική αίσθηση. Στην πραγματικότητα, στη θεωρία υπολογισιμότητας έχει αποδειχθεί ότι οι μ-αναδρομικές συναρτήσεις είναι ακριβώς οι συναρτήσεις που μπορούν να υπολογιστούν από μηχανές Τιούρινγκ. Οι μ-αναδρομικές συναρτήσεις συνδέονται στενά με , και ο επαγωγικός ορισμός τους (κάτω) βασίζεται σε αυτές τις πρωτόγονες αναδρομικές συναρτήσεις. Ωστόσο, κάθε μ-αναδρομική συνάρτηση δεν είναι μια πρωτόγονη αναδρομική συνάρτηση—το πιο διάσημο παράδειγμα είναι η . (el)
- Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle (µ für griechisch μικρότατος ‚das kleinste‘). Nach der Church-Turing-These beschreibt sie die Menge aller Funktionen, die im intuitiven Sinn berechenbar sind. Eine wichtige echte Teilmenge der μ-rekursiven Funktionen sind die primitiv-rekursiven Funktionen. (de)
- In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "computable" in an intuitive sense – as well as in a formal one. If the function is total, it is also called a total recursive function (sometimes shortened to recursive function). In computability theory, it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines (this is one of the theorems that supports the Church–Turing thesis). The μ-recursive functions are closely related to primitive recursive functions, and their inductive definition (below) builds upon that of the primitive recursive functions. However, not every total recursive function (en)
- En lógica matemática y computación, las funciones recursivas o también conocidas como funciones recursivas-μ son una clase de funciones de los números naturales en los números naturales que son «computables» en un sentido intuitivo. De hecho, en teoría de la computabilidad se demuestra que las funciones recursivas son precisamente las funciones que pueden ser calculadas con el formalismo de cómputo más general conocido como lo son las máquinas de Turing. Las funciones recursivas están relacionadas con las funciones primitivas recursivas y su se construye basándose en la de las funciones primitivas recursivas (estas se obtienen por medio de recursión primitiva y composición de ). No toda función recursiva es primitiva recursiva. El ejemplo más conocido es la función de Ackermann. (es)
- Nella logica matematica e nell'informatica, le funzioni ricorsive sono una classe di funzioni dai numeri naturali ai numeri naturali che sono "calcolabili" in un qualche senso intuitivo. Infatti nella teoria della calcolabilità si mostra che le funzioni ricorsive corrispondono precisamente a quelle funzioni che possono essere calcolate tramite una macchina di Turing. (it)
- Em lógica matemática e ciência computacional, as funções μ-recursivas são uma classe de funções parciais de números naturais para números naturais que são “computáveis” num sentido intuitivo. De fato, na teoria da computação é mostrado que as funções μ-recursivas são precisamente as que podem ser computadas por máquinas de Turing. As funções μ-recursivas são intimamente relacionadas às funções recursivas primitivas, e sua definição indutiva se baseia nestas funções recursivas primitivas. No entanto, nem toda função μ-recursivas é uma função primitiva recursiva – o mais famoso exemplo é a função de Ackermann. (pt)
|
| rdfs:label
|
- Funció recursiva (ca)
- Částečně rekurzivní funkce (cs)
- Μ-Rekursion (de)
- Μ-αναδρομική συνάρτηση (el)
- Función recursiva (es)
- General recursive function (en)
- Funzione ricorsiva (it)
- Fonction récursive (fr)
- Μ-재귀 함수 (ko)
- Μ再帰関数 (ja)
- Funkcja rekurencyjna (pl)
- Μ-recursieve functie (nl)
- Função μ-recursiva (pt)
- 递归函数 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
