# Is the ability to do depth first search a proof of Turing Completeness? Can we write a non-TC automaton that does DFS?

As the title states. Let's say we have a set of inputs that define a tree structure. Is it possible to construct an automaton that can perform depth-first search on this data that is not Turing-complete? If so, can we state that the ability to do DFS a sufficient proof of Turing-completeness?

For the purpose of the question, you can have some leeway about how the data is represented. As long as you can come up with a combination of a tree representation and an automaton that can DFS it that is less than Turing-complete, that's good enough. If it simplifies anything, you can make assumptions about the nature of the tree (e.g. binary or not), but a more generalizable answer would be preferred.

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.

• Can you demonstrate a solution to the problem using an LBA? – Hal T Jun 19 '17 at 18:03
• @HalT I guess I could, but I won't -- it's tedious work. A rough sketch would be to follow the usual implementation and note that we have a stack of at most linear height, plus some marking of visited notes -- all of this fits into linear additional memory. – Raphael Jun 19 '17 at 19:44

No, the ability to do DFS does not imply Turing-completeness.

Fix some encoding of trees as strings. Consider a Turing machine $M$ that has the following properties:

• if its input doesn't code the pair of a string $x$ and a tree $T$, $M$ rejects;
• on input $x,T$, $M$ performs DFS on $T$; it accepts if it finds $x$ in the tree and rejects, otherwise.

Now, consider the singleton set $\{M\}$. This is a model of computation (i.e., a set of objects and a description of what functions those objects compute) which can perform DFS but it can't do anything else, so it's not Turing-complete.

• You are correct. We can definitely contrive a machine that solves just this and not the Turing completeness requirements. It's not exactly the answer I wanted to hear, but that's on me for not asking the right question. – Hal T Jun 19 '17 at 18:08

You are asking two different questions:

1)Is the ability to do depth first search a proof of Turing Completeness?

2)Can we write a non-TC automaton that does DFS?

As for the first question, I don't think that ability to do DFS somehow relates to a power of computation. DFS is just an algorithm, while Turing machine is a model of computation. In other word algorithm is different concept from the model of computation. Algorithm is a set of instructions, while a computation model is a means to run/implement this algorithm on. For example, you can consider finite automata, or push down automata which are less powerful than Turing machines and so are not Turing-complete.

As for the second question. I am not sure but I think it is impossible to do DFS on a model which is not as powerful as Turing machines.

• For 1, the question is, using your terms, "Can we design a version of this algorithm that can be implemented by a machine that is less powerful than a Turing machine?", which makes it equivalent to the second question. – Hal T Jun 19 '17 at 18:02
• Actually, you're right, I'm wrong. David Richerby's answer shows the difference. – Hal T Jun 19 '17 at 18:05