  A major target of linguistics and cognitive science has been to understand
what class of learning systems can acquire the key structures of natural
language. Until recently, the computational requirements of language have been
used to argue that learning is impossible without a highly constrained
hypothesis space. Here, we describe a learning system that is maximally
unconstrained, operating over the space of all computations, and is able to
acquire several of the key structures present natural language from positive
evidence alone. The model successfully acquires regular (e.g. $(ab)^n$),
context-free (e.g. $a^n b^n$, $x x^R$), and context-sensitive (e.g.
$a^nb^nc^n$, $a^nb^mc^nd^m$, $xx$) formal languages. Our approach develops the
concept of factorized programs in Bayesian program induction in order to help
manage the complexity of representation. We show in learning, the model
predicts several phenomena empirically observed in human grammar acquisition
experiments.
