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.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 10db24,77f71d0bde4c5bb4
X-Google-Attributes: gid10db24,public
X-Google-Thread: 103376,86fd56abf3579c34
X-Google-Attributes: gid103376,public
From: dewar@cs.nyu.edu (Robert Dewar)
Subject: Re: What good is halting prob?
Date: 1995/04/21
Message-ID: <dewar.798482893@gnat>#1/1
X-Deja-AN: 101370105
references: <3kaksj$iur@isnews.calpoly.edu> <cppD77Ex6.E77@netcom.com>
 	<3mve9b$gaj@news.cais.com> <cppD7880n.32B@netcom.com>
 	<3n285v$9vl@news.cais.com> <dewar.798271681@gnat>
 <EACHUS.95Apr21103559@spectre.mitre.org>
organization: Courant Institute of Mathematical Sciences
newsgroups: comp.lang.ada,comp.edu
Date: 1995-04-21T00:00:00+00:00
List-Id: <comp.lang.ada>

"   Of course, as Robert knows well, if the language is non-trivial,
such a compiler will be guarenteed to give an error message for some
correct programs."

Robert does not "know this well", Robert Eachus and I have argued over his
interpretation of Goedel's theorem in this context. I think his interpretation
is completely bogus, and that this does not apply.

Given a typical computer language, it is certainly possible to write a parser
that is 100.(infinite zeroes) correct in its ability to diagnose syntactically
correct programs.

Of course, given an arbitrary size input, your compiler may require
arbitrary amounts of memory. You may say "ah ha", there you go, a limitation,
because I know perfectly well you don't have arbtirary amounts of memory,
but by the same token, how can you present an arbitrary length program to
the compiler in the first place. This is unuseful angels-on-pins stuff.

I am not uncomfortable with this "consequence" of Goedel's theorem, because
I do not accept that it applies in this case.