Re: At what point is a language so abstract that it simply cannot be compiled?

"Derek M. Jones" <derek@_NOSPAM_knosof.co.uk>
Mon, 13 May 2019 20:15:02 +0100

          From comp.compilers
Related articles
| List of all articles for this month |
From: "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk>
Newsgroups: comp.compilers
Date: Mon, 13 May 2019 20:15:02 +0100
Organization: virginmedia.com
References: 19-05-083
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
Content-Language: en-US

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

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.