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-09 19:52:15 PST
Path: archiver1.google.com!postnews1.google.com!not-for-mail
From: dewar@gnat.com (Robert Dewar)
Newsgroups: comp.lang.ada
Subject: Re: Turing-undecidable languages (OT)
Date: 9 May 2002 19:52:14 -0700
Organization: http://groups.google.com/
Message-ID: <5ee5b646.0205091852.6935a25d@posting.google.com>
References: <ab93tl$2etb$1@msunews.cl.msu.edu>
 <ab9fmh$2qh1$1@msunews.cl.msu.edu>
 <ionhduku9trnt8pdm11ovutkp7g8jb0bjd@4ax.com>
 <abbmo6$1osf$1@msunews.cl.msu.edu> <abddca$h96t0$1@ID-77047.news.dfncis.de>
 <abe7ir$2ktu$1@msunews.cl.msu.edu>
NNTP-Posting-Host: 205.232.38.14
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1020999135 4869 127.0.0.1 (10 May 2002 02:52:15
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 10 May 2002 02:52:15 GMT
Xref: archiver1.google.com comp.lang.ada:23815
Date: 2002-05-10T02:52:15+00:00
List-Id: <comp.lang.ada>

"Chad R. Meiners" <crmeiners@hotmail.com> wrote in message news:<abe7ir$2ktu$1@msunews.cl.msu.edu>...
> I tried to clarify Robert's statement and answer some other questions as
> they poped up.  But as far as attacking Tom's idea of randoming generating
> sorting algoritms with predefined time and space bounds, I would do no such
> thing because placing bounds on algorithms is one way to change the halting
> problem to make it decidable.

True, but a problem that is theoretically recursively
undecidable over infinite inputs is typically practically
unsolvable if the only bound is available memory, available disk space
etc. So appealing to this is not particularly
interesting in practice. Yes, of course we know that from
a theoretical point of view, any bounding of a problem
changes things completely.

For example, there are many problems that are NP complete,
but as soon as you limit the size, they are theoretically
trivial. For example, consider the problem of coloring
an N node graph on a RAM machine with unit time access to
memory. If you limit N to googol**googol, then there is
a trivial algorithm that yields whether the graph can be
colored with M colors (again limit M), by simple table 
lookup in unit time. But that is not particularly interesting and in
practice, coloring is still hard :-)