While "RNNs are Turing-complete" is true in theory under certain assumptions, it is not true in practice. See slide 12 and on here (https://uclmr.github.io/nampi/2016/talk_slides/grefenstette-...) for some discussion.