arvutatav

Arvutatav is an Estonian adjective describing something that can be calculated or determined by computation. In mathematics and computer science it is used for objects such as functions, values, or problems for which an algorithm can produce a result in finite time.

Etymology: the word is formed from the verb arvutada, “to calculate,” with the suffix -tav, meaning “able to be” or “capable of.”

Usage: In computability theory, a function is arvutatav (computable) if there exists an effective procedure, such as a Turing machine, that given any valid input produces the correct output after a finite number of steps. A language may be described as arvutatav or decidable if there is an algorithm that accepts all strings in the language and rejects all strings not in it. The term is also used more broadly in Estonian mathematical and computational literature to denote problems or values that can be determined algorithmically.

Common phrases include arvutatav väärtus (computable value) and arvutatav funktsioon (computable function). The opposite concept is uncomputable or non-computable, and in discussions of theory of computation the halting problem is a standard example of something that is not arvutatav.

See also: computability theory, decidability, computable functions, computational complexity, Estonian terminology for computer science.