tag:blogger.com,1999:blog-2156351450610104971.post2349265662734123600..comments2023-05-11T01:26:15.287-07:00Comments on No sueñes tu vida. Vive tu sueño.: Neo-computationMemohttp://www.blogger.com/profile/06502069611432789430noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-2156351450610104971.post-17119403125049635322009-03-23T18:18:00.000-07:002009-03-23T18:18:00.000-07:00No te preocupes memo, ya 'encontraremos' un model...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....?PAGEhttps://www.blogger.com/profile/15989930277691323101noreply@blogger.comtag:blogger.com,1999:blog-2156351450610104971.post-37146303039472125742009-03-19T19:48:00.000-07:002009-03-19T19:48:00.000-07:00Así es, pero por desgracia el cómputo paralelo est...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. <BR/><BR/>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".Memohttps://www.blogger.com/profile/06502069611432789430noreply@blogger.comtag:blogger.com,1999:blog-2156351450610104971.post-15258422733782541002009-03-19T19:28:00.000-07:002009-03-19T19:28:00.000-07:00¡No, claro que no es lo mismo! Para todo AFND exis...¡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.<BR/><BR/>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.jsofferhttps://www.blogger.com/profile/13243634407449930234noreply@blogger.comtag:blogger.com,1999:blog-2156351450610104971.post-1198943480292425462009-03-19T18:00:00.000-07:002009-03-19T18:00:00.000-07:00No, no es suficiente :(Pero aparte peor, porque sa...No, no es suficiente :(<BR/><BR/>Pero aparte peor, porque sabemos que un AFD es equivalente a un AFND, así que de alguna manera eso "lo mismo" :(Memohttps://www.blogger.com/profile/06502069611432789430noreply@blogger.comtag:blogger.com,1999:blog-2156351450610104971.post-84143503262045778162009-03-19T01:42:00.000-07:002009-03-19T01:42:00.000-07:00La respuesta fácil es decir inmediatamente, pues c...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.<BR/><BR/>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.<BR/><BR/>Pero lo malo es que un AFND todavía no es suficiente :(jsofferhttps://www.blogger.com/profile/13243634407449930234noreply@blogger.com