Computable
Computability refers to the whether or not some problem can be solved by some system. Typically the term computable is in the context of Turing complete systems, like Turing machines. If a problem is computable then there exists a Turing machine which solves an equivalent definition of the problem. There are many computable problems, examples including various popular problems.
Uncomputable problems cannot be solved by a given system. In the typical context of Turing machines, uncomputable problems cannot be solved by Turing machines. An example of an uncomputable problem is the Turing machine halting problem.
The terms also apply to other models of computation, like finite state automata and push-down automata, but Turing machine computability is the most common use.
Formalism
Fix some wikipedia:partial combinatory algebra (PCA). An algorithm is realizable if it corresponds to a proof in the PCA. Construct the realizability topos over the PCA; this is not easy, but is always possible. Any arrow in the topos is computable by decomposition into its constituent realizers.
Given any realizability topos, a language L is an collection of sentences over some alphabet of symbols S in the topos. A computable language is an arrow S* → 2 in the topos; that is, it is a subset of the sentences over S for which every element of the set has a corresponding realizer witnessing its membership.
Generalizing this particular example, consider arbitrary objects L and arrows L → 2 which express their subobjects as computations. Such arrows are known as computable subsets of L, computable properties of L, or computable decision problems, and are contained in the complexity class R.
Examples of uncomputable languages
- Languages which can solve the Turing machine or greater halting problems are uncomputable, like Oracle and various other oracle machines
- Contradictory languages like ^
- Joke languages that have commands with unknowable effects on execution, like Ifthen and User talk:/w/wiki/index.php/Talk:index.php/Main page
Non-examples
- Ambiguous languages like Brain:D which have non-deterministic parsing phases are computable; the computation ranges over all possible parses.
- Similarly, non-deterministic languages can also be computable, since a computable universal search can be proceeded over all possibilities