matthew@cs.uq.oz.au (Matthew McDonald) (04/12/91)
I pretty sure the answer to this is no, but I'd be interested in knowing why exactly. If the answer is yes, even better. :-) I'll collect replies and summarize to the net if there's any interest. Sorry if the question is too stupid. In general, is there a recursively enumerable set of functions which are guaranteed to terminate for all input from a given domain, such that for *any* function f, terminating for at least some input from that same input domain, there is a member of the enumerated set whose input/output pairs are a superset of the set of input/output pairs of f (Where the set of i/o pairs for f includes only input for which f terminates.) I'd appreciate anything you got, thanks in anticipation, Matthew.
iam@Gang-of-Four.Stanford.EDU (Ian Mason) (04/13/91)
if by a recursively enumerable set of functions you mean a recursively enumerable set of indices of such fuctions, then the rice shapiro theorem gives a strong negative answer to you question. a reference to it is nigel cutland's computability. -iam-