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=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	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 01:24:17 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!postnews1.google.com!not-for-mail
From: chris.danx@ntlworld.com (Danx)
Newsgroups: comp.lang.ada
Subject: Re: Turing-undecidable languages (OT)
Date: 8 May 2002 01:24:17 -0700
Organization: http://groups.google.com/
Message-ID: <da2da981.0205080024.6576be16@posting.google.com>
References: <ab93tl$2etb$1@msunews.cl.msu.edu>
 <7mWB8.6827$0z6.115522658@newssvr21.news.prodigy.com>
 <ab9fmh$2qh1$1@msunews.cl.msu.edu>
NNTP-Posting-Host: 213.107.24.115
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1020846257 4968 127.0.0.1 (8 May 2002 08:24:17
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 8 May 2002 08:24:17 GMT
Xref: archiver1.google.com comp.lang.ada:23705
Date: 2002-05-08T08:24:17+00:00
List-Id: <comp.lang.ada>

"Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<ab9fmh$2qh1$1@msunews.cl.msu.edu>...

> This is an excellent question.  First, let's rephrase your question to:
> 
> If some says, "I'll am going to write a program Y that solves problem X",
> how should he act if told
> 
> a) X is not recursive.  (This is the same as Robert's recursively
> undecidable)
> b) Program Y may get stuck in an infinite loop.
> 
> In case a, Y cannot exist.

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?


Chris