Fundamentos De Algoritmos
Páginas: 11 (2595 palabras)
Publicado: 25 de septiembre de 2011
Luis Mario Perez Molina
Fundamentos de Algoritmos
06/09/11
Tarea #4
La Computabilidad y Concepto de algoritmo: Máquina de Turing
La máquina de Turing es una caja negra (tan simple como una máquina de escribir y tan compleja como un ser humano) capaz no sólo de leer y escribir un alfabeto de símbolos finito a partir de una cantidad finita pero muy grande de cinta de papel, sino demodificar su propia configuración o "estado mental".
La máquina de Turing se convirtió en un instrumento ideal para probar si un procedimiento es efectivamente computable o no.
Funcionamiento
Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos. Consiste en una cabeza de lectura/escritura que examina una dimensión posiblemente infinita de unacinta bidireccional dividida en cuadros cada uno de los cuales está identificado con un 0 o un 1.
Para llevar a cabo algún algoritmo, la máquina se inicializa en algún estado interno arbitrario. A continuación, se pone en marcha y la máquina lee el bit que se encuentra en ese momento en su interior y ejecuta alguna operación con ese bit (lo cambia o no, dependiendo de su estado interno). Después semueve hacia la derecha o hacia la izquierda, y vuelve a procesar el siguiente bit de la misma manera. Al final se para, dejando el resultado al lado izquierdo por ejemplo.
Una instrucción típica podría ser: 01->11011i
La traducción es como sigue: si la máquina se encuentra en el estado interno 0 y lee 1 en la cinta, entonces pasará al estado interno 1101 (13), escribirá 1 y se moveráhacia la izquierda un paso (la cinta se moverá hacia la derecha). A continuación es conveniente inventar una notación para la secuencia del INPUT. Esta notación se llama notación binaria expandida. Consiste en cambiar la secuencia original binaria por otra construida de la siguiente forma: el 0 se cambia por 0 y el 1 por 10 y se ponen un cero a la izquierda y/o a la derecha del resultado si empieza oacaba en 1 respectivamente. Así por ejemplo, el número 13 que en binario es 1101 es en binario expandido 1010010 con un cero delante por esta última regla 01010010. Para volver al original hay que contraer el binario expandido con la siguiente regla:
Empezamos a leer por la izquierda el binario expandido. Cuando encontremos un 0 tomamos nota de cuántos 1 hay hasta llegar al siguiente 0 y loescribimos. Si encontramos que hay dos 0 seguidos, apuntaríamos un 0 porque no habría ningún 1. Con el 13 se haría: el primer 0 se encuentra en la primera posición y el siguiente 0 está en la posición 3. Entre los dos solo hay un 1. Lo anotamos. Seguidamente hay un 1, y después un 0, entonces apuntamos 1 porque hay un 1 entre medias de ellos. Esto es lo que se hace sucesivamente y encontramos: 1101que es el número original.
Cualquier función que pueda ser considerada de "modo natural" como computable puede ser computada por una máquina universal de Turing.
Si bien la conjetura no ha podido ser demostrada, hasta el momento ha resistido todos los intentos de encontrar un contraejemplo.
Computabilidad y no Computabilidad
Una de las cuestiones mas estudiadas en la teoría de lacomputabilidad ha sido la posibilidad de construir algoritmos que nos determinen si un determinado algoritmo posee o no una determinada propiedad.
En un principio se fueron obteniendo demostraciones individuales de la no computabilidadde cada una de estas cuestiones, de forma que se tenía la sensación de que casi cualquier pregunta interesante acerca de algoritmos era no computable.
A pesar de esto, ycomo consecuencia de la existencia de un programa universal hay otras muchas cuestiones interesantes que se han demostrado computables.
El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límites teóricos de los ordenadores.
Además de las cuestiones sobre algoritmos,...
Fundamentos de Algoritmos
06/09/11
Tarea #4
La Computabilidad y Concepto de algoritmo: Máquina de Turing
La máquina de Turing es una caja negra (tan simple como una máquina de escribir y tan compleja como un ser humano) capaz no sólo de leer y escribir un alfabeto de símbolos finito a partir de una cantidad finita pero muy grande de cinta de papel, sino demodificar su propia configuración o "estado mental".
La máquina de Turing se convirtió en un instrumento ideal para probar si un procedimiento es efectivamente computable o no.
Funcionamiento
Una máquina de Turing es un dispositivo que transforma un INPUT en un OUTPUT después de algunos pasos. Consiste en una cabeza de lectura/escritura que examina una dimensión posiblemente infinita de unacinta bidireccional dividida en cuadros cada uno de los cuales está identificado con un 0 o un 1.
Para llevar a cabo algún algoritmo, la máquina se inicializa en algún estado interno arbitrario. A continuación, se pone en marcha y la máquina lee el bit que se encuentra en ese momento en su interior y ejecuta alguna operación con ese bit (lo cambia o no, dependiendo de su estado interno). Después semueve hacia la derecha o hacia la izquierda, y vuelve a procesar el siguiente bit de la misma manera. Al final se para, dejando el resultado al lado izquierdo por ejemplo.
Una instrucción típica podría ser: 01->11011i
La traducción es como sigue: si la máquina se encuentra en el estado interno 0 y lee 1 en la cinta, entonces pasará al estado interno 1101 (13), escribirá 1 y se moveráhacia la izquierda un paso (la cinta se moverá hacia la derecha). A continuación es conveniente inventar una notación para la secuencia del INPUT. Esta notación se llama notación binaria expandida. Consiste en cambiar la secuencia original binaria por otra construida de la siguiente forma: el 0 se cambia por 0 y el 1 por 10 y se ponen un cero a la izquierda y/o a la derecha del resultado si empieza oacaba en 1 respectivamente. Así por ejemplo, el número 13 que en binario es 1101 es en binario expandido 1010010 con un cero delante por esta última regla 01010010. Para volver al original hay que contraer el binario expandido con la siguiente regla:
Empezamos a leer por la izquierda el binario expandido. Cuando encontremos un 0 tomamos nota de cuántos 1 hay hasta llegar al siguiente 0 y loescribimos. Si encontramos que hay dos 0 seguidos, apuntaríamos un 0 porque no habría ningún 1. Con el 13 se haría: el primer 0 se encuentra en la primera posición y el siguiente 0 está en la posición 3. Entre los dos solo hay un 1. Lo anotamos. Seguidamente hay un 1, y después un 0, entonces apuntamos 1 porque hay un 1 entre medias de ellos. Esto es lo que se hace sucesivamente y encontramos: 1101que es el número original.
Cualquier función que pueda ser considerada de "modo natural" como computable puede ser computada por una máquina universal de Turing.
Si bien la conjetura no ha podido ser demostrada, hasta el momento ha resistido todos los intentos de encontrar un contraejemplo.
Computabilidad y no Computabilidad
Una de las cuestiones mas estudiadas en la teoría de lacomputabilidad ha sido la posibilidad de construir algoritmos que nos determinen si un determinado algoritmo posee o no una determinada propiedad.
En un principio se fueron obteniendo demostraciones individuales de la no computabilidadde cada una de estas cuestiones, de forma que se tenía la sensación de que casi cualquier pregunta interesante acerca de algoritmos era no computable.
A pesar de esto, ycomo consecuencia de la existencia de un programa universal hay otras muchas cuestiones interesantes que se han demostrado computables.
El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límites teóricos de los ordenadores.
Además de las cuestiones sobre algoritmos,...
Leer documento completo
Regístrate para leer el documento completo.