If i want to implement a Deterministic Turing Machine from a Non-deterministic Turing machine is always suggested to use the Breadth-first algorithm ? If yes, why ?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ You're free to do whatever you want. $\endgroup$– Yuval FilmusCommented Feb 24, 2018 at 11:04
-
1$\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$– RaphaelCommented Feb 24, 2018 at 11:14
-
$\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$– RaphaelCommented Feb 24, 2018 at 11:14
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The reason for that is, if you use Depth-First Search (DFS), there exists the probability of the search going through a path that is infinite in length (loop) and you will never get an answer. If you use BFS it's more likely that you will find a path on to an accept state, if a path to one exists.
For example imagine that you have a tree with 100 children on left from the root and the right child of the root you only have 3. If you use DFS you will traverse the 100-deep left branch and later go right, and now instead having 100 branches just imagine you have infinite number of branches.
$\begingroup$
$\endgroup$
Think first that 'will my program halt?'. If you are sure that yes, your TM will definitely HALT then go for any searching algorithm, no problems at all. But, if are not sure about the HALTING issue, then? A TM is an idealized computer because the amounts of time and tape memory that it is allowed to use are unbounded. When it falls in ‘loops’ it may run for many years or even centuries after centuries although it will not produce any output. To avoid this looping problem we adapt BFS searching policy while developing a TM.
