2011年
On the Amount of Nonconstructivity in Learning Recursive Functions
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011
- ,
- 巻
- 6648
- 号
- 開始ページ
- 332
- 終了ページ
- 343
- 記述言語
- 英語
- 掲載種別
- 研究論文(国際会議プロシーディングス)
- DOI
- 10.1007/978-3-642-20877-5_33
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
Nonconstructive proofs are a powerful mechanism in mathematics. Furthermore, nonconstructive computations by various types of machines and automata have been considered by e.g., Karp and Lipton [17] and Freivalds [11]. They allow to regard more complicated algorithms from the viewpoint of much more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem.
In the present paper, the amount of nonconstructivity in learning of recursive functions is studied. Different learning types are compared with respect to the amount of nonconstructivity needed to learn the whole class of general recursive functions. Upper and lower bounds for the amount of nonconstructivity needed are proved.
In the present paper, the amount of nonconstructivity in learning of recursive functions is studied. Different learning types are compared with respect to the amount of nonconstructivity needed to learn the whole class of general recursive functions. Upper and lower bounds for the amount of nonconstructivity needed are proved.
- リンク情報
-
- DOI
- https://doi.org/10.1007/978-3-642-20877-5_33
- DBLP
- https://dblp.uni-trier.de/rec/conf/tamc/FreivaldsZ11
- Web of Science
- https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000392154000033&DestApp=WOS_CPL
- URL
- http://dblp.uni-trier.de/db/conf/tamc/tamc2011.html#conf/tamc/FreivaldsZ11
- ID情報
-
- DOI : 10.1007/978-3-642-20877-5_33
- ISSN : 0302-9743
- DBLP ID : conf/tamc/FreivaldsZ11
- Web of Science ID : WOS:000392154000033