4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Doesn't Rice's theorem preclude that you can construct a learner M with behavior strictly different from learner N? $\endgroup$ – Antonio Valerio Miceli-Barone Jun 30 '11 at 13:31
  • $\begingroup$ @Antonio Valerio Miceli-Barone: Can you give more details of your argument? $\endgroup$ – Zirui Wang Jun 30 '11 at 15:43
  • $\begingroup$ @Zirui Wang: When you say a program enumerates a subset of natural numbers, is the enumeration in order? Also, when you say that a learner converges on a text if it outputs the same enumeration procedure, does this mean that it outputs identical code, or just a series of programs that produce identical enumerations? $\endgroup$ – Dave Jul 4 '11 at 8:44
  • $\begingroup$ @Dave: Not necessarily in order. Identical code. This is what's called explanatory learning. The other alternative is called behaviorally correct learning, which is not mentioned in this question. $\endgroup$ – Zirui Wang Jul 4 '11 at 12:12
  • $\begingroup$ I want to add that if you use the behaviorally correct definition of convergence then the answer is no. Refer to Sanjay Jain, Frank Stephan and Nan Ye's paper, Prescribed learning of r.e. classes. There they show that the open problem is positive in the behaviorally correct case. (But the explanatory case is still open.) $\endgroup$ – Zirui Wang Jul 14 '11 at 23:10
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot and I think you are right on questions 1, 2, 3. Unfortunately, I found I wanted to ask the fourth question. Should I award a tick to Dave? I fear that people would think that the question is closed. $\endgroup$ – Zirui Wang Jul 5 '11 at 3:07
  • $\begingroup$ Even though the learner N from Dave's construction doesn't always halt, we can make a new learner N' from N such that (a) N' converges on exactly the same texts as N and (b) N' always halts. $\endgroup$ – Zirui Wang Jul 5 '11 at 3:23
  • $\begingroup$ Feel free to withhold the tick if you want more people to try to answer question 4. $\endgroup$ – Dave Jul 5 '11 at 4:39
  • $\begingroup$ Thanks for your generosity. I guess it will take a while for an answer to question 4 to appear, because it's too similar to the open problem. $\endgroup$ – Zirui Wang Jul 5 '11 at 4:52
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Note that the above only works if the numbers in a text are in sorted order. If texts aren't in sorted order, the learner $M$ which always outputs a program that outputs every natural number converges on the uncountably infinitely many orderings of the set of all natural numbers. As there are uncountably infinitely many texts, no learner is more powerful than $M$. $\endgroup$ – Dave Jul 1 '11 at 2:51
  • $\begingroup$ I can design a learner that converges on (a) all texts that contain n, n + 1, ... for some n and (b) all texts for the set of even numbers. So even though the number of texts in (a) is maximal, this learner is more powerful than a learner that converges on only (a). $\endgroup$ – Zirui Wang Jul 1 '11 at 10:23
  • $\begingroup$ I believe my comment addresses what you just said. If you take the learner that outputs a machine which enumerates all natural numbers, the set of texts it accepts has the same cardinality as the rational numbers. So does the set of all texts. So this learner is more powerful than any learner $N$ that converges on a set with smaller cardinality, and there is no more powerful learner for any $N$ that converges on a set with equal cardinality. $\endgroup$ – Dave Jul 2 '11 at 1:08
  • $\begingroup$ I updated my answer to better explain this comment. $\endgroup$ – Dave Jul 2 '11 at 2:24
  • $\begingroup$ I think this becomes a distinction based on what Zirui means by '(strictly) more texts' (1). If you interpret that based only on cardinality, then Dave's argument works, but cardinality is pretty coarse grained. You can also interpret (1) as strict superset, and then it seems that Zirui's comment breaks Dave's answer. But maybe I am not quiet understanding the question/answer. $\endgroup$ – Artem Kaznatcheev Jul 3 '11 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.