Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!floyd!vax135!cornell!uw-beaver!tektronix!hplabs!sri-unix!PEREIRA@SRI-AI.ARPA
From: PEREIRA@SRI-AI.ARPA
Newsgroups: net.ai
Subject: Identifying programs
Message-ID: <210@sri-arpa.UUCP>
Date: Mon, 26-Mar-84 02:50:08 EST
Article-I.D.: sri-arpa.210
Posted: Mon Mar 26 02:50:08 1984
Date-Received: Sun, 25-Mar-84 19:19:27 EST
Lines: 12

"Algorithmic Program Debugging" by Ehud Shapiro, MIT Press includes
substantial discussion of the question of identifying programs
from I/O pairs. Of course in general the identification is not
exact. Concepts of asymptotic identification ("identification in
the limit") are used instead. A lot of this work has been
developed to try to pin down the concept of "learnable language".
There are a number of recent papers on this question by Scott
Weinstein (University of Pennsylvania) and others, in the journal
Information and Control. If anyone is interested, I'll dig out
the references.

-- Fernando Pereira