From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Thread: a07f3367d7,39579ad87542da0e
X-Google-Attributes: gida07f3367d7,public,usenet
X-Google-NewGroupId: yes
X-Google-Language: ENGLISH,ASCII-7-bit
X-Received: by 10.66.122.39 with SMTP id lp7mr7220068pab.44.1368739261535;
        Thu, 16 May 2013 14:21:01 -0700 (PDT)
Path: 
 bp1ni2642pbd.1!nntp.google.com!news.glorb.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups: comp.lang.ada
Subject: Re: Seeking for papers about tagged types vs access to subprograms
Date: Fri, 17 May 2013 00:20:59 +0300
Organization: Tidorum Ltd
Message-ID: <avl0tsF6g4nU1@mid.individual.net>
References: <op.wv8jh1c1ule2fv@cardamome> <kmecg6$et4$1@loke.gir.dk>
 <12gn9wvv1gwfk.10ikfju4rzmnj.dlg@40tude.net> <kmh7d4$up3$1@loke.gir.dk>
 <1oy5rmprgawqs.1jz36okze0xju$.dlg@40tude.net> <kmk45u$v45$1@loke.gir.dk>
 <1q2ql1e4rcgko.diszzq1mhaq8$.dlg@40tude.net>
 <518dedd4$0$6581$9b4e6d93@newsspool3.arcor-online.net>
 <hxkln519n179.1kt13z7phxg2f.dlg@40tude.net> <kms7hs$8ur$1@loke.gir.dk>
 <1um7tijeo609b$.1gtdijp0acfmn$.dlg@40tude.net> <op.ww2nq7t6ule2fv@cardamome>
 <mk9m6fxa1jbr$.mm0kw7g3igma$.dlg@40tude.net>
 <alpine.DEB.2.02.1305150714300.2254@whirlwind>
 <1nkyb845dehcu.1sd90udwsrpdu.dlg@40tude.net>
 <alpine.DEB.2.02.1305151601340.7888@whirlwind>
 <1mg9eepp12ood$.14lj7s8a7eygd$.dlg@40tude.net>
 <alpine.DEB.2.02.1305160641330.2594@whirlwind>
 <1cj8b5amtua30.1foe0rdpldt2.dlg@40tude.net>
 <alpine.DEB.2.02.1305160829510.2501@whirlwind>
 <lnx0yaymncw7$.pqorucpcq8r3$.dlg@40tude.net>
 <5195144f$0$6558$9b4e6d93@newsspool4.arcor-online.net>
 <alpine.DEB.2.02.1305161404190.3294@whirlwind>
Mime-Version: 1.0
X-Trace: individual.net RrgaWnp4DmjVwuCF+vkEsgOtIY0DUXNBsjsjZZDifASDPv3c3p
Cancel-Lock: sha1:MDtwDvSzLAN0ZoPTe/hJL/nCYT8=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.6;
 rv:17.0) Gecko/20130328 Thunderbird/17.0.5
In-Reply-To: <alpine.DEB.2.02.1305161404190.3294@whirlwind>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Date: 2013-05-17T00:20:59+03:00
List-Id: <comp.lang.ada>

On 13-05-16 21:09 , Peter C. Chapin wrote:
> On Thu, 16 May 2013, G.B. wrote:
> 
>> On 16.05.13 15:54, Dmitry A. Kazakov wrote:
> 
>>>> I realize that equivalence of functions is a difficult concept in
>>>> general
>>> There is nothing difficult in that. A function is a set of pairs. Two
>>> sets
>>> are equal when contain same elements.
>>
>> I think the difficulty is that eq is not computable. For example,
>> if f1 and f2 are any Ada compilers, produce an algorithm that computes
>>
>>  eq(f1, f2)
>>
>> Then, proceed to finding eq of procedures computing eq.
> 
> The other problem with Dmitry's earlier suggestion is that the sets he's
> talking about could be infinite in size (at least in principle).
> Comparing infinite sets can't be done in finite time, of course,

But comparing finite descriptions (generator programs) of the sets could
perhaps be done in finite time.

> so it
> doesn't really solve the problem in the general case. This is part of
> being not computable. I believe computing the equivalence of functions
> is undecidable, but I don't have a proof off hand (maybe one could be
> looked up).

A proof seems simple enough, assuming that the set of inputs is infinite
and enumerable: if you want to decide whether f1 and f2 are equivalent,
make a program P that iteratively generates (enumerates) all possible
inputs x; computes f1(x) and f2(x); and stops if f1(x) /= f2(x). This
program P halts if and only if f1 /= f2. Since halting is undecidable,
so therefore is function equality.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
      .      @       .