|From:||Jan Ziak <firstname.lastname@example.org>|
|Date:||Tue, 14 May 2019 08:52:41 -0700 (PDT)|
|Injection-Info:||gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="88388"; mail-complaints-to="email@example.com"|
|Posted-Date:||14 May 2019 13:00:17 EDT|
On Monday, May 13, 2019 at 9:31:05 PM UTC+2, Derek M. Jones wrote:
> > [...
> > 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
> 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.
My preference is to phrase it like this:
For any program P that is able to decide in finite time whether a subset S of
its Turing-complete inputs will halt it is possible to construct an input X
not in S which will cause P to either loop forever or return the result
"unable to decide whether X halts".
From practical viewpoint (which does not allow infinite runtimes), P must
always terminate in finite time and return one of these three results:
1: X halts
2: X loops forever
3: unable to decide whether X halts or loops forever
(3) can be further extended in precision by allowing conditional expressions
in the result, such as:
3.A: If <condition> then [X halts] else [X loops forever]
3.B: If <condition> then [X halts] else [unable to decide whether X halts or
Precision of (3) is maximized when <condition> has the form of a universal
expression which evaluates to true or false in finite time.
[This thread has gotten far afield from compilers. Please note followup-to. -John]
Return to the
Search the comp.compilers archives again.