# on termination

**Cagdas Ozgenc
**
co19@cornell.edu

*Thu, 15 May 2003 10:23:21 +0300*

>*
*>* 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.
*
It is not a power set. A language is a subset of the word monoid generated
by the alphabet by applying reccurent production of the alphabet (the star
operation).
>* > 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.
*
I always thought in a similar fashion. But literature insists that the
decidability is always measured with respect to a Turing Machine. Thus, I
was unable to communicate to many other people on the usenet.