on termination

[Cagdas Ozgenc]

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