1 Alan Turing (1912-1954) Una pregunta acechaba a Turing, y era
el hecho de que: ¿Debe existir al menos en principio
algún método definido, o proceso mediante el cual
toda cuestión matemática pueda ser demostrada?
(entscheidugsproblem) Para contestar a esta pregunta necesitaba
una definición del concepto método, y para ello
analizó que era lo que hacía una persona para
transformar un proceso metódico, y buscar una forma de
hacer esto mecánicamente. Expresó el analisis en
términos de una máquina teórica que
sería capaz de transformar con precisión
operaciones elementales previamente definidas en símbolos
en una cinta de papel. En Agosto de 1936 presenta el concepto
final de la Maquina de Turing en su artículo On Computable
Numbers (1936). En este artículo determinó la
naturaleza y las limitaciones teóricas de las
máquinas lógicas antes de que se construyera
siquiera una sencilla computadora por completo programable
2 En Princeton, desarrolló una máquina de cifrado,
y estudió sobre este campo debido a la utilidad de ello en
la Guerra con Alemania. Trabajando secretamente para el Colegio
de Cifrado y Código Gubernamental o también llamado
Departamento de Criptoanálisis. Turing fue reclutado por
Inglaterra, en Bletchley Park, para descifrar los mensajes que
componía la máquina alemana Enigma, y, como
consecuencia, los aliados construyeron la máquina
Colossus. Es en este periodo cuando toma contacto con la
más avanzada tecnología electrónica de la
época y planea la Máquina de Turing Universal en su
forma electrónica, de hecho había inventado las
computadoras digitales.
3 En 1950, Turing publica el artículo Computing Machinery
and Intelligence en la revista Mind, en el que introducía
el célebre Test de Turing. Este artículo
estimuló a los pensadores sobre la filosofía e
investigación en el campo de la Inteligencia Artificial.
Turing tuvo la visión de una computadora con memoria que
implementaría las funciones aritméticas mediante
programación en vez de con componentes
electrónicos, y que podría desempeñar todo
tipo de tareas (por ejemplo, manejo de archivos, álgebra,
jugar ajedrez, encriptamiento, etc.) Hacia 1947, concibió
la idea de las redes de cómputo y el concepto de subrutina
y biblioteca de software. En vez de publicar los principios
fundamentales de cómputo que había descubierto, se
dedicó a estudiar fisiología y neurología, y
en un reporte interno del NLP (Laboratorio Nacional de
Física, Inglaterra) de esa época, describe las
ideas básicas de lo que hoy se conoce como una red
neuronal.
4 Test de Turing En 1950, Alan Turing publicó en la
revista Mind el artículo Computing Machinery and
Intelligence en el que introducía el concepto de Test de
Turing. Este artículo puede considerarse el precursor de
muchos de los desarrollos actuales en el campo de la Inteligencia
Artificial. El test consistía en juzgar el nivel de
inteligencia de una máquina. Se supone un juez situado en
una habitación, y una máquina y un ser humano en
otras. El juez debe descubrir cuál es el ser humano y
cuál es la máquina, estándoles a los dos
permitidos mentir al contestar por escrito las preguntas que el
juez les hiciera. La tesis de Turing es que si ambos jugadores
eran suficientemente hábiles, el juez no podría
distinguir quién era el ser humano y quién la
máquina.
5 ¿Qué es computabilidad? Consiste en ser capaz de
encontrar la representación adecuada para la
descripción de un problema o fenómeno. Para tal
representación es necesario: Un conjunto finito de
símbolos. Hacer asociaciones entre conceptos y elementos
del lenguaje (de símbolos) Encontrar las combinaciones
adecuadas de símbolos para evitar ambigüedad. Definir
una manera de confirmar tal descripción para que terceros
puedan reproducirla y llegar a los mismos resultados.
6 El concepto de modelo Modelo: es una especificación,
generalmente en términos de un lenguaje matemático,
de los pasos necesarios para reproducir un subconjunto
determinado de la realidad. La representación del modelo
surge siempre a partir de su descripción. ¿Es
posible siempre pasar de la descripción de un modelo a su
representación? ¿Todo lo que es descriptible puede
ser representable? Aparentemente la exactitud de la
descripción hace depender a la exactitud de la
representación. Existen procesos que pueden ser descritos
con gran exactitud, pero su representación o modelado no
es posible.
7 Teoría de la computabilidad La Teoría de la
Computabilidad consiste en encontrar maneras de representar
descripciones de procesos, de tal manera que se pueda asegurar si
existe o no una representación. Se dice que un algoritmo
es una manera formal y sistemática de representar la
descripción de un proceso.
8 La máquina de Turing* En el artículo On
Computable Numbers, Turing construyó un modelo formal de
computador, la Máquina de Turing, (con esto
resolvió el entscheidungsproblem (planteado por, David
Hilbert) y demostró que había problemas tales que
una máquina no podía resolver. La máquina de
Turing es el primer modelo teórico de lo que luego
sería un computador programable. Con el tiempo a este tipo
de máquina se la conoció como máquina de
estado finito, debido a que en cada etapa de un cálculo,
la siguiente acción de la máquina se contrastaba
con una lista finita de instrucciones de estado posibles. * La
“máquina” no se debe confundir con un aparato
físico. Se trata más bien de una
construcción matemática.
9 Componentes de la máquina de Turing Una cinta de
longitud infinita dividida en celdas (cada celda puede tener
solamente un símbolo tomado de un diccionario de
símbolos predefinido). Un control finito que tiene la
capacidad de examinar el algún símbolo de alguna
celda y tomar una decisión que depende del símbolo
observado y del estado en que se encuentre el control finito. El
control es finito porque puede estar solamente en alguno de los
estados posibles, habiendo solamente un número finito de
ellos. Se supone un diccionario de símbolos finto.
10 Se puede observar la cinta de longitud infinita, que en este
caso se encuentra en la primera celda de la cinta con el
símbolo S1. Se debe entender a la máquina como un
ser vivo que reacciona de maneras preestablecidas ante
estímulos provenientes del exterior (en este caso la
cinta). Un estímulo lo será si ocurren dos sucesos:
Que el control finito se encuentre en cierto estado E1 En la
celda actual existe un símbolo S1
11 Entonces la máquina reaccionará a este
estímulo que consistirá en: Pasará a un
nuevo estado (puede ser el mismo que tenía antes).
Escribirá un nuevo símbolo en el lugar
recién leído (puede ser el mismo que el anterior).
Moverá el control finito una celda a la derecha (D) o a la
izquierda (I).
MERG 12 Ejemplo de una MT La máquina tiene 7 estados. Los
estados finales son E5 y E6, el estado final es E0. Maneja 6
símbolos: 0,1,X,Y,Z,B El objetivo de este problema es
darse cuenta de que es posible programar la máquina para
que se comporte de tal forma que pueda lograr algún fin
previsto. Esto es la representación de algún
proceso que fue adecuadamente codificado en la máquina. El
resultado final de la máquina será un conjunto de
celdas que tendrán la solución encontrada.
13 Qué pasa en la siguiente cinta .
14 Al número le resta 1 0 1 1 1 D 0 0 2 0 D 1 0 2 0 D 1 1
1 1 D 1 _ 3 _ I 2 0 2 0 D 2 1 1 1 D 2 _ 3 _ I 3 0 3 1 I 3 1 F 0 I
Cinta 1 0 1 0 _ _ Complemento a 2 x _ 0 _ D x 1 0 0 D x 0 0 1 D 0
0 0 1 D 0 1 0 0 D 0 _ 1 _ I 1 0 F 1 D 1 1 1 0 I 1 _ F 1 D Cinta _
1 0 1 0 _ _
15 . Complemento a 2 0 _ 1 _ D 0 0 1 1 D 0 1 1 0 D 1 1 1 0 D 1 0
1 1 D 1 _ 2 _ I 2 0 F 1 I 2 1 2 0 I 2 _ F 1 I EdoI=0 EdoF=F
Cadenas: _ 0 1 1 0 1 0 _ _ Cuenta los unos I _ 0 _ D 0 0 0 0 D 0
1 1 0 D 0 _ F _ D 1 1 1 1 D 1 0 1 0 D 1 _ 2 _ D 2 1 2 1 D 2 _ 3 1
I 3 1 3 1 I 3 _ 4 _ I 4 0 4 0 I 4 1 4 1 I 4 _ 0 _ D Cinta ? _ 1 0
1 0 _ _ _ _ _ _ Inicio: I Fin: F