Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
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

Answered By : Gilles

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14499

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback