
8 May
2003
8 May
'03
2:05 a.m.
Greetings. This may be a little off topic, but I could not get much response from comp.theory, so here it goes: 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? Perhaps, I couldn't explain it very clearly. I suppose another way of saying this is: Is there a strongly normalizing system that can decide the class of recursive languages? Perhaps something less strong than a Turing Machine, for example deciding all recursive languages but not recognizing any recursively enumerable languages. Thanks