On Thursday 08 May 2003 09:05, Cagdas Ozgenc wrote:
Is it possible to have a programming language that can be used to produce only the programs that terminate, but at the same time decide all recursive languages? Or does such limitation automatically reduce the class of languages that such a programming language decide to primitive-recursive?
I'm not sure if that's theoretically possible. A recursive language requires
more than an LBA for recognition. But then the new edition of Cindrella book
says when you use a polynomial-bounded TM it's not guaranteed to halt. I
pondered the same question last year but when I couldn't find an answer
easily I gave up :)
Is your intention to design such a programming language or to make a
mindblowing proof?
Maybe it's better to start with subsets of recursive languages. DL people are
dealing with decidable subsets of FOL, that might be interesting. Ouch, the
thought of all recursive sets gave me a headache (^_-)
Cheers,
--
Eray Ozkural (exa)