General recursive function
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
- B
- eni
- enm
- enn
- enq
- 1
- 13
- 2
- 3
- Comment
- enIn 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
- Has abstract
- enIn 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.
- Is primary topic of
- General recursive function
- Label
- enGeneral recursive function
- Link from a Wikipage to an external page
- books.google.com/books%3Fid=0LpsXQV2kXAC&pg=PA70
- books.google.com/books%3Fid=9I7Pl00LU5gC&pg=PP1
- people.irisa.fr/Francois.Schwarzentruber/recursive_functions_to_turing_machines/
- plato.stanford.edu/entries/recursive-functions/
- Link from a Wikipage to another Wikipage
- Ackermann function
- Category:Computability theory
- Category:Theory of computation
- Church's thesis
- Church–Turing thesis
- Computability theory (computation)
- Computable function
- Computational complexity theory
- Computer science
- Domain of a function
- Fibonacci number
- Halting problem
- Integer square root
- Journal of Symbolic Logic
- Junctor
- Kleene's T predicate
- Lambda calculus
- Logical negation
- Markov algorithm
- Marvin Minsky
- Mathematical logic
- McCarthy 91 function
- Natural number
- Partial function
- Primitive recursive function
- Primitive recursive functions
- R (complexity)
- Recursion
- Recursion (computer science)
- Recursion theory
- Register machine
- Total Turing machine
- Turing machine
- Universal Turing machine
- Μ operator
- P
- enm
- enn
- 1
- 3
- 7
- SameAs
- 2eRBh
- Částečně rekurzivní funkce
- Fonction récursive
- Função μ-recursiva
- Función recursiva
- Funció recursiva
- Funkcja rekurencyjna
- Funzione ricorsiva
- Q284164
- Μ-recursieve functie
- Μ-Rekursion
- Μ-αναδρομική συνάρτηση
- Μ-рекурзивна функција
- Μ再帰関数
- Μ-재귀 함수
- פונקציה רקורסיבית
- تابع μ-بازگشتی
- 递归函数
- Subject
- Category:Computability theory
- Category:Theory of computation
- WasDerivedFrom
- General recursive function?oldid=1123730765&ns=0
- WikiPageInterLanguageLink
- Рекурсивная функция (теория вычислимости)
- WikiPageLength
- 17790
- Wikipage page ID
- 26469
- Wikipage revision ID
- 1123730765
- WikiPageUsesTemplate
- Template:Authority control
- Template:Blockquote
- Template:Cite book
- Template:Cite journal
- Template:Example needed
- Template:Expand section
- Template:Math
- Template:Mset
- Template:Mvar
- Template:Refbegin
- Template:Refend
- Template:Reflist
- Template:Rp
- Template:Sfn
- Template:Short description
- Template:Su
- Template:Unordered list
- Template:Val