Maquina de turing

Maquina de turing

El concepto de Máquina de Turing fue introducido por Alan Turing en el trabajo On computable numbers, with an application to the Entscheidungsproblem, publicado por la SociedadMatemática de Londres en 1936, en el cual se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse acualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. Turing ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podíaresolver.
Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.
Mediante este modelo teórico y el análisis de complejidad dealgoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones en tiempo polinómicoson encontradas según el determinismo y no determinismo respectivamente de la máquina de Turing.
De hecho, se puede probar matemáticamente que para cualquier programa de computadora es posible crearuna máquina de Turing equivalente. Esta prueba resulta de la Tesis de Church-Turing, formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX[]
La idea subyacente esel concepto de que una máquina de Turing es una persona ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinadosólo una parte finita es accesible.

Definición formal
Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla , donde:[2]
* es un conjunto finito de estados.
* es unconjunto finito de símbolos distinto del espacio en blanco, denominado alfabeto de máquina o de entrada.
* es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta. ()
* es...