Fix an alphabet A. A language L (i.e. a set of words composed of letters of A) is called recursive if there exists a Turing machine which accepts that language. That is, there exists some Turing machine M such that when M is run on a word w, M(w) terminates and produces the output 1 if w is in L, and M(w) terminates and produces the output if w is not in L.

Most variations on this definition also produce the same end-result. This is the essence of the Church-Turing thesis. However, the requirement that M always terminate (i.e. that the function it computes not be partial) may not be dropped so easily.

We may similarly define a function f taking words over A and returning words over A as computable if f is the function computed by some Turing machine M which terminates for each input.

It is not computable whether a Turing machine calculates a computable function.

Com*put"a*ble (?), a. [L. computabilis.]

Capable of being computed, numbered, or reckoned.

Not easily computable by arithmetic. Sir M. Hale.

<-- computable number. -->

 

© Webster 1913.

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