The RNN construction of the paper is independent of training, because the weights are fixed and no learning occurs. The proof is based on how the encoding of the input output mechanism should be translated into an RNN so that it behaves the same as a Turing machine given the same input. They construct an RNN equivalent to a two-stack push-down automata, which can simulate any Turing machine. They also end up with a Turing complete universal processor net with 1058 units.
Training process is an approximation for a function, thus accuracy is always a parameter to decide on the computation time. Theoretically speaking, for a network with finite number of processors, and with weights and states represented with rational numbers (computable numbers), which is also a translation of a computable function (i.e. not a real random number generator for each sample), it should converge. Thus, the answer is yes.