From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.3 required=5.0 tests=BAYES_00,FREEMAIL_FROM,
	REPLYTO_WITHOUT_TO_CC autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,c42dbf68f5320193
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-05-08 10:20:13 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!bloom-beacon.mit.edu!nycmny1-snh1.gtei.net!cpk-news-hub1.bbnplanet.com!news.gtei.net!nntp.abs.net!news.voicenet.com!nntp.upenn.edu!msunews!not-for-mail
From: "Chad R. Meiners" <crmeiners@hotmail.com>
Newsgroups: comp.lang.ada
Subject: Re: Turing-undecidable languages (OT)
Date: Wed, 8 May 2002 13:16:22 -0400
Organization: Michigan State University
Message-ID: <abbmk8$1oo0$1@msunews.cl.msu.edu>
References: <ab93tl$2etb$1@msunews.cl.msu.edu>
 <7mWB8.6827$0z6.115522658@newssvr21.news.prodigy.com>
 <ab9fmh$2qh1$1@msunews.cl.msu.edu>
 <da2da981.0205080024.6576be16@posting.google.com>
Reply-To: "Chad R. Meiners" <crmeiners@hotmail.com>
NNTP-Posting-Host: arctic.cse.msu.edu
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2600.0000
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Xref: archiver1.google.com comp.lang.ada:23728
Date: 2002-05-08T13:16:22-04:00
List-Id: <comp.lang.ada>


"Danx" <chris.danx@ntlworld.com> wrote in message
news:da2da981.0205080024.6576be16@posting.google.com...
> "Chad R. Meiners" <crmeiners@hotmail.com> wrote in message
news:<ab9fmh$2qh1$1@msunews.cl.msu.edu>...
> Does that mean that if any problem cannot be expressed recursively,
> then no program can be coded to solve it?  In other words, any problem
> that can be solved without recursion, can also be expressed using
> recursion and any problem that cannot be solved by recursion cannot be
> solved by a computer?

Recursive refers to a set of languages. When we say x is recursive, we mean
x in is the set of recursive languages.  This is why I prefer the term
Turing-decidable.  As to the above question, we must be careful with phrases
"cannot be solved by recursion" because they are vague.  Context free
grammars are recursively defined yet they are less powerful then Turing
Machines, but I guess the best general answer is that Turing Machines can
simulate arbitrary recursion and nonrecursive algorithms can be thought as a
subset of recursive algorithms.  So given that explanation, you can solve X
with recursion if and only if you can solve X with a Turing Machine.