Vamos a imaginar una extraña máquina… una máquina que consta de simplemente de una cinta de papel y un cabezal que sea capaz de hacer estas tres acciones:
- Moverse una posición a la derecha o a la izquierda
- Leer un caracter
- Escribir un caracter
Parece sencillo, ¿no? Esta máquina se conoce como Máquina de Turing, en honor a su creador, Alan Turing. Y es bastante sencillo construir una. Hay quien ha optado por el Lego, aunque también podemos simular una con papel y lápiz…
Ahora agárrese a la silla: esa máquina inocente puede hacer exactamente lo mismo que su potente ordenador. Dicho de otro modo más impactante: no podrá hacer nada con su ordenador que yo no pueda hacer con mi máquina de Turing.
Piense en algo que pueda hacer con su equipo, lo más complicado… puedo jurarle que la máquina de Turing puede hacerlo. Probablemente más despacio, pero lo hará… ¿Se lo imagina? Esto no es vudú ni magia negra, sino que se debe al hecho (dramático) de que un ordenador no es más que una máquina de Turing.
Si queremos una explicación más detallada, tenemos que entender que los ordenadores no son más que unos dispositivos que computan, esto es, que calculan cosas a partir de otras cosas. Dibujar algo en una pantalla no es una tarea complicada para un ordenador, en absoluto… sus problemas vienen cuando se trata de realizar operaciones o decidir sobre problemas… de hecho, si pudieramos meter en una bolsa todos los problemas del universo, veríamos que los ordenadores sólo son capaces de resolver unos pocos… Otro día comentaré algunos problemas que los computadores convencionales jamás podrán solucionar…
El panorama es un poco deprimente… mi potente equipo no puede hacer nada que no pueda hacer la máquina de Lego que comentaba antes… esto, en teoría de computación se conoce como el «límite computacional», que delimita esa pequeña porción de problemas en los que los ordenadores se sienten cómodos… Este límite no ha cambiado, ni cambiará… los ordenadores son capaces de resolver problemas que antes no podían resolverse en un tiempo razonable, pero no hacen nada ahora que no pudieran hacer antes.
Alan Turing postuló que el poder de su máquina llegaba hasta el mismo límite computacional. Y parece que no se equivocó…
¿Puede alguien dar más detalles sobre el límite computacional este?. Jo, esto ha sido como hace años cuando un profe nos dejó tirados con el teorema de Godel y los límites del conocimiento humano pero no nos quiso dar detalles para no complicarnos la vida … :)
[Otro que vino de CPI y se quedó]
Es un tema ciertamente complicado (todo lo que tiene de complejo lo tiene de interesante…), pero escribiremos algo más sobre eso :-)
¡Gracias por tu visita!
Excelentes artículos veo por aquí.
Puntualizo, no es que la MT haga «exactamente» lo mismo que un ordenador. Hace más porque su memoria es infinita.
Y, aunque no sé si es este u otro post similar el contiene el despiste, no es que una MT «nunca» pueda saber si un programa para, es que «no siempre» puede saberlo…
Un saludo!