on termination (little correction)

Andrew J Bromage ajb@spamcop.net
Thu, 15 May 2003 14:22:53 +1000


On Wed, May 14, 2003 at 02:59:50PM +0300, Cagdas Ozgenc wrote:

> Perhaps that's a little misleading, but I don't know how to phrase it
> properly. Basically what is the largest class of languages that a
> terminating system can decide?

Assuming for the moment that your "terminating system" is a TM...

I believe that if you were to produce such a class of languages, I can
produce another recursively enumerable language not in your class by
some kind of diagonalisation procedure.  I can then create a
terminating recogniser which accepts your class, plus the new language
as a special case.

Andrew Bromage