On 16 Jun 2011, at 18:36, meekerdb wrote:

On 6/16/2011 7:38 AM, Bruno Marchal wrote:
Concerning the learning competence of a machine, I measure it by the classes of computable functions that the machine is able to identify from finite samples of input-outputs. This leads to the "computational learning theory" or "inductive inference" theory, which shows that the possible competences form a complex lattice with a lot of incomparable competences, and with a lot of necessarily non constructive gaps existing among them.

Do you have some reference where this is explained?

My favorite paper on this is:

CASE J. & SMITH C., 1983, Comparison of Identification Criteria for Machine Inductive
Inference. In Theoretical Computer Science 25,.pp 193-220.

But since, there has been a ton of papers published. Notably the COLT proceedings.

There is also the book:

OSHERSON D.N., STOB M.and WEINSTEIN S., 1986, Systems that Learn, MIT press. (New edition exists since)

It is a recursion theoretic based field. Of course it does not interest so much the engineers as most result are not constructive, indeed necessarily so.

A basic fundamental paper is:

GOLD, E. M., 1965, Limiting recursion, Journal of Symbolic Logic, 30, 1, pp. 27-48.

and

GOLD E.M., 1967, Language Identification in the Limit. Information & Control 10, pp.
447-474.

Another one is:

BLUM L. & BLUM M., 1975, Toward a Mathematical Theory of Inductive Inference.
Information and Control 28,.pp. 125-155.

There is a full chapter on this in "Conscience et mécanisme". You will find other references in the "bibilographie générale" pdf.
http://iridia.ulb.ac.be/~marchal/bxlthesis/consciencemecanisme.html

The gap G* minus G formalizes an easy set of inferable but non provable self-referential truth by inductive inference type of Löbian machines (the 'mystical machines').

Bruno



http://iridia.ulb.ac.be/~marchal/



--
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en.

Reply via email to