on termination (little correction)
Andrew J Bromage
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.