The opposite of computable, that is, a function which can not be calculated by a Turing machine (and so, according to the Church-Turing Thesis, by any mechanism).

The most famous example of a noncomputable function is the halting problem. Actually it turns out that there is a whole hierachy of different levels of diffucilty of noncomputable functions, in the sense that a function A is said to be more difficult than B if we would be able to compute B given a method of computing A but not vice versa. The halting problem belongs to the easiest impossible problems. One step up the ladder, we find for example the totality problem: does a given machine halt for all its imputs?

Apparently, Turing once wrote a paper about "Oracle Machines" - Turing Machines augmented with an "oracle box" which could answer noncomputable questions.

Often-used synonyms: incomputable, uncomputable

Log in or register to write something here or to contact authors.