Un árbol de cálculo es una representación de los pasos de cálculo de una máquina de Turing no determinista en una entrada especificada. [1] Un árbol de cálculo es un árbol enraizado de nodos y aristas. Cada nodo del árbol representa un solo estado computacional, mientras que cada borde representa una transición al siguiente cálculo posible. El número de nodos del árbol es el tamaño del árbol 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 cálculo para un problema de decisión , cada nodo de salida se etiqueta Sí o No. Si un árbol, T, con un espacio de entrada X, siy la ruta para x termina en el nodo etiquetado sí, entonces se acepta la entrada x. De lo contrario, se rechaza. [2]
La profundidad del árbol de cálculo para una entrada determinada es el tiempo de cálculo de 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]
Referencias
- ^ a b Griffor, ER (1999), Manual de teoría de la computabilidad , Estudios de lógica y fundamentos de las matemáticas, 140 , Elsevier, p. 595, ISBN 9780080533049.
- ^ Moret, Bernard ME (1998), La teoría de la computación , Addison-Wesley, p. 338, ISBN 9780201258288.
- ^ Ben-Or, M. (1983), "Límites inferiores para árboles de cálculo algebraico", Proc. 15th Annu. Symp. Teoría de la Computación , págs. 80-86, doi : 10.1145 / 800061.808735.
- ^ Grigoriev, Dima; Vorobjov, Nicolai (1996), "Límites inferiores de complejidad para árboles de cálculo con puertas elementales de función trascendental", Theor. Computación. Sci. , 157 : 185–214, doi : 10.1016 / 0304-3975 (95) 00159-X.