Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Can a method be written if the language is undecidable?

, ,
Problem Detail:

If a language is decidable, we can write a method that always halts and returns `true` for each string that is an element of the language and `false` otherwise.

If a language is undecidable, what does that mean? Does it mean:

a.) We cannot write a method; we cannot even conceive of a method.

b.) We can write a method that returns `true` for each string that is an element of the language; for strings that are not an element of the language, the method may return `false` or it may loop indefinitely.

c.) Other (what?)

###### Asked By : Roger Costello

(c) If a language is undecidable, we can write a method that returns `true` for some strings that are an element of the language and `false` for some strings that are not an element of the language. But such methods will always return an incorrect result or not terminate on at least some elements of in the language.

(b) describes a particular kind of undecidable languages: the languages that are semi-decidable. A semi-decidable language is one such that there is a way to enumerate all the elements of the language with a Turing machine (or other equivalent computation method). So the method can go on enumerating the language until it finds its argument; this method loops indefinitely if the argument isn't in the language.

An example of a semi-decidable language which isn't decidable is the set of provable statements in any reasonable foundation of mathematics. (Note that I wrote provable, not true. The opposite of a provable statement is a statement that admits no proof; this statement might not be false: there may be no way to prove its opposite either.) Given a potential proof, you can easily verify that it's correct, and thus provable statements can always be recognized as such. However, it can happen that neither the statement nor its negation is provable, in which case the search for a proof would loop forever.

An example of a language that isn't semi-decidable, and whose complement isn't semi-decidable either is the set of programs in a Turing-complete programming language that take an argument and return true for all arguments. This is the halting problem. For a language that isn't semi-decidable, (b) doesn't apply: it is impossible to write a function that returns `true` for all programs that terminate on all arguments and loops forever (or returns `false`) on all programs that loop on at least one input.