computability theory

Computing Dictionary

computability theory definition

mathematics
The area of theoretical computer science concerning what problems can be solved by any computer.
A function is computable if an algorithm can be implemented which will give the correct output for any valid input.
Since computer programs are countable but real numbers are not, it follows that there must exist real numbers that cannot be calculated by any program. Unfortunately, by definition, there isn't an easy way of describing any of them!
In fact, there are many tasks (not just calculating real numbers) that computers cannot perform. The most well-known is the halting problem, the busy beaver problem is less famous but just as fascinating.
["Computability", N.J. Cutland. (A well written undergraduate-level introduction to the subject)].
["The Turing Omnibus", A.K. Dewdeney].
(1995-01-13)

The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: computability
Next Definition: computable
More from Thesaurus.com
Synonyms and Antonyms for computability theory
More from Reference.com
Search for articles containing computability theory
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature
FAVORITES
RECENT

;