on termination

[Eray Ozkural]

On Thursday 15 May 2003 15:49, Cagdas Ozgenc wrote:
> Completeness is not equal to deciding all recursive languages IMO. The
> bottom explanation of yours is not the same as the above question. Systems
> with sufficient power are incomplete. The system I am looking for doesn't
> have to decide its own termination, but its termination should be
> decideable by using an auxillary TM.
> Be careful with the jargon. Literature insists that "undecidable" is equal
> to "cannot be decided by a TM". Although an automaton may not decide its
> own halting , it may be decided by a TM, hence will be called decideable.
>

Decidable means that accept or reject states are guaranteed to halt. That is 
as you said the defining property of recursive sets. The complement of a 
recursive set is recursive....
I didn't say otherwise (that it should have to decide a "halting problem" for 
itself). Let's rephrase. If a language is recursively enumerable but not 
recursive it's not decidable. You would like to exclude all such languages 
from your automata and would like to recognize (accept or reject) all 
recursive languages. Right?

> The fact that there may be looping LBAs is irrelevant because we can
> discard those, since the halting is decidable(again note the terminology,
> can be decided by a TM) for LBA. Indeed the system has to be powerful than
> an LBA but we still should be able to write a TM that is capabale of
> discarding the ones that go into infinite loop. I don't know whether it is
> correct to say that it should be more powerful than a LBA, because it won't
> have the power to loop :).

You mean the following:
   I can write a programming language for CSL recognizers that can, at compile 
time, give an error message such as:
** Undecidable program!!! Check your logic!

Do you mean this? And how do you, for instance generalize this to polynomial 
bounded automata or higher orders?

Sincerely,

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C