PEREIRA@SRI-AI.ARPA (03/26/84)
"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