Diferencia entre revisiones de «Máquina de Turing»
m (Texto reemplazado: «<div align="justify">» por «») |
|||
| (No se muestran 9 ediciones intermedias de 5 usuarios) | |||
| Línea 1: | Línea 1: | ||
| − | {{Objeto|nombre=Máquina de Turing|imagen= | + | {{Objeto |
| + | |nombre=Máquina de Turing | ||
| + | |imagen=Turing_1.png | ||
| + | |descripcion=Representación artística de la Máquina de Turing.}}'''Máquina de Turing'''(MT), es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma. | ||
| − | + | == Características generales == | |
| − | |||
| − | |||
| − | == Historia == | + | Este modelo está formado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual puede ser infinita) pertenecientes al alfabeto de entrada. |
| − | Alan Turing introdujo el concepto de máquina de Turing en el trabajo On computable numbers, with an application to the Entscheidungsproblem, publicado por | + | |
| − | Con este aparato extremadamente sencillo es posible realizar | + | La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo [[Símbolo]] perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida. |
| − | Mediante este modelo teórico y el análisis de la complejidad de los algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones pueden encontrarse en tiempo polinómico por máquinas de Turing deterministas y no deterministas, respectivamente. | + | |
| − | Precisamente, la tesis de Church-Turing formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX caracteriza la noción informal de computabilidad con la computación mediante una máquina de Turing. | + | == Historia == |
| − | La idea subyacente es el concepto de que una máquina de Turing puede verse como un autómata ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. | + | |
| + | [[Alan Turing]] introdujo el concepto de máquina de Turing en el trabajo On computable numbers, with an application to the Entscheidungsproblem, publicado por la Sociedad Matemática de [[Londres]] en [[1936]], en el que se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no. | ||
| + | |||
| + | Turing ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver. | ||
| + | |||
| + | Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar. | ||
| + | |||
| + | Mediante este modelo teórico y el análisis de la complejidad de los algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones pueden encontrarse en tiempo polinómico por máquinas de Turing deterministas y no deterministas, respectivamente. | ||
| + | |||
| + | Precisamente, la tesis de Church-Turing formulada por Alan Turing y [[Alonzo Church]], de forma independiente a mediados del siglo XX caracteriza la noción informal de computabilidad con la computación mediante una máquina de Turing. | ||
| + | |||
| + | La idea subyacente es el concepto de que una máquina de Turing puede verse como un autómata ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible. | ||
| + | |||
| + | == Funcionamiento == | ||
| + | |||
| + | La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a: | ||
| − | |||
| − | |||
Avanzar el cabezal lector/escritor hacia la derecha. | Avanzar el cabezal lector/escritor hacia la derecha. | ||
| − | Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a escribir en la cinta. | + | |
| − | La memoria es la cinta de la máquina que se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado "blanco". Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, "si estamos en el estado x leyendo la | + | Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a escribir en la cinta. |
| − | La máquina de Turing puede considerarse como un autómata | + | |
| + | La memoria es la cinta de la máquina que se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado "blanco". Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, "si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha". | ||
| + | |||
| + | La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido, es capaz de reconocer los lenguajes recursivamente enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional. | ||
== Máquina de Turing Cuántica == | == Máquina de Turing Cuántica == | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | [[ | + | En [[1985]], Deutsch presentó el diseño de la primera Máquina cuántica basada en una máquina de Turing. Con este fin enunció una nueva variante la tesis de Church-Turing dando lugar al denominado "principio de Church-Turing-Deutsch". |
| − | [[ | + | La estructura de una máquina de Turing cuántica es muy similar a la de una máquina de Turing clásica. Está compuesta por los tres elementos clásicos: una cinta de memoria infinita en donde cada elemento es un [[qubit]], un procesador finito y un cabezal. |
| − | + | El procesador contiene el juego de instrucciones que se aplica sobre el elemento de la cinta señalado por el cabezal. El resultado dependerá del qubit de la cinta y del estado del procesador. El procesador ejecuta una instrucción por unidad de tiempo. | |
| − | |||
| − | + | La cinta de memoria es similar a la de una máquina de Turing tradicional. La única diferencia es que cada elemento de la cinta de la máquina cuántica es un qubit. El alfabeto de esta nueva máquina está formado por el espacio de valores del [[qubit]]. La posición del cabezal se representa con una variable entera. | |
| + | == Fuentes == | ||
| + | * [http://enciclopedia.us.es/index.php/Máquina_de_Turing enciclopedia.us.es] | ||
| + | * [http://www.mitecnologico.com/ www.mitecnologico.com] | ||
| + | |||
[[Category:Ciencias_informáticas_y_Telecomunicaciones]] | [[Category:Ciencias_informáticas_y_Telecomunicaciones]] | ||
última versión al 08:16 14 ago 2019
| ||||
Máquina de Turing(MT), es un modelo computacional que realiza una lectura/escritura de manera automática sobre una entrada llamada cinta, generando una salida en esta misma.
Sumario
Características generales
Este modelo está formado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco (normalmente b, Δ o 0), un conjunto de estados finitos y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres (la cinta, la cual puede ser infinita) pertenecientes al alfabeto de entrada.
La máquina va leyendo una celda de la cinta en cada paso, borrando el símbolo en el que se encuentra posicionado su cabezal y escribiendo un nuevo Símbolo perteneciente al alfabeto de salida, para luego desplazar el cabezal a la izquierda o a la derecha (solo una celda a la vez). Esto se repite según se indique en la función de transición, para finalmente detenerse en un estado final o de aceptación, representando así la salida.
Historia
Alan Turing introdujo el concepto de máquina de Turing en el trabajo On computable numbers, with an application to the Entscheidungsproblem, publicado por la Sociedad Matemática de Londres en 1936, en el que se estudiaba la cuestión planteada por David Hilbert sobre si las matemáticas son decidibles, es decir, si hay un método definido que pueda aplicarse a cualquier sentencia matemática y que nos diga si esa sentencia es cierta o no.
Turing ideó un modelo formal de computador, la máquina de Turing, y demostró que existían problemas que una máquina no podía resolver.
Con este aparato extremadamente sencillo es posible realizar cualquier cómputo que un computador digital sea capaz de realizar.
Mediante este modelo teórico y el análisis de la complejidad de los algoritmos, fue posible la categorización de problemas computacionales de acuerdo a su comportamiento, apareciendo así, el conjunto de problemas denominados P y NP, cuyas soluciones pueden encontrarse en tiempo polinómico por máquinas de Turing deterministas y no deterministas, respectivamente.
Precisamente, la tesis de Church-Turing formulada por Alan Turing y Alonzo Church, de forma independiente a mediados del siglo XX caracteriza la noción informal de computabilidad con la computación mediante una máquina de Turing.
La idea subyacente es el concepto de que una máquina de Turing puede verse como un autómata ejecutando un procedimiento efectivo definido formalmente, donde el espacio de memoria de trabajo es ilimitado, pero en un momento determinado sólo una parte finita es accesible.
Funcionamiento
La máquina de Turing consta de un cabezal lector/escritor y una cinta infinita en la que el cabezal lee el contenido, borra el contenido anterior y escribe un nuevo valor. Las operaciones que se pueden realizar en esta máquina se limitan a:
Avanzar el cabezal lector/escritor hacia la derecha.
Esta tabla toma como parámetros el estado actual de la máquina y el carácter leído de la cinta, dando la dirección para mover el cabezal, el nuevo estado de la máquina y el valor a escribir en la cinta.
La memoria es la cinta de la máquina que se divide en espacios de trabajo denominados celdas, donde se pueden escribir y leer símbolos. Inicialmente todas las celdas contienen un símbolo especial denominado "blanco". Las instrucciones que determinan el funcionamiento de la máquina tienen la forma, "si estamos en el estado x leyendo la posición y, donde hay escrito el símbolo z, entonces este símbolo debe ser reemplazado por este otro símbolo, y pasar a leer la celda siguiente, bien a la izquierda o bien a la derecha".
La máquina de Turing puede considerarse como un autómata capaz de reconocer lenguajes formales. En ese sentido, es capaz de reconocer los lenguajes recursivamente enumerables, de acuerdo a la jerarquía de Chomsky. Su potencia es, por tanto, superior a otros tipos de autómatas, como el autómata finito, o el autómata con pila, o igual a otros modelos con la misma potencia computacional.
Máquina de Turing Cuántica
En 1985, Deutsch presentó el diseño de la primera Máquina cuántica basada en una máquina de Turing. Con este fin enunció una nueva variante la tesis de Church-Turing dando lugar al denominado "principio de Church-Turing-Deutsch".
La estructura de una máquina de Turing cuántica es muy similar a la de una máquina de Turing clásica. Está compuesta por los tres elementos clásicos: una cinta de memoria infinita en donde cada elemento es un qubit, un procesador finito y un cabezal.
El procesador contiene el juego de instrucciones que se aplica sobre el elemento de la cinta señalado por el cabezal. El resultado dependerá del qubit de la cinta y del estado del procesador. El procesador ejecuta una instrucción por unidad de tiempo.
La cinta de memoria es similar a la de una máquina de Turing tradicional. La única diferencia es que cada elemento de la cinta de la máquina cuántica es un qubit. El alfabeto de esta nueva máquina está formado por el espacio de valores del qubit. La posición del cabezal se representa con una variable entera.
