Word:

computability theory

(mathematics)computability theory - 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].
Browse
compulsivity
Compulsorily
Compulsory
compulsory process
Compunct
Compunction
Compunctionless
Compunctious
Compunctiously
Compunctive
Compurgation
Compurgator
Compurgatorial
CompuServe Corporation
CompuServe Information Service
Compusult Ltd.
-- computability theory --
Computable
Computation
Computation counting
computational
Computational Adequacy Theorem
computational complexity
computational geometry
computational learning
computational linguist
computational linguistics
computationally
Compute
COMpute ParallEL
compute server
computed axial tomography
computed tomography
Definitions Index: # A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

About this site and copyright information - Online Dictionary Home - Privacy Policy