Unions of Identifiable Classes of Total Recursive Functions
作者： Kalvis Apsītis , Rūsinš Freivalds , Mārtinš Krikis , Raimonds Simanovskis , Juris Smotrovs
关键词: Property (philosophy) 、 Tuple 、 Identification (information) 、 Mathematics 、 Recursive functions 、 Combinatorics
摘要: J.Barzdin [Bar74] has proved that there are classes of total recursive functions which EX-identifiable but their union is not. We prove no 3 U1, U2, U3 such U1∪U2,U1∪U3 and U2∪U3 would be in EX U1∪U2∪U3∉ EX. For FIN-identification with the above-mentioned property 4 U3, U4 all unions triples these identifiable identification more than p minchanges a (2p+2−1)-tuple do exist (2p+2)-tuple properly.
springer.com
sci-hub.st 参考文章(7)
Rolf Wiehagen, Identification of formal languages mathematical foundations of computer science. pp. 571- 579 ,(1977) , 10.1007/3-540-08353-7_182
Rūsiņš Freivalds, Inductive Inference of Recursive Functions: Qualitative Theory Baltic Computer Science, Selected Papers. pp. 77- 110 ,(1991) , 10.1007/BFB0019357
E Mark Gold, Language identification in the limit Information & Computation. ,vol. 10, pp. 447- 474 ,(1967) , 10.1016/S0019-9958(67)91165-5
Carl H. Smith, The Power of Pluralism for Automatic Program Synthesis Journal of the ACM. ,vol. 29, pp. 1144- 1165 ,(1982) , 10.1145/322344.322356
John Case, Carl Smith, Comparison of identification criteria for machine inductive inference Theoretical Computer Science. ,vol. 25, pp. 193- 220 ,(1983) , 10.1016/0304-3975(83)90061-0
Dana Angluin, Carl H. Smith, Inductive Inference: Theory and Methods ACM Computing Surveys. ,vol. 15, pp. 237- 269 ,(1983) , 10.1145/356914.356918
Solomon Feferman, Hartley Rogers, Theory of Recursive Functions and Effective Computability. American Mathematical Monthly. ,vol. 76, pp. 715- ,(1969) , 10.2307/2316720