Computable function: Difference between revisions

Revision as of 03:48, 17 July 2006

Revision as of 03:48, 17 July 2006

Line 60:

A key property of a formal language is the level of difficulty required to decide whether a given word is in the language. Some coding system must be developed to allow a computable function to take an arbitrary word in the language as input; this is usually considered routine. A language is called '''computable''' (synonyms: '''recursive''', '''decidable''') if there is a computable function <math>f</math> such that for each word ''w'' over the alphabet, <math>f(w) \downarrow = 1</math> if the word is in the language and <math>f(w)\downarrow = 0</math> if the word is not in the language. Thus a language is computable just in case there is a procedure that is able to correctly tell whether arbitrary words are in the language.

A language is '''computably enumerable''' (synonyms: '''recursivlyrecursively enumerable''', '''semidecidable''') if there is a computable function ''f'' such that <math>f(w)</math> is defined if and only if the word ''w'' is in the language. The term ''enumerable'' has the same etymology as in computably enumerable sets of natural numbers.

==Examples==