Is the ability to do depth first search a proof of Turing Completeness? Can we write a non-TC automaton that does DFS?
Most functions you'll ever deal with in practice are primitive recursive, a model of computation that is properly less powerful than TMs.

More specifically, the problem from the question can be implemented on linear-bounded automata (LBA), a model of computation that is equivalent with context-sensitive grammars -- properly less powerful than TMs.