A computation tree is a representation for the computation steps of a non-deterministic Turing machine on a specified input.[1] A computation tree is a rooted tree of nodes and edges. Each node in the tree represents a single computational state, while each edge represents a transition to the next possible computation. The number of nodes of the tree is the size of the tree and the length of the path from the root to a given node is the depth of the node. The largest depth of an output node is the depth of the tree. The leaves of the tree are called output nodes.
In a computation tree for a decision problem, each output node is labeled Yes or No. If a tree, T, with an input space X, if and the path for x ends in node labeled yes, then the input x is accepted. Else it is rejected.[2]
The depth of the computation tree for a given input is the computation time for the Turing machine on that input.[1]
Computation trees have also been used to study the computational complexity of problems in computational geometry and real number calculations.[3][4]
References
edit- ^ a b Griffor, E. R. (1999), Handbook of Computability Theory, Studies in Logic and the Foundations of Mathematics, vol. 140, Elsevier, p. 595, ISBN 9780080533049.
- ^ Moret, Bernard M. E. (1998), The Theory of Computation, Addison-Wesley, p. 338, ISBN 9780201258288.
- ^ Ben-Or, M. (1983), "Lower bounds for algebraic computation trees", Proc. 15th Annu. Symp. Theory of Computing, pp. 80–86, doi:10.1145/800061.808735.
- ^ Grigoriev, Dima; Vorobjov, Nicolai (1996), "Complexity lower bounds for computation trees with elementary transcendental function gates", Theor. Comput. Sci., 157 (2): 185–214, doi:10.1016/0304-3975(95)00159-X.