Methods, systems, and apparatus, including computer programs encoded on computer storage media, relating to multi-task recurrent neural networks. One of the methods includes maintaining data specifying, for a recurrent neural network, a separate internal state for each of a plurality of memory regions; receiving a current input; identifying a particular memory region of the memory access address defined by the current input; selecting, from the internal states specified in the maintained data, the internal state for the particular memory region; processing, in accordance with the selected internal state for the particular memory region, the current input in the sequence of inputs using the recurrent neural network to: generate an output, the output defining a probability distribution of a predicted memory access address, and update the selected internal state of the particular memory region; and associating the updated selected internal state with the particular memory region in the maintained data.