Annals of Pure and Applied Logic 139 (1):303-326 (2006)
AbstractThis paper investigates some delicate tradeoffs between the generality of an algorithmic learning device and the quality of the programs it learns successfully. There are results to the effect that, thanks to small increases in generality of a learning device, the computational complexity of some successfully learned programs is provably unalterably suboptimal. There are also results in which the complexity of successfully learned programs is asymptotically optimal and the learning device is general, but, still thanks to the generality, some of those optimal, learned programs are provably unalterably information deficient—in some cases, deficient as to safe, algorithmic extractability/provability of the fact that they are even approximately optimal. For these results, the safe, algorithmic methods of information extraction will be by proofs in arbitrary, true, computably axiomatizable extensions of Peano Arithmetic
Similar books and articles
Machine Learning of Higher-Order Programs.Ganesh Baliga, John Case, Sanjay Jain & Mandayam Suraj - 1994 - Journal of Symbolic Logic 59 (2):486-500.
Debilitated Shock Escape is Produced by Both Short- and Long-Duration Inescapable Shock: Learned Helplessness Vs. Learned Inactivity.Aidan Altenor, Joseph R. Volpicelli & Martin E. P. Seligman - 1979 - Bulletin of the Psychonomic Society 14 (5):337-339.
The Mind-Body Problem and the Intertwining [Spanish].James Mensch - 2011 - Eidos: Revista de Filosofía de la Universidad Del Norte 15:76-95.
Failure to Observe Learned Helplessness in Rats Exposed to Inescapable Footshock.William W. Beatty - 1979 - Bulletin of the Psychonomic Society 13 (4):272-273.
From Beast-Machine to Man-Machine. By Leonora Cohen Rosenfield. (New York: Oxford University Press. 1941. Pp. Xxviii + 353. Price $3.50.). [REVIEW]B. M. Laing - 1941 - Philosophy 16 (64):438-.
Interconsequence Generality of Learned Helplessness.Michael D. Mauk & Edward J. Pavur - 1979 - Bulletin of the Psychonomic Society 14 (6):421-423.
Spaces of Difference: The Contradictions of Alternative Educational Programs.Jennifer A. Vadeboncoeur - 2009 - Educational Studies: A Jrnl of the American Educ. Studies Assoc 45 (3):280-299.
Human and Machine Logic: A Rejoinder.John R. Lucas - 1968 - British Journal for the Philosophy of Science 19 (2):155-6.
Effects of Inescapable Shock in the Rat: Learned Helplessness or Response Competition.David R. Burdette, David S. Krantz & Abram Amsel - 1975 - Bulletin of the Psychonomic Society 6 (1):96-98.
The Effects of Inescapable Shock on the Retention of a Previously Learned Response in an Appetitive Situation with Delay of Reinforcement.Richard S. Calef, Michael C. Choban, Jim P. Shaver, Jack D. Dye & E. Scott Geller - 1986 - Bulletin of the Psychonomic Society 24 (3):213-216.
Is There a Well-Founded Solution to the Generality Problem?Jonathan D. Matheson - 2015 - Philosophical Studies 172 (2):459-468.
Added to PP
Historical graph of downloads
Citations of this work
No citations found.
References found in this work
Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1987 - MIT Press.
General Recursive Functions of Natural Numbers.S. C. Kleene - 1937 - Journal of Symbolic Logic 2 (1):38-38.
A Machine-Independent Theory of the Complexity of Recursive Functions.Manuel Blum - 1969 - Journal of Symbolic Logic 34 (4):657-658.
On the Computational Complexity of Algorithms.J. Hartmanis & R. E. Stearns - 1967 - Journal of Symbolic Logic 32 (1):120-121.