Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Computable_function> ?p ?o. }
Showing items 1 to 29 of
29
with 100 items per page.
- Computable_function abstract "Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines. Any definition, however, must make reference to some specific model of computation but all valid definitions yield the same class of functions.Particular models of computability that give rise to the set of computable functions are the Turing-computable functions and the μ-recursive functions.Before the precise definition of computable function, mathematicians often used the informal term effectively calculable. This term has since come to be identified with the computable functions. Note that the effective computability of these functions does not imply that they can be efficiently computed (i.e. computed within a reasonable amount of time). In fact, for some effectively calculable functions it can be shown that any algorithm that computes them will be very inefficient in the sense that the running time of the algorithm increases exponentially (or even superexponentially) with the length of the input. The fields of feasible computability and computational complexity study functions that can be computed efficiently.According to the Church–Turing thesis, computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space. Equivalently, this thesis states that any function which has an algorithm is computable. Note that an algorithm in this sense is understood to be a sequence of steps a person with unlimited time and an infinite supply of pen and paper could follow.The Blum axioms can be used to define an abstract computational complexity theory on the set of computable functions. In computational complexity theory, the problem of determining the complexity of a computable function is known as a function problem.".
- Computable_function wikiPageID "1139338".
- Computable_function wikiPageRevisionID "592010430".
- Computable_function hasPhotoCollection Computable_function.
- Computable_function subject Category:Computability_theory.
- Computable_function subject Category:Theory_of_computation.
- Computable_function comment "Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithm. They are used to discuss computability without referring to any concrete model of computation such as Turing machines or register machines.".
- Computable_function label "Computable function".
- Computable_function label "Fonction calculable".
- Computable_function label "Función computable".
- Computable_function label "Funkcja obliczalna".
- Computable_function label "Funzione calcolabile".
- Computable_function label "Função computável".
- Computable_function label "Вычислимая функция".
- Computable_function label "دوال حسابية".
- Computable_function label "可计算函数".
- Computable_function label "計算可能関数".
- Computable_function sameAs Función_computable.
- Computable_function sameAs Fonction_calculable.
- Computable_function sameAs Funzione_calcolabile.
- Computable_function sameAs 計算可能関数.
- Computable_function sameAs 계산_가능한_함수.
- Computable_function sameAs Funkcja_obliczalna.
- Computable_function sameAs Função_computável.
- Computable_function sameAs m.049pw9.
- Computable_function sameAs Q1148456.
- Computable_function sameAs Q1148456.
- Computable_function wasDerivedFrom Computable_function?oldid=592010430.
- Computable_function isPrimaryTopicOf Computable_function.