My questions are:
[Solved by Dave] Given a learner N, can you design a learner M that behaves differently from N? No.
[Solved by Dave] Given a learner N, can you design a learner M that is more powerful than N? No.
[Solved by Dave] Given a learner N that always halts, can you design a learner M and a set of natural numbers L, such that (a) for every text T that contains exactly L, M converges on T and (b) there exists a text T' that contains exactly L, such that N diverges on T'? No.
[Open] Given a learner N that is prudent and always halts, can you effectively design a learner M such that there exists a set of natural numbers L such that
- for every text T that contains exactly L, M converges on T and
- there exists a text S that contains exactly L, such that N diverges on S?
Note that the difference between the fourth and the third questions is that N is required to be prudent. But M is not required. So N can't simulate M and follow exactly what M does -- M may conjecture a set it does not always converge on.
Also note that a yes answer to the open problem (discussed below) will imply a no answer to the fourth question. I'm saying this because, if you follow Dave's line of thought, you are solving the open problem, which is a stronger statement than (a negative answer to) my question.
And a yes answer to the fourth problem implies a no answer to the open question.
Now come the definitions.
A learner is a Turing machine that, when the input is a (finite) sequence of natural numbers, outputs a program that enumerates a subset of natural numbers.
A text is an infinite sequence of natural numbers.
A learner is said to converge on a text if, when feeding successively longer initial segments of the text, there exists a point after which the learner outputs the same enumeration procedure that enumerates exactly the elements in the text.
A learner diverges on a text if it does not converge on it.
Learner A is said to behave differently from learner B if there exists a text on which A converges but B diverges or A diverges but B converges.
Learner A is said to be more powerful than learner B if A converges on (strictly) more texts than B.
A learner M is prudent iff, if on some initial segment of some text it conjectures a set S, it converges on all texts for S.
The background of these problems is the open question whether there exists a program that when given a learner outputs a prudent learner that converges on a superset of texts. Mark Fulk proved that the prudent learner exists (in Theorem 15 of the article "Prudence and other conditions on formal language learning"), but his proof is non-constructive because it has a seemingly undecidable case distinction. The open problem is to give a constructive proof of this theorem.