on termination

[Eray Ozkural]

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