En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique. 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.

PropertyValue
dbpedia-owl:abstract
  • En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique. 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. 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 que cela englobe.
  • 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. La 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 funzioni λ-ricorsive e le funzioni che possono essere calcolate da un algoritmo di Markov.
  • 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 funções λ-recursivas 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.
  • In mathematical logic and computer science, the μ-recursive functions are a class of partial functions from natural numbers to natural numbers that are "computable" in an intuitive sense. In fact, in computability theory it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines. 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 μ-recursive function is a primitive recursive function—the most famous example is the Ackermann function.Other equivalent classes of functions are the λ-recursive functions and the functions that can be computed by Markov algorithms.The set of all recursive functions is known as R in computational complexity theory.
  • 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 sistemes formals equivalents quant a poder d'expressió, per exemple, el càlcul lambda i les cadenes de Markov.
  • Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. 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.
  • 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 definición inductiva se construye basándose en la de las funciones primitivas recursivas (estas se obtienen por medio de recursión primitiva y composición de funciones iniciales). 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.
  • μ再帰関数(ミューさいきかんすう、英: μ-recursive function)または帰納的関数(きのうてきかんすう)は、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数(原始帰納的関数)と密接な関連があり、その帰納的定義(後述)は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。計算複雑性理論では、全再帰関数の集合をRと称する。
  • Čá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
dbpedia-owl:wikiPageID
  • 85472 (xsd:integer)
dbpedia-owl:wikiPageInterLanguageLink
dbpedia-owl:wikiPageLength
  • 5990 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 37 (xsd:integer)
dbpedia-owl:wikiPageRevisionID
  • 110353797 (xsd:integer)
dbpedia-owl:wikiPageWikiLink
prop-fr:wikiPageUsesTemplate
prop-fr:wikiversity
  • Récursivité dans l'algorithmique et la programmation
prop-fr:wikiversityTitre
  • Récursivité dans l'algorithmique et la programmation
  • Récursivité dans l'algorithmique et la programmation
dcterms:subject
rdfs:comment
  • En informatique et en mathématiques, le terme fonction récursive désigne une classe de fonctions calculables, autrement dit de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique. 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.
  • μ再帰関数(ミューさいきかんすう、英: μ-recursive function)または帰納的関数(きのうてきかんすう)は、数理論理学と計算機科学において、直観的に「計算可能」な自然数から自然数への部分関数のクラスである。計算可能性理論では、μ再帰関数はチューリングマシンで計算可能な関数と正確に一致することが示されている。μ再帰関数は原始再帰関数(原始帰納的関数)と密接な関連があり、その帰納的定義(後述)は原始再帰関数に基づいている。ただし、μ再帰関数が全て原始再帰関数とは言えない。そのような例としてアッカーマン関数がある。また、ラムダ計算で記述される再帰関数やマルコフアルゴリズムで計算できる関数も同じである。計算複雑性理論では、全再帰関数の集合をRと称する。
  • Čá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
  • In mathematical logic and computer science, the μ-recursive functions are a class of partial functions from natural numbers to natural numbers that are "computable" in an intuitive sense. In fact, in computability theory it is shown that the μ-recursive functions are precisely the functions that can be computed by Turing machines.
  • Die Klasse Pr der μ-rekursiven Funktionen oder partiell-rekursiven Funktionen spielt in der Rekursionstheorie, einem Teilgebiet der theoretischen Informatik, eine wichtige Rolle. Nach der Church-Turing-These beschreibt sie die Menge aller Funktionen, die im intuitiven Sinn berechenbar sind.
  • 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.
  • 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.
  • 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.
  • 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.
rdfs:label
  • Fonction récursive
  • Funció recursiva
  • Función recursiva
  • Funkcja rekurencyjna
  • Funzione ricorsiva
  • Função μ-recursiva
  • Částečně rekurzivní funkce
  • Μ-Rekursion
  • Μ-recursive function
  • Μ再帰関数
owl:sameAs
http://www.w3.org/ns/prov#wasDerivedFrom
foaf:isPrimaryTopicOf
is dbpedia-owl:wikiPageWikiLink of
is foaf:primaryTopic of