# on termination

Eray Ozkural erayo@cs.bilkent.edu.tr
Thu, 15 May 2003 14:37:20 +0300

```On Thursday 15 May 2003 07:16, Andrew J Bromage wrote:
> G'day.
>
> On Wed, May 14, 2003 at 04:05:54PM +0300, Eray Ozkural wrote:
> > It seems to be
> > different: is there a language to denote any complete system?
>
> Of course there is.  A language is just a subset of the power set of
> some symbol alphabet.  So, for example, the set of all halting TMs
> (encoded appropriately) forms a language.
>

Well... A language L \subset of \Sigma^* as Cagdas said.

Anyway, by language I meant something else. Is "Formal System" better?

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

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

> > Is there a known proof that one needs at least a TM to recognize all
> > decidable languages?
[snip]
>
> If your class of automata is DFAs, for example, all languages are
> decidable, so you don't even need a TM for that.  If your class of