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

## Jan Ziak <0xe2.0x9a.0x9b@gmail.com>

Tue, 14 May 2019 08:52:41 -0700 (PDT)

*From comp.compilers*

| List of all articles for this month |

**From: ** | Jan Ziak <0xe2.0x9a.0x9b@gmail.com> |

**Newsgroups: ** | comp.compilers |

**Followup-To: ** | comp.theory |

**Date: ** | Tue, 14 May 2019 08:52:41 -0700 (PDT) |

**Organization: ** | Compilers Central |

**References: ** | 19-05-083 19-05-085 |

**Injection-Info: ** | gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="88388"; mail-complaints-to="abuse@iecc.com" |

**Keywords: ** | theory, comment |

**Posted-Date: ** | 14 May 2019 13:00:17 EDT |

**In-Reply-To: ** | 19-05-085 |

On Monday, May 13, 2019 at 9:31:05 PM UTC+2, Derek M. Jones wrote:

*> 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.*

Hello.

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

loops forever]

Precision of (3) is maximized when <condition> has the form of a universal

expression which evaluates to true or false in finite time.

Sincerely

Jan

[This thread has gotten far afield from compilers. Please note followup-to. -John]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.