Recurrent neural networks of unspecified size Are there recurrent neural networks (RNNs) of variable size?
From what I've seen, RNNs are usually built using several nodes (or layers), in a manner similar to unrolled hidden Markov models (HMMs); however, one could construct a Markov model of unspecified size using a single truly recurrent node (or layer), which would have edges back into itself.
One benefit of using this truly recurrent formulation (rather than the unrolled formulation) is that it allows processing of data where the size is not known in advance. This could be used, for example, to feed forward until a node (or layer) variable takes on a certain state, allowing the recurrence to exit. The challenge of the recurrent formulation is that backpropagation may be more complex since we are essentially calculating derivatives within a chain.
Do these truly recurrent NNs exist? I imagine they would be nice for applications in NLP, even if training may be a bit of a pipe dream without resorting to numeric differentiation.

Yes, RNNs can work with arbitrary and variable sized inputs, and backpropagation can be done with these arbitrary and variable sized computation graphs.
You still have to "unroll" the graph (and have enough memory to do so) -- in some sense, there is no such thing as a "rolled graph", that's just a nice abstraction for humans to look at, but it's not a mathematical object that you can perform backprop on.
It's typically true that during training, you might want to compute the loss on a batch of inputs, and it's easier to parallelize this if all the inputs in your batch are of the same length, hence padding / trimming is common. During inference time (or if your batch size is 1), there's no need for this.
Another, more esoteric reason for preferring "fixed sized" RNNs is that historically, some neural network libraries (tensorflow) would first require the user to specify a fixed computation graph, then perform some clever allocation / assignment of graph nodes to compute device (cpu/gpu), and then you finally you could run the graph both forward and backward. Of course, this makes a dynamic computation pattern very annoying, because you have to destroy and reconstruct the graph constantly. Newer libraries (and newer versions of tensorflow), don't have this limitation anymore.
