on termination

[Eray Ozkural]

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
> automata is TMs, not even a TM will help you.

This is not a proof I hope :P

Cheers,

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