La maquina de turing

Máquina de Turing

Es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.

está formado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados.
Su funcionamiento se basa en unafunción de transición, que recibe un estado inicial y una cadena de caracteres) pertenecientes al alfabeto de entrada.
Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.
Historia
Fue creada por Alan Turing quien ideó un modelo formal de computador, la , y demostró que existían problemas que unamáquina no podía resolver.
Funcionamiento
La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor.
Una respuesta que genera muchas preguntas

Una Máquina de Turing es un modelo matemático que consiste en un autómata capaz de implementar cualquier problema matemático expresadopor medio de un algoritmo. Dicho esto, alguien podría preguntarse porqué esta sección no se llama Respuestas difíciles a preguntas fáciles, pero no se alarmen. Para poder explicar bien los que es una máquina de Turing y, lo que me interesa más, porqué es tan importante, voy a necesitar que comprendan bien la frase con la que se inicia este artículo. Así que, como dijo aquel, vayamos por partes.Alan Turing

Antes de meternos de lleno en esta explicación acerca de la Máquina de Turing, hagamos una pequeña referencia a la persona que la descubrió y que le da nombre.

Alan Turing fue un matemático inglés que vivió durante la primera mitad del siglo XX. Aunque fue un matemático brillante en muchos campos, destacando especialmente en criptografía, su principal interés se centraba en lalógica, que en aquellos momentos se encontraba en plena ebullición gracias al intento de David Hilbert de hallar una formulación de las matemáticas sobre una base estricta de lógica formal. La Máquina de Turing, o Máquina de Computación Lógica como la llamaba él, fue quizás la mayor aportación de Alan Turing a esta tarea y con seguridad su descubrimiento de mayor transcendencia, ya que abrió el caminode la ciencia de la Computación, que a su vez nos lleva al computador que en estos momentos estoy utilizando para escribir esto, o al que usted está usando para leerlo. En definitiva, Alan Turing fue uno de los científicos más importantes de la primera mitad del siglo XX y, sin duda, una de las mentes que más influyó en la manera actual que tenemos de ver el mundo e interactuar con él.

Elproblema de la decisión

Dentro del esfuerzo de Hilbert y su equipo por formalizar las matemáticas, se planteó una pregunta para la que no había respuesta: ¿Es posible encontrar una manera sencilla de decidir si un problema matemático cualquiera tiene solución? Cuidado que nos podemos confundir, la pregunta no es si podemos encontrar un método sencillo para descubrir la solución de cualquierproblema, sino de decidir (o, si se prefiere, comprobar) si un problema cualquiera puede solucionarse siempre o si existen problemas para los que no puede encontrarse ninguna solución.

Esto, que parece un mero entretenimiento algo freak, tuvo una importancia trascendental, ya que una respuesta afirmativa significaba que todos los problemas matemáticos tenían una solución, y por tanto el proyecto deformalizar todo el conocimiento matemático como una ciencia completa y sin fisuras tendría mayores posibilidades de ser viable.

Problemas matemáticos

Pero ¿qué es exactamente un problema matemático? Cuando se habla de un problema de matemáticas, a la mayoría de las personas les viene a la cabeza la idea de una serie de cálculos más o menos complicados que hay que resolver, algo que es...