Editing Algorithmic learning theory (section)

==Learning in the limit==

The concept was introduced in [[E. Mark Gold]]'s seminal paper "[[Language identification in the limit]]".<ref>{{cite journal |last1=Gold |first1=E Mark |title=Language identification in the limit |journal=Information and Control |date=May 1967 |volume=10 |issue=5 |pages=447–474 |doi=10.1016/S0019-9958(67)91165-5 }}</ref> The objective of [[language identification]] is for a machine running one program to be capable of developing another program by which any given sentence can be tested to determine whether it is "grammatical" or "ungrammatical". The language being learned need not be [[english language|English]] or any other [[natural language]] - in fact the definition of "grammatical" can be absolutely anything known to the tester.

In Gold's learning model, the tester gives the learner an example sentence at each step, and the learner responds with a [[hypothesis]], which is a suggested [[computer program|program]] to determine grammatical correctness. It is required of the tester that every possible sentence (grammatical or not) appears in the list eventually, but no particular order is required. It is required of the learner that at each step the hypothesis must be correct for all the sentences so far.{{citation needed|reason=In his paper 'Language Identification in the Limit', Gold did not require this, see the definition of 'Learnability' on p.449.|date=November 2013}}

A particular learner is said to be able to "learn a language in the limit" if there is a certain number of steps beyond which its hypothesis no longer changes.{{citation needed|reason=Gold additionally required the hypothesis to be correct, see previous 'citation needed' remark.|date=November 2013}} At this point it has indeed learned the language, because every possible sentence appears somewhere in the sequence of inputs (past or future), and the hypothesis is correct for all inputs (past or future), so the hypothesis is correct for every sentence. The learner is not required to be able to tell when it has reached a correct hypothesis, all that is required is that it be true.

Gold showed that any language which is defined by a [[Turing machine]] program can be learned in the limit by another [[Turing-complete]] machine using [[enumeration]].{{clarify|reason=Gold introduces a methode called 'identification by enumeration' (p.458), but he didn't claim that each language 'defined by a Turing machine program can be learned' by that method, or by any other. Such a result would contradict the unlearnability result stated in the next section of this article.|date=November 2013}} This is done by the learner testing all possible Turing machine programs in turn until one is found which is correct so far - this forms the hypothesis for the current step. Eventually, the correct program will be reached, after which the hypothesis will never change again (but note that the learner does not know that it won't need to change).

Gold also showed that if the learner is given only positive examples (that is, only grammatical sentences appear in the input, not ungrammatical sentences), then the language can only be guaranteed to be learned in the limit if there are only a [[finite set|finite]] number of possible sentences in the language (this is possible if, for example, sentences are known to be of limited length).{{clarify|reason=The problem Gold investigated is not about learning a language, but about learning a language class. For example, it is trivial to learn an infinite language L from a class consisting of L only.) Gold's result meant here is probably that of his Theorem I.8 (p.470). The paragraph should be repharsed accordingly.|date=November 2013}}

Language identification in the limit is a highly abstract model. It does not allow for limits of [[Run time (program lifecycle phase)|runtime]] or [[computer memory]] which can occur in practice, and the enumeration method may fail if there are errors in the input. However the framework is very powerful, because if these strict conditions are maintained, it allows the learning of any program known to be computable{{citation needed|date=January 2021}}. This is because a Turing machine program can be written to mimic any program in any conventional [[programming language]]. See [[Church-Turing thesis]].