Computation tree

Definition

A computation tree is a representation for the computation steps of a Turing Machine. A computation tree is an acyclic graph of nodes and edges. Each node in the tree represents a single computation, while the edge represents the 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 output nodes of the tree are called leaves.

In a computation tree each output node is labeled Yes or No. If a tree, T, with a intput space X, if $xX$ and the path for x ends in node labeled yes, then the input x is accepted. Else it is rejected.