Can a method be written if the language is undecidable?

Question

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?)

Answer 1

(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.

Answer 2

First of all, the word "conceive" is not clear. What's the different between writing and conceiving?

This question relates to the classes $RE$ and $coRE$. The class $RE$ is the set of languages that are recognizable by a TM. For such languages you can write a method that returns "true" on yes-instances, but might not halt on no-instances.

A language is in $coRE$ if its complement is in $RE$. Thus, for such languages you can write a method that returns "false" on no-instances, but may not halt on yes-instances.

There are languages that are not in $RE\cup coRE$ (e.g. $\{\langle M\rangle\}: L(M)=\Sigma^*$). For such languages there is no method that always halts on no- or on yes-instances.

For further reading, try the computability part in Sipser's book.

This also relates to the Arithmetical hierarchy, but I think it is a bit out of scope for this question.