noncomputable

noncomputable
(Of a function) Incapable of being computed by any deterministic algorithm in any finite amount of time.

Wikipedia foundation.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… …   Wikipedia

  • Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown …   Wikipedia

  • Busy beaver — In computability theory, a busy beaver (from the colloquial expression for an industrious person) is a Turing machine that attains the maximum operational busyness (such as measured by the number of steps performed, or the number of nonblank… …   Wikipedia

  • Reverse mathematics — is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. The method can briefly be described as going backwards from the theorems to the axioms. This contrasts with the ordinary… …   Wikipedia

  • Reduction (recursion theory) — In computability theory, many reducibility relations (also called reductions, reducibilities, and notions of reducibility) are studied. They are motivated by the question: given sets A and B of natural numbers, is it possible to effectively… …   Wikipedia

  • Hypercomputation — refers to various hypothetical methods for the computation of non Turing computable functions (see also supertask). The term was first introduced in 1999 by Jack Copeland and Diane Proudfoot [Copeland and Proudfoot,… …   Wikipedia

  • Large numbers — This article is about large numbers in the sense of numbers that are significantly larger than those ordinarily used in everyday life, for instance in simple counting or in monetary transactions. The term typically refers to large positive… …   Wikipedia

  • Language identification in the limit — is a formal model for inductive inference. It was introduced by E. Mark Gold in his paper with the same title [http://www.isrl.uiuc.edu/ amag/langev/paper/gold67limit.html] . In this model, a learner is provided with presentation of some language …   Wikipedia

  • Computable number — In mathematics, particularly theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers or the computable reals, are the real numbers that can be computed to within any desired precision by a… …   Wikipedia

  • König's lemma — or König s infinity lemma is a theorem in graph theory due to Dénes Kőnig (1936). It gives a sufficient condition for an infinite graph to have an infinitely long path. The computability aspects of this theorem have been thoroughly investigated… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”