¿Qué es una Máquina de Turing? (i)


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 expresado por 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 la ló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 camino de 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.

El problema 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 cualquier problema, 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 de formalizar 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 lógico teniendo en cuenta la forma en la que nos enseñaron las matemáticas a la mayoría de nosotros. Pero la realidad está bastante lejos de eso.

Se podría decir que un problema matemático es una afirmación de una determinada naturaleza que hay que determinar si es cierta o falsa. Veámoslo con un ejemplo.

Uno de los problemas matemáticos más célebres es el de la cuadratura del circulo, que dice:

¿Se puede construir un cuadrado, utilizando regla y compás, que posea un área igual a la de un círculo dado?

Alguien podría decir: pero vamos a ver, esto es una pregunta, ¿no acaba de decir que un problema matemático es una afirmación? Bueno sí, es cierto, pero si nos fijamos podemos escribir:

Se puede construir un cuadrado, utilizando regla y compás, que posea un área igual a la de un círculo dado.

Ésta expresión, que es una afirmación, es equivalente a la primera. Lo único que cambia es la forma de la respuesta: en el primer caso será o no, y en el segundo caso será la afirmación es verdadera o es falsa, pero el significado es el mismo en ambos casos.

Haciendo un pequeño esfuerzo, nos podemos imaginar cualquier problema matemático en forma de afirmación: Dos y dos suman cuatro es una afirmación verdadera, el área de un cuadrado es el cuadrado de la longitud de su lado es una afirmación verdadera y para cualquier trío de números enteros a, b y c y cualquier número entero n mayor que dos se cumple que an+bn=cn es una afirmación falsa (hay una demostración maravillosa para esto, pero la que conocemos tiene 98 páginas)

Por tanto, ahora sí podemos comprender que el problema de la decisión consiste en decidir si se puede saber siempre si una afirmación (vista como un problema matemático) es verdadera o falsa, o por el contrario existen afirmaciones cuya naturaleza no se puede determinar.

Por cierto, la afirmación referente a la cuadratura del círculo es falsa.


Implementar un algoritmo

Ya sabemos lo que es un problema matemático, pero ¿qué es un algoritmo? Por suerte esto es mucho más sencillo.

Un algoritmo es un conjunto ordenado de pasos elementales que nos ayudan a resolver un problema. Por ejemplo, si quiero ver el televisor, podría utilizar el siguiente algoritmo para hacerlo:

1. ¿Estoy en el salón?

1.1 No → ir al salón, volver a 1

1.2 Si → pasar a 2

2. ¿Está encendido el televisor?

2.1 No → encenderlo, volver a 2

2.2 Si → pasar a 3

3. ¿Quiero seguir castigando mi cerebro?

3.1 No → apagarlo, FIN

3.2 Si → volver a 2, tú verás lo que haces

Así, un problema matemático expresado por medio de un algoritmo no es más que una afirmación que puede resolverse en un número determinado de pasos elementales. Por ejemplo, dos más dos es cuatro se puede resolver partiendo del dos, sumándole uno, sumándole otro uno y comprobando el resultado. Como éste es cuatro, la afirmación es verdadera.

Definir ahora lo que significa implementar es fácil: implementar un algoritmo es leerlo y ejecutarlo (ponerse a ver la tele o apagarla, vamos). Así que lo que hemos sacado en claro por ahora es que una Máquina de Turing es algo que implementa algoritmos que representan un problema matemático.

Llegados a este punto, nos tomaremos un pequeño respiro y volveremos con la segunda parte del artículo, en la que explicaré lo que es un autómata, un modelo matemático y, por fin, una Máquina de Turing.

Lo publicó Javier Oribe en  El Máquina de Turing.

About these ads

7 comentarios

  1. me parece muy buena la informacion, me hubiera gustado sin embargo, que pusiera datos sobre cuanto pesaba, cuanto media, que contenia o algo de eso.
    tal vez no era su tema pero hubiera estado myu bueno
    igual estubo bien su informacion
    saludos :D y felicidades

    1. No era una máquina de verdad, es un modelo teòrico.

  2. Excelente…

  3. Joder, llegué deprimido de una clase de 3 horas en la que explicaban esto… aún me falta la segunda parte, pero ha sido más productivo este texto que la explicación en la U

  4. Excelente explicación, gracias!

  5. Gracias, por la información y, sobretodo, por la manera tan clara en la que la has presentado.

  6. Damián Jesús Granados Ruiz |Responder

    Como todo hijo de vecino, cuando tuve 18 años, me sentí atraído por la informática. Tuve la oportunidad de iniciar la licenciatura, y en esos meses iniciales, leí un tema introductorio donde se hablaba de la revolución informática, con la similitud a lo que fue la revolución industrial. Todo comenzó con la teoría de la computación, donde Alan Turing fue un auténtico pionero. Pero algo fallaba en mi comprensión de aquel texto, en la medida de que cuando manejabas el ordenador para hacer un inventario era más sencillo hacerlo en papel. Veintitres años después, como usuario de internet y el gran desarrollo de las aplicaciones de las que se disponen que nos sirven como herramientas de gran apoyo para realizar tareas, se observa y se palpa los resultados de aquellos esquemas teóricos, casi imposibles de llevar a la práctica. Todos conocemos a los hacedores del milagro, como Gates o Jobs, pero ¿que hubiera sido de ellos sin el esquema de Turing y otros matemáticos? ¿Se hará algún día alguna película decente en Hollywood sobre algún matemático? ¿Se otorgará algún día el Nobel a las matemáticas? ¿se contratará algún día a un matemático en una empresa,… un banco quizá? ¿se interesarán los alumnos algún día en las matemáticas igual que en jugar a basket… alentados por sus padres? ¿se explicarán en las aulas las matemáticas de manera comprensible y eficiente,… basándose en ejemplos y aplicaciones, para en un mayor nivel comprender las demostraciones? Quizá cuando algún licenciado, graduado o aficionado a las matemáticas se demuestre que se ha hecho millonario a través de ellas…. Un fuerte abrazo Javi, y suerte… después de decidir voluntariamente o forzadamente (teoría de la decisión).

Si tiene algo que decir, éste es el momento

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

Cuentos Cuánticos

Un sitio donde los cuentos de ciencia están contados y no contados al mismo tiempo

J.M.Hernández

Página personal

"Usted tiene perfecto derecho a elegir entre conocer las matemáticas o no, pero debe ser consciente de que, en caso de no conocerlas, podrá ser manipulado más fácilmente." John A. Paulos

Los Matemáticos no son gente seria

"Usted tiene perfecto derecho a elegir entre conocer las matemáticas o no, pero debe ser consciente de que, en caso de no conocerlas, podrá ser manipulado más fácilmente." John A. Paulos

Francis (th)E mule Science's News

La Ciencia de la Mula Francis. Relatos breves sobre Ciencia, Tecnología y sobre la Vida Misma

El mundo de Rafalillo

"Usted tiene perfecto derecho a elegir entre conocer las matemáticas o no, pero debe ser consciente de que, en caso de no conocerlas, podrá ser manipulado más fácilmente." John A. Paulos

"Usted tiene perfecto derecho a elegir entre conocer las matemáticas o no, pero debe ser consciente de que, en caso de no conocerlas, podrá ser manipulado más fácilmente." John A. Paulos

Hablando de Ciencia

La Ciencia al Alcance de tu mano

Tito Eliatron Dixit

"Usted tiene perfecto derecho a elegir entre conocer las matemáticas o no, pero debe ser consciente de que, en caso de no conocerlas, podrá ser manipulado más fácilmente." John A. Paulos

Gaussianos

Porque todo tiende a infinito...

La Ciencia y sus Demonios

La primera gran virtud del hombre fue la duda y el primer gran defecto la fe (Carl Sagan)

Seguir

Recibe cada nueva publicación en tu buzón de correo electrónico.

Únete a otros 591 seguidores

%d personas les gusta esto: