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)