La máquina de Turing, presentada por Alan Turing en 1936 en On computable numbers, with an application to the Entscheidungsproblems, es el modelo matemático de un dispositivo que se comporta como un autómata finito y que dispone de una cinta de longitud infinita en la que se pueden leer, escribir o borrar símbolos. Existen otras versiones con varias cintas, deterministas o no, etc., pero todas son equivalentes (respecto a los lenguajes que aceptan).
Backtracking (en español vuelta atrás) es una técnica para encontrar solución esos problemas que tienen que satisfacer ciertas restricciones. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense Derrick Henry Lehmer en la década de 1950.El backtracking gradualmente construye tareas básicas y las inspecciona para determinar si conducen a la solución del problema. Si una tarea no conduce a la solución, retrocede a la tarea original y se prueba otra cosa distinta. Es una prueba sistemática hasta llegar a la solución, o bien determinar que no hay solución por haberse agotado todas las opciones que probar (espacio de búsqueda).
Comentarios en artículos
No comments
Nobody has submitted a comment yet.