About Taringa!

Popular channels

Los Principios de la Informatica(Turing)

Alan Mathison Turing (23 de junio de 1912 - 7 de junio de 1954)

Introduccion al modelo de turning (el porque de la maquina):

¿Qué significa esto en lo que se refiere al universo físico? La respuesta de Wheeler a esta pregunta es tan asombrosa como profunda. Concluye que ya no podemos seguir considerando el universo como un hardware que existe "ahí fuera", sino que debemos empezar a verlo como compuesto por un "software 'significativo'" y situado, como dice Wheeler, "quién sabe dónde". En otras palabras, hemos empezado a ver el universo como constituido en definitiva no por materia y energía, sino por pura información". Michael Talbot. "Mas allá de la Teoría Cuántica". Edit. Gedisa 3ª Edición 1995 Barcelona.

Definicion de un Algoritmo A través de la maquina de Turnig:

Encontra de lo que pudiera parecer, la ciencia de la computación y las teorías sobre computabilidad no pertenecen a la disciplina que hoy conocemos como "Informática", sino a las matemáticas, que son, con mucho, anteriores a aquella.

A principio del siglo XX, el campo de la matemática teórica estaba en plena efervescencia, gracias sobre todo a los trabajos de Hilbert y Gödel. En particular Hilbert había planteado ciertas cuestiones que derivaron en las teorías de la computación y la computabilidad, en concreto cual sería el significado de la computabilidad de un procedimiento.

En matemáticas se considera que un método o procedimiento es efectivo para obtener un resultado cuando se cumple que:

El procedimiento puede ser expresado mediante un algoritmo (un número finito de instrucciones concretas 1.2.1); en el que cada instrucción puede ser expresada por un número finito de símbolos.
El procedimiento puede ser seguido sin error para conseguir el resultado en un número finito de pasos.
El procedimiento puede ser (al menos teóricamente) seguido por un humano sin más ayuda que un papel y lápiz.
El procedimiento no exige ninguna habilidad o inteligencia especial por parte de la persona que lo ejecuta. En lenguaje coloquial diríamos que "hasta un tonto podría hacerlo". La idea es que solo haya que seguir ciertas reglas de forma mecánica. Por esta razón cuando se cumplen estas condiciones se dice que el procedimiento es efectivo o "mecánico".

Para dar una definición matemáticamente precisa de lo que es un algoritmo, Turing ideó un dispositivo imaginario al que denominó Máquina de computación lógica LCM ("Logical Computing Machine"), pero que ha recibido en su honor el nombre de máquina de Turing. Aunque su propuesta es anterior a la aparición de los computadores digitales (1936 "On computable numbers, with an application to the Entscheidungproblem"), actualmente es el objeto central de estudio de los teóricos de la computación. Precisamente la definición moderna de lo que es "Computable" se basa en este concepto, y del mismo modo que cuando se habla de inteligencia artificial es inevitable referirse al Test de Turing, cuando se habla de algoritmos y computación es casi inevitable encontrar alguna referencia a la máquina de Turing. Por si esto fuera poco, los conceptos subyacentes en la idea han jugado un papel importante en las recientes teorías filosóficas sobre la mente.

Lo que confiere al dispositivo su extraordinaria importancia es que es capaz de resolver cualquier problema matemático a condición de que haya sido reducido a un algoritmo.

Maquina De Turning:

Una máquina de Turing es un autómata que se mueve sobre una secuencia lineal de datos. En cada instante la máquina puede leer un solo dato de la secuencia (generalmente un carácter) y realiza ciertas acciones en base a una tabla que tiene en cuenta su "estado" actual (interno) y el último dato leído. Entre las acciones está la posibilidad de escribir nuevos datos en la secuencia; recorrer la secuencia en ambos sentidos y cambiar de "estado" dentro de un conjunto finito de estados posibles.

En realidad la máquina de Turing es más una abstracción matemática que un dispositivo físico o mecánico. El hecho que se le denomine "máquina" se debe a que su funcionamiento puede ser descrito en términos de operaciones individuales muy sencillas que sugieren una implementación real muy simple, lo que ha motivado que existan muchas versiones prácticas del mismo.

Existen diversas "variedades" de una máquina de Turing, pero la más simple puede ser descrita diciendo que es cualquier dispositivo que cumple las siguientes condiciones:

Tiene una cinta sobre la que puede desplazarse a izquierda y derecha un cabezal de lectura/escritura. La cinta contiene una serie de celdas, y en cada una de ellas puede escribirse un símbolo de un conjunto finito; este conjunto de símbolos se denomina el alfabeto de la máquina. En principio todas las celdas que no se hayan escrito antes contienen un carácter especial nulo o vacío (que se representa por 0 o #). La cinta puede contener tantas celdas a derecha e izquierda del cabezal como sean necesarias para el funcionamiento de la máquina.

El cabezal puede moverse a derecha (R) a izquierda (L) de su posición actual, así como leer el contenido de una celda o escribir en ella cualquier carácter de su alfabeto.

Existe un registro de estado que almacena el estado de la máquina. El número de estados posibles es finito, y no se exige ningún estado especial con el que sea iniciada la máquina.

Existe una tabla de acción , que contiene las instrucciones de lo que hará el autómata. Estas instrucciones representan en cierta forma el "programa" de la máquina. Las ejecución de cada instrucción de la tabla de acción incluye cuatro pasos:

Leer un carácter en la posición actual.

Escribir un nuevo símbolo en esta posición (puede ser el mismo que había). El símbolo a escribir es alguno del alfabeto de la máquina, y depende del carácter leído y del estado actual.

Desplazar el cabezal una celda a derecha o izquierda (R/L); en algunos modelos el desplazamiento puede ser nulo (detener H).

Decidir cual será el nuevo estado en función del carácter que se acaba de leer y del estado actual. Si la tabla de acción no contiene ninguna correspondencia con el estado actual y el símbolo leído, entonces la máquina detiene su funcionamiento.

En los modelos didácticos computarizados la tabla suele definirse mediante una matriz de cinco columnas que contiene:

Estado/Carácter-leído/Carácter-a-escribir/Movimiento/Nuevo-estado


En el recuadro se incluye una muestra de una de estas tablas. Representa el comportamiento de una máquina de turing que es capaz de sumar 1 a cualquier número unario ( 0.1). El alfabeto solo tiene dos símbolos: Vacío (0) y valor (1). La máquina puede adoptar tres estados diferentes numerados del 0 al 2 (es costumbre señalar el estado inicial con 0). El movimiento H ("Halt") significa no desplazar el cabezal. En este caso la máquina se detiene (o entra en un bucle sin fin).


También es posible representar la tabla de acción mediante un grafo. Los diferentes estados internos se representan por círculos. Los cambios de estado con flechas a las que se añade una leyenda. Generalmente se utiliza una flecha para señalar el estado inicial. En la figura 1 se muestra el grafo correspondiente a la tabla.

Es notable que el diseño de Turing contiene de forma implícita la idea de que el autómata puede alterar su propio programa, pero el punto más significativo de su filosofía de funcionamiento es que se comporta como la mente, en el sentido que la configuración interna de la máquina establece el entorno en el que se toman las decisiones, de forma que la acción depende de dos factores: el estado interno y la información externa que puede "ver" a través de su cabezal . La consecuencia es que es imposible predecir su comportamiento de la simple inspección de su tabla de acción, ya que el comportamiento depende también de la entrada recibida.

El hecho que el número de estados posibles y su alfabeto sea finitos, califica a estos autómatas como máquinas de estados finitos FSM ("Finite State Machine").

Fotografia de la Maquina en si:



para cerrar... el que encuentre alguna formula para pasar de problemas "HARD" a problemas comunes reclame su millon de dolares y la glora


Fuente: http://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
http://www.zator.com/Cpp/E0_1_1.htm
algo de mi conocimiento
0No comments yet
      GIF