Can you make a different learner?

Question

My questions are:

[Solved by Dave] Given a learner N, can you design a learner M that behaves differently from N? No.

and

[Solved by Dave] Given a learner N, can you design a learner M that is more powerful than N? No.

and

[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.

and especially

[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.

Discussion

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.

Answer 1

Answer to questions 1 and 2: No. This is also the answer to 3 if $M$ is required to always halt (isn't this implied by the definition of a learner, or do you mean the program produced by $M$ must always halt?). Here's a proof for 1 (2 and 3 work pretty much the same way)

Suppose there's an algorithm $A$ which takes the description of a learner $N$ and outputs a learner $M$ which behaves differently. Let $N$ be a learner which runs $A$ on its own description, then runs the output $A(N) = M$ on the input text to produce a program that enumerates some set. By definition of $A$, $N$ and $M$ behave differently, but by construction they behave identically, contradicting the existence of $A$.

This same argument can be pretty easily modified to show that 2 is impossible. It can also be used to show that 3 is impossible if $M$ must always halt.

Not a real answer for question 4, but you might find this helpful: A prudent learner cannot converge on both every text for a finite set and on every text for the set of all natural numbers. Let $N$ be a learner that converges on every text for a finite set. Now, consider the following text for the set of all natural numbers. It contains all numbers in order, separated by differing numbers of 1s. After $i$, it contains enough 1s that $N$ will return a program which enumerates the set $1,\ldots,i$. $N$ will do this because it converges on every finite set. Because it will return a program enumerating a finite set after every prefix of this text, it does not converge on this text.

So if you let $M_1$ be the learner which converges on all finite sets and $M_2$ be the learner which converges on all texts for the set of all natural numbers, at least one of $M_1,M_2$ satisfies the criteria in question 4. You can extend this to a countably infinite set of learners in which at least all but one learner satisfies the criteria in question 4 by producing a machine $M_i$ for each natural number $i$ which converges on all finite sets which don't contain powers of the $i$th prime and also converges on the set of all powers of the $i$th prime. By similar logic as above, $N$ can't converge on all sets that any two of these converge on.

You can use this set of learners to find an $M$ satisfying 4 with arbitrarily high probability.

Answer 2

Here's an answer to your second question. Consider a learner $M$ which always produces a machine that enumerates every natural number. This converges on any text which contains every natural number. In the next paragraph, we will show that there is a one-to-one mapping from the set of all texts to the texts on which $M$ converges. Therefore, $M$ converges on as many texts as there are. It is more powerful than any text which converges on a set of smaller cardinality, and no learner can converge on more sets. So either $M$ is more powerful than $N$, or no learner is.

Let $T$ be a text. Consider the representation $T_b$ of $T$ in binary. We match this with a text $f(T)$ which we construct as follows. If bit $i$ of $T_b$ is equal to 0, then positions $2i-1$ and $2i$ of $f(T)$ are $2i-1$ and $2i$, in order. If bit $i$ is 0, then positions $2i-1$ and $2i$ of $f(T)$ are $2i$ and $2i-1$, reversing the order. For example, if $T_b$ begins $01100$, then $f(T)$ begins $1,2,4,3,6,5,7,8,9,10$.

If two texts $T,T'$ are such that $f(T) = f(T')$, then they have identical binary representations, so $T=T'$. Thus, this mapping is one-to-one, so the cardinality of the set of texts on which $M$ converges is the same as that of the set of all texts.