|
| |
Las máquinas de Turing fueron propuestas por primera vez por Alan Turing, en
un intento para dar una definición matemática precisa de algoritmo o
procedimiento mecánico. Los primeros trabajos de Turing y Alonzo Church abrieron
la rama de la lógica matemática, que eventualmente se convertiría en la Teoría
de Funciones Recursivas.
Una máquina de Turing es una representación abstracta de un dispositivo de
cómputo o informático. Consiste en una cabeza de lectura/escritura que examina
una dimensión posiblemente infinita de una cinta bidireccional dividida en
cuadros cada uno de los cuales está identificado con un 0 o un 1. El Cómputo
empieza con la máquina, en un estado dado, examinando un cuadrado. Borra lo que
encuentra allí, imprime un 0 o 1, se mueve a un cuadrado adyacente, y entra en
un nuevo estado. Esta conducta es completamente determinada por tres parámetros:
(1) el estado en que la máquina está, (2) el número en el cuadrado está
examinando, y (3) una tabla de instrucciones. La tabla de instrucciones
especifica, para cada estado y entrada binaria, lo que la máquina debe escribir,
en qué dirección se debe mover, y en qué estado debe entrar. (Por ejemplo, "Si
en Estado 1 examina un 0: imprima 1, se mueve a la izquierda, y entra en Estado
3".) La tabla puede enlistar únicamente estados finitos, cada uno de los cuales
se define implícitamente por el papel que juega en la tabla de instrucciones.
Estos estados están a menudo referidos como "estados funcionales" de la máquina.
Por consiguiente, una máquina de Turing es más como un programa de computadora
(software) que una computadora en sí (hardware). Cualquier máquina de Turing
dada puede comprenderse o implementarse en un número infinito de dispositivos
físicos de cómputo diferentes. Científicos de la computación y logistas han
mostrado que si las computadoras digitales convencionales son consideradas en
aislamiento de las entradas externas aleatorias (como un flujo de bits generado
por decaimiento radiactivo), entonces dado bastante tiempo y cinta, las máquinas
de Turing pueden computar cualquier función que cualquier computadora digital
convencional puede computar. (Nosotros no consideraremos si las máquinas de
Turing y las computadoras digitales modernas pueden ser equivalentes cuando a
las dos se les dan las entradas externas, dado que eso exigiría cambiar la
definición de la máquina de Turing.) También, un ‘atómata probabilístico' puede
definirse como una máquina de Turing en la que la transición de la entrada y
estado a la salida y estado toma lugar como una cierta probabilidad (Por ejemplo
"Si en Estado 1 se examina un 0: (a) hay un 60% probabilidad que la máquina
imprimirá 1, se moverá a la izquierda, y entra en Estado 3, y (b) hay un 40% de
probabilidad que la máquina imprimirá 0, se moverá a la izquierda, y entrará en
Estado 2".)
[634] [635]
| |
Un miembro de
The History Of Computing Foundation
El motor de búsqueda de texto permite formar consultas a partir de
expresiones lógicas que contengan las palabras clave AND, OR y NOT, o varias de
ellas agrupadas con paréntesis. Por ejemplo:
información recuperación
busca documentos que contengan 'información' o 'recuperación'. Una o ambas
palabras.
información or recuperación
igual que en el caso anterior
información and recuperación
busca documentos que contengan 'información' y 'recuperación'. Exclusivamente
ambas palabras.
información not recuperación
busca documentos que contengan 'información' pero no 'recuperación'
(información not recuperación) and WAIS
busca documentos que contengan 'WAIS' e 'información' pero no 'recuperación'
web*
busca documentos que contengan palabras que empiecen por 'web
|
