on termination
Cagdas Ozgenc
co19@cornell.edu
Thu, 8 May 2003 09:05:25 +0300
This is a multi-part message in MIME format.
------=_NextPart_000_02D0_01C31540.F6B2A960
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
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
------=_NextPart_000_02D0_01C31540.F6B2A960
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 6.00.2800.1170" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>Greetings.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>This may be a little off topic, but I =
could not get=20
much response from comp.theory, so here it goes:</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Is it possible to have a programming =
language that=20
can be used to produce only the programs that terminate, but at the same =
time=20
decide all recursive languages? Or does such limitation automatically =
reduce the=20
class of languages that such a programming language decide to=20
primitive-recursive?</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Perhaps, I couldn't explain it very =
clearly. I=20
suppose another way of saying this is: Is there a strongly normalizing =
system=20
that can decide the class of recursive languages? Perhaps something less =
strong=20
than a Turing Machine, for example deciding all recursive languages but =
not=20
recognizing any recursively enumerable languages.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Thanks</FONT></DIV></BODY></HTML>
------=_NextPart_000_02D0_01C31540.F6B2A960--