Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Computable_function> ?p ?o }
- 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, in the sense that a function is computable if there exists an algorithm that can do the job of the function, i.e. given an input of the function domain it can return the corresponding output. Computable functions 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 and vice versa. 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 wikiPageLength "20308".
- Computable_function wikiPageOutDegree "90".
- Computable_function wikiPageRevisionID "700939837".
- Computable_function wikiPageWikiLink Addition.
- Computable_function wikiPageWikiLink Alan_Turing.
- Computable_function wikiPageWikiLink Algorithm.
- Computable_function wikiPageWikiLink Arg_max.
- Computable_function wikiPageWikiLink Arithmetical_hierarchy.
- Computable_function wikiPageWikiLink Blum_axioms.
- Computable_function wikiPageWikiLink Busy_beaver.
- Computable_function wikiPageWikiLink Bxc3xa9zouts_identity.
- Computable_function wikiPageWikiLink Category:Computability_theory.
- Computable_function wikiPageWikiLink Category:Theory_of_computation.
- Computable_function wikiPageWikiLink Chaitins_constant.
- Computable_function wikiPageWikiLink Church–Turing_thesis.
- Computable_function wikiPageWikiLink Closure_(mathematics).
- Computable_function wikiPageWikiLink Compiler.
- Computable_function wikiPageWikiLink Computability_theory.
- Computable_function wikiPageWikiLink Computable_number.
- Computable_function wikiPageWikiLink Computational_complexity_theory.
- Computable_function wikiPageWikiLink Constant_function.
- Computable_function wikiPageWikiLink Countable_set.
- Computable_function wikiPageWikiLink David_Hilbert.
- Computable_function wikiPageWikiLink Diophantine_equation.
- Computable_function wikiPageWikiLink Domain_of_a_function.
- Computable_function wikiPageWikiLink Effective_method.
- Computable_function wikiPageWikiLink Entscheidungsproblem.
- Computable_function wikiPageWikiLink Exponential_growth.
- Computable_function wikiPageWikiLink Finitary.
- Computable_function wikiPageWikiLink Finitary_relation.
- Computable_function wikiPageWikiLink Formal_language.
- Computable_function wikiPageWikiLink Function_composition.
- Computable_function wikiPageWikiLink Function_problem.
- Computable_function wikiPageWikiLink Greatest_common_divisor.
- Computable_function wikiPageWikiLink Halting_problem.
- Computable_function wikiPageWikiLink Herbert_Enderton.
- Computable_function wikiPageWikiLink Hyperarithmetical_theory.
- Computable_function wikiPageWikiLink Hypercomputation.
- Computable_function wikiPageWikiLink If_and_only_if.
- Computable_function wikiPageWikiLink Injective_function.
- Computable_function wikiPageWikiLink Kolmogorov_complexity.
- Computable_function wikiPageWikiLink Lambda_calculus.
- Computable_function wikiPageWikiLink Mathematician.
- Computable_function wikiPageWikiLink Model_of_computation.
- Computable_function wikiPageWikiLink Multiplication.
- Computable_function wikiPageWikiLink Natural_number.
- Computable_function wikiPageWikiLink Oracle_machine.
- Computable_function wikiPageWikiLink Partial_function.
- Computable_function wikiPageWikiLink Pi.
- Computable_function wikiPageWikiLink Post–Turing_machine.
- Computable_function wikiPageWikiLink Primitive_recursive_function.
- Computable_function wikiPageWikiLink Recursive_ordinal.
- Computable_function wikiPageWikiLink Register_machine.
- Computable_function wikiPageWikiLink Semicomputable_function.
- Computable_function wikiPageWikiLink Set_(mathematics).
- Computable_function wikiPageWikiLink Super-recursive_algorithm.
- Computable_function wikiPageWikiLink Tag_system.
- Computable_function wikiPageWikiLink Tetration.
- Computable_function wikiPageWikiLink Theory_of_computation.
- Computable_function wikiPageWikiLink Tuple.
- Computable_function wikiPageWikiLink Turing_degree.
- Computable_function wikiPageWikiLink Turing_jump.
- Computable_function wikiPageWikiLink Turing_machine.
- Computable_function wikiPageWikiLink Turing_reduction.
- Computable_function wikiPageWikiLink Unary_operation.
- Computable_function wikiPageWikiLink Μ-recursive_function.
- Computable_function wikiPageWikiLink Μ_operator.
- Computable_function wikiPageWikiLinkText "Computable function".
- Computable_function wikiPageWikiLinkText "Computable function#Uncomputable functions and unsolvable problems".
- Computable_function wikiPageWikiLinkText "Turing computability".
- Computable_function wikiPageWikiLinkText "Turing computable".
- Computable_function wikiPageWikiLinkText "algorithmically computable".
- Computable_function wikiPageWikiLinkText "computable function".
- Computable_function wikiPageWikiLinkText "computable function#Incomputable functions and unsolvable problems".
- Computable_function wikiPageWikiLinkText "computable function#Uncomputable functions and unsolvable problems".
- Computable_function wikiPageWikiLinkText "computable".
- Computable_function wikiPageWikiLinkText "effective".
- Computable_function wikiPageWikiLinkText "non-computable algorithm".
- Computable_function wikiPageWikiLinkText "non-computable".
- Computable_function wikiPageWikiLinkText "noncomputable function".
- Computable_function wikiPageWikiLinkText "partial computable functions".
- Computable_function wikiPageWikiLinkText "partial recursive".
- Computable_function wikiPageWikiLinkText "predictable functions".
- Computable_function wikiPageWikiLinkText "recursive function".
- Computable_function wikiPageWikiLinkText "recursive functions".
- Computable_function wikiPageWikiLinkText "recursive or effective computability".
- Computable_function wikiPageWikiLinkText "recursive relation".
- Computable_function wikiPageWikiLinkText "recursive".
- Computable_function wikiPageWikiLinkText "recursively computable".
- Computable_function wikiPageWikiLinkText "total computable function".
- Computable_function wikiPageWikiLinkText "total recursive function".
- Computable_function wikiPageWikiLinkText "total recursive".
- Computable_function wikiPageUsesTemplate Template:=.
- Computable_function wikiPageUsesTemplate Template:ComplexityClasses.
- Computable_function wikiPageUsesTemplate Template:Main.
- Computable_function wikiPageUsesTemplate Template:Math.
- Computable_function wikiPageUsesTemplate Template:Mathematical_logic.
- Computable_function wikiPageUsesTemplate Template:Mvar.