Un árbol de cálculo es una representación de los pasos de cálculo de una máquina de Turing no determinista sobre una entrada específica. [1] Un árbol de cálculo es un árbol con raíz de nodos y aristas. Cada nodo del árbol representa un único estado computacional, mientras que cada arista representa una transición al siguiente cálculo posible. La cantidad de nodos del árbol es el tamaño del árbol y la longitud del camino desde la raíz hasta un nodo determinado es la profundidad del nodo. La profundidad más grande de un nodo de salida es la profundidad del árbol. Las hojas del árbol se denominan nodos de salida.
En un árbol de cálculo para un problema de decisión , cada nodo de salida se etiqueta como Sí o No. Si se trata de un árbol, T, con un espacio de entrada X, si y el camino para x termina en un nodo etiquetado como Sí, entonces se acepta la entrada x. De lo contrario, se rechaza. [2]
La profundidad del árbol de cálculo para una entrada dada es el tiempo de cálculo de la máquina de Turing en esa entrada. [1]
Los árboles de cálculo también se han utilizado para estudiar la complejidad computacional de problemas en geometría computacional y cálculos con números reales . [3] [4]
