1
$\begingroup$

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.

Improve this question
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can you demonstrate a solution to the problem using an LBA? $\endgroup$ – Hal T Jun 19 '17 at 18:03
  • 1
    $\begingroup$ @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. $\endgroup$ – Raphael♦ Jun 19 '17 at 19:44
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Hal T Jun 19 '17 at 18:08
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Hal T Jun 19 '17 at 18:02
  • $\begingroup$ Actually, you're right, I'm wrong. David Richerby's answer shows the difference. $\endgroup$ – Hal T Jun 19 '17 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.