on termination

[Andrew J Bromage]

G'day.

On Thu, May 15, 2003 at 10:23:21AM +0300, Cagdas Ozgenc wrote:

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

You're right, sorry.

> I always thought in a similar fashion. But literature insists that the
> decidability is always measured with respect to a Turing Machine.

That's probably because of the Church-Turing thesis (i.e. computation
equals Turing Machine).  However, there are smaller and larger
definitions of "computation" than what can be accomplished on a TM.

Cheers,
Andrew Bromage