The paper shows the equivalence for specific networks, it doesn't say every GNN (and as such transformers) are Dynamic Programmers. Also the models are explicitly trained on that task, in a regime quite different from ChatGPT.
What the paper shows and the possibility of LLMs being able to reason are pretty much completely independent from each other