on termination

[Andrew J Bromage]

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