I seem to recall that determining whether a language is Turing complete is an undecidable problem in general, but I was wondering what would work as a rule-of-thumb heuristic that strongly suggests it.
My first thought was that if you are able to output the primes without ever halting, that that would do the trick. My second thought was that that's probably overkill; something like the Fibonacci sequence would probably be enough.
I realize neither of those would be proof, inasmuch as you could write a program that prints out Fibonacci numbers and that's all it does, which clearly is not Turing complete itself. But in a reasonable context with a system you expect might be Turing complete, would either of those be strong indicators that it indeed is? If not, what would? And if so, are there even simpler heuristics that would be pretty reliable?