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-09 09:20:11 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!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: Thu, 9 May 2002 12:18:02 -0400
Organization: Michigan State University
Message-ID: <abe7ir$2ktu$1@msunews.cl.msu.edu>
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>
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:23776
Date: 2002-05-09T12:18:02-04:00
List-Id: <comp.lang.ada>


"Dmitry A.Kazakov" <mailbox@dmitry-kazakov.de> wrote in message
news:abddca$h96t0$1@ID-77047.news.dfncis.de...
> If I
> correctly understood it, Tom considers a problem regading programs of
fixed
> size, while opponents attack him with the results valid for infinite
cases.

Where do you see people attacking Tom in this discusion of TMs?  This whole
discusion started when Tom replied to Robert with the following statement:

>   So the set of instructions emitted by Gnat when it compiles bubble sort
> code may or may not constitute a general sorting algorithm, and whether
> it does or not is undecidable?  I learn something new every day.

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.