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: 103376,39579ad87542da0e
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII-7-bit
X-Received: by 10.224.42.141 with SMTP id s13mr26366374qae.3.1368727802246;
        Thu, 16 May 2013 11:10:02 -0700 (PDT)
Path: 
 y6ni49949qax.0!nntp.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 16 May 2013 13:10:01 -0500
Newsgroups: comp.lang.ada
Date: Thu, 16 May 2013 14:09:59 -0400
From: "Peter C. Chapin" <PChapin@vtc.vsc.edu>
X-X-Sender: peter@whirlwind
Subject: Re: Seeking for papers about tagged types vs access to subprograms
In-Reply-To: <5195144f$0$6558$9b4e6d93@newsspool4.arcor-online.net>
Message-ID: <alpine.DEB.2.02.1305161404190.3294@whirlwind>
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>
User-Agent: Alpine 2.02 (DEB 1266 2009-07-14)
MIME-Version: 1.0
X-Usenet-Provider: http://www.giganews.com
X-Trace: 
 sv3-OIrHYYMTH93S1av+VZADrgkvtCW3WedRxXYfDzJGpoi+ekWApLSJZdi/nS1j3snnKoOFtpLjYAQFJ8K!RWUYuUdLrWOmCKVvEtN2vq+sHjHZGB6lQuBiLT1m/oq7vZikiqKzEIOHKGxPFgSI8wShOi8r0g==
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint
 properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3010
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
Date: 2013-05-16T14:09:59-04:00
List-Id: <comp.lang.ada>

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, 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).

Peter