Árbol de computación

Un árbol de computación es una representación de los pasos de computación de una máquina de Turing no determinista sobre una entrada específica. ^{[ 1 ]} Un árbol de computación es un árbol con raíz formado por nodos y aristas. Cada nodo del árbol representa un único estado de computación, mientras que cada arista representa una transición al siguiente cálculo posible. El número de nodos del árbol es su tamaño y la longitud del camino desde la raíz hasta un nodo dado es la profundidad del nodo. La mayor profundidad de un nodo de salida es la profundidad del árbol. Las hojas del árbol se denominan nodos de salida.

En un árbol de computación para un problema de decisión , cada nodo de salida está etiquetado como Sí o No. Si un árbol, T, con un espacio de entrada X, si${\displaystyle x\in X}$y la ruta para x termina en el nodo etiquetado como yes, entonces la entrada x es aceptada. De lo contrario, es rechazada. ^{[ 2 ]}

La profundidad del árbol de computación para una entrada dada es el tiempo de computación para la máquina de Turing en esa entrada. ^{[ 1 ]}

Los árboles de computación también se han utilizado para estudiar la complejidad computacional de problemas en geometría computacional y cálculos de números reales . ^{[ 3 ] [ 4 ]}