on termination

[Cagdas Ozgenc]

> Let's see:
>   Is there a formal system to denote all complete systems and nothing
else?

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.

> Let's try it in automata jargon:
>
> We know that one needs a machine more powerful than an LBA to recognize
all
> recursive languages. However, even an LBA, by definition is a TM and it
can
> loop over two symbols forever. That is not all LBAs are guaranteed to
halt.
>
> Can there be an alternative machine formulation that only recognizes
recursive
> sets and nothing else?

You mean "decide" not "recognize", right?

> That is it should be stronger than an LBA, yet less
> powerful than a TM  because it excludes R.E - recursive. So, we are
looking
> for something that doesn't have a corresponding machine. It's possible
that
> it does not exist. But the proof could be interesting for us.

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