Existen problemas que van fuera del alcance de una computadora, son los llamados problemas no computables. Hay una infinidad de ellos que no sabemos ni por donde atacar. Cuando encontremos un problema difícil, está demostrado que podemos encontrar otro aún más difícil que ése y así infinitas veces.
Aún así, no todo está perdido, existen una infinidad de problemas que podemos resolver con una computadora, los problemas computables. Pero por desgracia, la gran mayoría de ellos, donde sí tenemos alguna manera de resolverlos (llámense algoritmos), tenemos el inconveniente en el tiempo que nos llevamos para obtenerd una solución. Estos métodos los resuelven, sí, pero en tiempos humanamente intratables, ¿horas?, ¿años?, ¿siglos?
¿Entonces no podemos resolver nada? ¿Una computadora no sirve para nada? Hay algo cierto en eso, una computadora puede resolver muy pocos problemas. Actualmente los científicos han tratado que las computadoras sean más veloces y así puedan resolver problemas un poquito más grandes. Pero ¿será la solución colocar cada vez más procesadores en una tarjeta?, ¿colocar más memoria?, ¿hardware? No lo creo.
La computación es una ciencia muy joven, con muchos problemas sin resolver y mucho trabajo que hacer. Investigadores tratan de darle la vuelta, y han creado nuevos paradigmas para resolver problemas, nuevos modelos.
Por ejemplo, las computadoras cuánticas, algoritmos genéticos, DNA Computing, redes neuronales, etc. Muchas de estas propuestas son ya usadas e investigadas a fondo, pero no dejan de ser modelos probabilísticos. Ciertamente aproximan bien las soluciones de los problemas, pero nunca garantizan que se encontrará una solución y mucho menos que será óptima.
Entonces ¿qué es lo que debemos hacer? ¿El modelo de la máquina de Turing necesita ser remplazado, modificado? ¿En este nuevo modelo necesitamos ver los problemas que veíamos difíciles como fáciles? ¿Qué tanto cambiaría la computación actual con un nuevo modelo? ¿existirá ese nuevo modelo o será equivalente a la Máquina de Turing también? ¿Estamos bien como estamos? ¿Si pudieramos resolver esos problemas que son intratables, qué problemas no podríamos resolver con nuestro nuevo modelo?
Aún así, no todo está perdido, existen una infinidad de problemas que podemos resolver con una computadora, los problemas computables. Pero por desgracia, la gran mayoría de ellos, donde sí tenemos alguna manera de resolverlos (llámense algoritmos), tenemos el inconveniente en el tiempo que nos llevamos para obtenerd una solución. Estos métodos los resuelven, sí, pero en tiempos humanamente intratables, ¿horas?, ¿años?, ¿siglos?
¿Entonces no podemos resolver nada? ¿Una computadora no sirve para nada? Hay algo cierto en eso, una computadora puede resolver muy pocos problemas. Actualmente los científicos han tratado que las computadoras sean más veloces y así puedan resolver problemas un poquito más grandes. Pero ¿será la solución colocar cada vez más procesadores en una tarjeta?, ¿colocar más memoria?, ¿hardware? No lo creo.
La computación es una ciencia muy joven, con muchos problemas sin resolver y mucho trabajo que hacer. Investigadores tratan de darle la vuelta, y han creado nuevos paradigmas para resolver problemas, nuevos modelos.
Por ejemplo, las computadoras cuánticas, algoritmos genéticos, DNA Computing, redes neuronales, etc. Muchas de estas propuestas son ya usadas e investigadas a fondo, pero no dejan de ser modelos probabilísticos. Ciertamente aproximan bien las soluciones de los problemas, pero nunca garantizan que se encontrará una solución y mucho menos que será óptima.
Entonces ¿qué es lo que debemos hacer? ¿El modelo de la máquina de Turing necesita ser remplazado, modificado? ¿En este nuevo modelo necesitamos ver los problemas que veíamos difíciles como fáciles? ¿Qué tanto cambiaría la computación actual con un nuevo modelo? ¿existirá ese nuevo modelo o será equivalente a la Máquina de Turing también? ¿Estamos bien como estamos? ¿Si pudieramos resolver esos problemas que son intratables, qué problemas no podríamos resolver con nuestro nuevo modelo?
5 comentarios:
La respuesta fácil es decir inmediatamente, pues como la máquina de Turing es un AFD conectado a una cinta, lo primero que hace falta es tomar un AFND y conectarlo a algo. El problema que tengo con ese modelo es que, si ese "algo" es una cinta, *los* cabezales (como no es determinista) un día van a chocar y escribir dos al mismo tiempo en la misma celda. Hay que escoger el sustituto de la cinta con cuidado.
Se supone que la computación cuántica es AFND, aunque por ahí tiene sus trucos. El problema de la cinta lo resuelve diciendo (muy a grosso modo) que cada celda tiene, por decir algo, 15% de probabilidad de tener un cero, 48% de probabilidad de tener un uno, y 37% de probabilidad de estar en blanco. Así no hay problema con escrituras simultáneas.
Pero lo malo es que un AFND todavía no es suficiente :(
No, no es suficiente :(
Pero aparte peor, porque sabemos que un AFD es equivalente a un AFND, así que de alguna manera eso "lo mismo" :(
¡No, claro que no es lo mismo! Para todo AFND existe un AFD equivalente, pero en términos de computabilidad no son iguales. Si lo fueran, no habría diferencia al emplear cómputo en paralelo, para empezar. Un modelo basado en AFND permite factorizar enteros en tiempo polinomial mediante el algoritmo de Shor, por ejemplo.
Cuando digo que no es suficiente es porque aún con ese modelo todavía no puedes, por decir algo, construir un algoritmo general que diga si una figura geométrica arbitraria cubre el plano. Si la respuesta va a ser "no", puedes esperar hasta el fin del mundo y no vas a estar completamente seguro.
Así es, pero por desgracia el cómputo paralelo está muy atado al hardware, entre más crece el problema a resolver, se necesitan más procesadores. y es cierto, por desgracia aún así, no podemos resolver esta problemática.
DNA Computing trata de resolver esto usando un paralelismo impresionante, con millones de cadenas de DNA casi garantizando probar todas las soluciones en tiempos relativamente cortos, habando de horas para problemas "grandes".
No te preocupes memo, ya 'encontraremos' un modelo más poderoso que las máquinas de turing. Yo creo que las pregunta que debieramos hacer es ¿las máquinas de turing son un caso particular de....?
Publicar un comentario