Hi there, I know this question is really stupid but I would really appreciate it if someone can help me out.
Q: When you are proving a language is decidable, what are you effectively doing?
Thank you
+2
A:
If you asking HOW is it done, I'm unsure, but I can check.
Basically, decidable is the language for which one can construct an algorithm (i.e. Turing machine) that will halt for ANY finite input (with accepting or rejecting the input). Undecidable is the language which is not decidable.
http://en.wikipedia.org/wiki/Recursive_language ... but more on the subject can easily be found. On this link there is only a quick mention of the term.
p.s. So, when constructing above mentioned algorithm, you are basically proving that language is decidable.
playcat
2010-10-24 15:05:30