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

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	Jan Ziak <0xe2.0x9a.0x9b@gmail.com>
Newsgroups	comp.compilers
Subject	Re: At what point is a language so abstract that it simply cannot be compiled?
Followup-To	comp.theory
Date	Tue, 14 May 2019 08:52:41 -0700 (PDT)
Organization	Compilers Central
Lines	51
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<19-05-089@comp.compilers> (permalink)
References	<19-05-083@comp.compilers> <19-05-085@comp.compilers>
Mime-Version	1.0
Content-Type	text/plain; charset="UTF-8"
Content-Transfer-Encoding	8bit
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
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
In-Reply-To	<19-05-085@comp.compilers>
Xref	csiph.com comp.compilers:2321

Followups directed to: comp.theory

Show key headers only | View raw

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]

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

At what point is a language so abstract that it simply cannot be compiled? "Costello, Roger L." <costello@mitre.org> - 2019-05-13 14:38 +0000
  Re: At what point is a language so abstract that it simply cannot be compiled? "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2019-05-13 20:15 +0100
    Re: At what point is a language so abstract that it simply cannot be compiled? Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2019-05-14 08:52 -0700
  Re: At what point is a language so abstract that it simply cannot be compiled? Martin Ward <martin@gkc.org.uk> - 2019-05-14 12:52 +0100
  Re: At what point is a language so abstract that it simply cannot be compiled? gah4@u.washington.edu - 2020-02-27 18:27 -0800

csiph-web