Computation tree (original) (raw)

A computation tree is a representation for the computation steps of a non-deterministic Turing machine on a specified input. 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.