G'day. On Wed, May 14, 2003 at 04:05:54PM +0300, Eray Ozkural wrote:
It seems to be different: is there a language to denote any complete system?
Of course there is. A language is just a subset of the power set of some symbol alphabet. So, for example, the set of all halting TMs (encoded appropriately) forms a language.
Is there a known proof that one needs at least a TM to recognize all decidable languages?
Here's my working definition of "decidable language": A language L is decidable for some class of automata C if there is an automaton in C which recognises L and halts for all inputs. That is, my working definition of "decidable language" is dependent on the class of automata in which you're trying to implement decidability. If your class of automata is DFAs, for example, all languages are decidable, so you don't even need a TM for that. If your class of automata is TMs, not even a TM will help you. Cheers, Andrew Bromage