Maquinas De Turing Y Su Implicancia En Problemas Np

Maquinas de Turing y su implicancia en problemas NP
Autor Rodrigo Cárdenas Plaza Universidad Tecnológica Metropolitana rodrigo.cardenasplaza@mail.com

RESUMEN
Investigación basada en la trascendencia de las maquinas de Turing en la resolución de problemas intratables y determinación de tipo “np” en el mundo de la informática, abordando el arte de la implicancia que han tenido en la materia.INTRODUCCIÓN

En lo que respecta con la teoría de la complejidad, se dice que la clase de complejidad de los problemas de decisión que pueden ser resueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing determinista es llamada P. Cuando se trata de una máquina de Turing nodeterminista, la clase es llamada NP. Una interrogante abierta más importantes en laactualidad es descubrir si estas clases son diferentes o no. Es en este aspecto que el trasfondo de esta investigación comprende principal énfasis al aporte que se hizo en la determinación de problemas complejos del ámbito de las ciencias de las computación, los que han sido definidos como “np”, que relacionan su complejidad con el tiempo de ejecución de un algoritmo (en este caso tiempo polinómico) enque pueden ser ejecutados, así como los desafíos inconclusos e interrogantes que en esta área de investigación aun siguen existiendo. Primordial es entender el objetivo y preponderancia que esta investigación tiene a futuro, tanto en el desarrollo de algoritmo determinísticos, dado que siempre existirán problemas que contengan mayor grado de complejidad; como también es importante conocer elcontexto en que se ha desarrollado uno de los pilares en la evolución que ha tenido la computación desde la época de Turing. Producto de lo anterior es que a continuación se expondrá una serie de etapas, como contexto histórico, procesos, algoritmos, entre otros; que demuestran y exponen lo relevante de este tema. Finalizando con una conclusión que resume y dicta lo que en este “paper” se estudió yconcluyó.

INVESTIGACIÓN
Para contextualizar el trabajo de Turing, relacionado con los problemas complejos, es necesario ubicarse en el tramo de su carrera en el que publicó "Los números computables, con una aplicación al Entscheidungsproblem" en el año 1936. Es desde ahí, que al demostrar que la máquina de Turing era capaz de implementar cualquier problema matemático que pudiera representarsemediante un algoritmo, comienzan a surgir los problemas tratables los que se pueden resolver en tiempo polinomico e intratables; y además comienzan a estudiarse y catalogarse distintos tipos de problemas de variada complejidad a los cuales se les denominaron, durante los años 70’ por Stephen Arthur Cook y el Doctor Jhon Hopcroft, problemas “p” según sus características de tiempo polinomico enejecución. A continuación una pequeña descripción de estos tipos de problemas.  Un problema “p” es tratable siempre cuando este se pueda resolver en tiempo polinomico. Ejemplo: determinar el camino óptimo que debe recorrer un cartero que pasa por N casas necesita menos de 50N2+N segundos. Por otra parte los problemas de tipo: 2n no es determinable en tiempo polinomico pero no es posible saber siexiste un algoritmo que lo resuelva en tiempo polinomico, denominado “np”( non-deterministic polynomial time), siendo subconjunto de “p”, pero a la vez no es posible demostrar si “p=np”. Habiendo expuesto los tipos de problemas existentes, es ahora cuando las maquinas de Turing se hacen presente en el estudio de estos, dada la sencillez que tienen las maquinas para abstraer un problema y poderrepresentarlo de manera didáctica, pero teniendo la misma capacidad de computo de otros sistemas mas complejos como “C” o Java. Utilizándose maquinas de Turing determinísticas que termina su ejecución en un numero de pasos acotado por una función polinómica: O(n k), es decir, problemas que determinan un conjunto, con un si o no, si una palabra pertenece al lenguaje, ejemplo: verificar si la palabra es...