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