Path: csiph.com!xmission!news.snarked.org!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: "Derek M. Jones" Newsgroups: comp.compilers Subject: Re: At what point is a language so abstract that it simply cannot be compiled? Date: Mon, 13 May 2019 20:15:02 +0100 Organization: virginmedia.com Lines: 24 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <19-05-085@comp.compilers> References: <19-05-083@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="65409"; mail-complaints-to="abuse@iecc.com" Keywords: theory Posted-Date: 13 May 2019 15:31:03 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Content-Language: en-US Xref: csiph.com comp.compilers:2319 John, > [... > There are plenty of problems that are known to be undecidable. The > best known is the halting problem. You cannot write a program that > can inspect any arbitrary program and always tell you whether the > program it's inspecting will eventually halt or it will run forever. .... > -John] This wording of the halting problem tends to lead to all kinds of misunderstandings. I prefer to phrase it as: It has been provided that there exist programs for which it is not possible to deduce whether it will eventually halt or not. For many programs it is possible to deduce whether they will halt, or not. -- Derek M. Jones blog:shape-of-code.coding-guidelines.com