TEST DE TURING

CONCEPTO

El Test de Turing nace como un método para determinar si una máquina puede pensar. Su desarrollo se basa en el juego de imitación.

La idea original es tener tres personas, un interrogador, un hombre y una mujer. El interrogador está apartado de los otros dos, y sólo puede comunicarse con ellos escribiendo en un lenguaje que todos entiendan. El objetivo del interrogador es descubrir quién es la mujer y quien es el hombre, mientras que el de los otros dos es convencer al interrogador de que son la mujer.

1.PNG

La variante introducida por Turing consiste en sustituir a uno de los interrogados por un ordenador. Se pueden dar dos casos, que se sustituya al hombre, con lo cual sólo el ordenador tendría que aparentar ser una mujer, o que se sustituya a la mujer, con lo cual tanto el hombre como el ordenador estarían imitando. Aunque esta última opción podría ser un experimento interesante, no se intenta comprobar la habilidad de imitar a una mujer, así Turing cambia el objetivo de conocer el sexo por el de reconocer la máquina. La finalidad de estos cambios es hacer el juego lo más justo posible. Lo primero, es que no tiene que consistir en un concurso de engaños, por lo que uno de los implicados no tendría por qué aparentar ser otra cosa. Otro detalle es que a Turing poco le importa si el ordenador emplea trucos preestablecidos para eludir o manipular las respuestas (por ejemplo, equivocándose en preguntas aritméticas o tardando más tiempo del necesario en responderlas). Supone que el interrogador también les empleará para reconocerle, así que lo importante es lo que resulta del juego, no los métodos que se emplean para jugar ni los mecanismos internos de razonamiento, que, entre otras cosas, también son desconocidos en el ser humano.

Una máquina podría pasar el test de Turing cuando el interrogador no lograra reconocerlo en un número significativo de ocasiones.

OBJECIONES

Nada más aparecer el Test de Turing, también salen a la luz las primeras críticas. La mayoría de ellas estaban basadas en temas éticos y religiosos, y muchas de las posiciones más críticas venían de personas que consideraban que el ser humano era muy especial y que ninguna máquina podría ni siquiera acercarse a las capacidades de este.

Una de las primeras objeciones es matemática. El teorema de Gödel afirma que en un sistema lógico con la suficiente potencia se pueden crear frases que no pueden ser ni probadas ni refutadas dentro de él. Sin embargo, Turing afirma que de los errores o confusiones tampoco está libre la mente humana, y esto merma la capacidad intelectual.

Otra dificultad es la falta de conciencia. Se afirmaba que para que una máquina fuera mentalmente activa debería tener conciencia, tanto de sí misma como de los demás, y generar sentimientos positivos o negativos sobre la información que le llega o las acciones que realiza. El solipsismo es una radicalización de esta idea, que sostiene que la única manera de saber si una máquina piensa es ser esa máquina. El problema es que, siguiendo esta idea, la única manera de saber si otro ser humano piensa es ser ese ser humano, lo que se conoce como el problema de las otras mentes. Turing afirma que, si entre los seres humanos se considera políticamente correcto obviar el solipsismo, también debería hacerse con las máquinas. Y cómo la única forma de resolver el problema de la falta de conciencia es el solipsismo, lo más adecuado es que tampoco se considere.

Con la objeción de Lady Lovelace se quiere mostrar la idea de que las máquinas nunca podrían generar nada nuevo, sorprendente o distinto. Como dice Turing (y como cualquiera que haya utilizado, por ejemplo, un programa de cálculo estructural o simplemente conocidos sistemas operativos de ventanas, podría ratificar), el ordenador, siendo una máquina, puede sorprender continuamente. Aunque esto no puede considerarse como un proceso mental creativo, puede que la creatividad se realice en la mente del observador, y no en el generador. Por ejemplo, tanto puede sorprender un libro como una persona o un coche.

Al problema de que la máquina sea un sistema discreto mientras que la mente humana un sistema continuo (problema de la continuidad del sistema nervioso), Turing responde que cualquier sistema continuo se puede discretizar con suficientes recursos de forma que no se note la diferencia entre uno y otro.

Para finalizar, se puede hablar del problema de la informalidad de la personalidad. El comportamiento humano no puede describirse con un conjunto de reglas útiles en cualquier situación. La respuesta de Turing consiste en que hay diferencias entre reglas de conducta (por ejemplo, con el semáforo en rojo, pare) y reglas de actuación. Las reglas de conducta pueden enumerarse, pero no las de actuación, porque, entre otras cosas, muchas se desconocen. Pero Turing también afirma que aún con unas pocas reglas de actuación en un sistema discreto las respuestas pueden ser totalmente inesperadas y distintas, de forma que, al igual que en un ser humano, no se pueden preveer.

LAS PREDICCIONES DE TURING

El artículo de Turing recoge muchos comentarios audaces sobre las posibilidades de la inteligencia de las máquinas, que en aquel momento muchas parecían de ciencia ficción. Turing creía a los computadores capaces de desarrollar tareas humanas y de un modo humano, que las dificultades de diseñar máquinas pensantes eran principalmente de programación y que las “proezas” que él esperaba de las máquinas serían realizables en un futuro previsible (como ajustar su propio programa o predecir el efecto de alteraciones en su propia estructura).

Lo que en 1950, en términos de velocidad y capacidad en ordenadores era inimaginable, es ahora realidad. Sin embargo, las predicciones de Turing sobre máquinas y el Juego de Imitación, son todavía un desafío (Turing pensó que en unos 50 años habría máquinas que “jugarían” tan bien al Juego de Imitación que un interrogador no tendría una probabilidad mayor al 70 % de realizar la adecuada identificación tras cinco minutos de cuestiones)

DEL JUEGO DE IMITACIÓN AL TEST DE TURING.

AÑOS 1960 Y 1970.

Las primeras alusiones al Test de Turing (TT) fueron mayoritariamente filosóficas.

  1. Comentarios de Keith Gunderson

En su artículo “The Imitation Game” (1964, Mind) enfatiza dos puntos:

Cree que jugar al Juego de Imitación con éxito es un fin que puede ser alcanzado a través de diversos medios y particularmente, sin poseer inteligencia.

Sostiene que pensar es un concepto general y que jugar al Juego de Imitación no es sino un ejemplo de lo que las entidades pensantes pueden hacer

Los dos puntos son claramente críticos con la validez del Juego de Imitación como una medida de la inteligencia.

  1. Réplicas de John G. Stevenson

Lanza varios argumentos contra Gunderson en su artículo “On The Imitation Game” (1976). Una de estas objeciones es que para Gunderson el hecho de ser capaz de jugar al Juego de Imitación es simplemente un ejemplo, cuando no es así, ya que una máquina buena en dicho juego es capaz de hacer cosas impresionantes, dice, aunque no las haga de forma tan exhaustiva como en pensamiento humano.

  1. El Test de Turing como Ciencia Ficción.

Richard Purtill publica en 1971 un artículo en Mind, “Beating The Imitation Game” donde critica ideas de Turing. Piensa que el juego es interesante, pero como parte de la ciencia ficción. Encuentra que es inimaginable construir en un futuro previsible una máquina que juegue al Juego de Imitación, que es un sueño humano. Manifiesta que si algún día las máquinas se comportan como en la ciencia ficción, asentirá que piensan. Los ordenadores no son capaces de “jugar” exitosamente porque, para él, el comportamiento de los seres pensantes no es determinista y no puede ser explicado en términos puramente mecánicos.

Geoffrey Sampson ataca brevemente los argumentos de Purtill en “In Defence Of Turing”. Cree que el comportamiento de los computadores es determinista porque están diseñados por humanos, quienes tienen herramientas que les permiten estudiar cómo se comportan.

AÑOS 1980 Y 1990.

La Habitación China

A principios de los 80 John Searle propone un ejemplo:

Una persona que no sabe ni una palabra de chino es encerrada en una habitación.

Hay una apertura en el cuarto a través de la cual pasamos hojas de papel que contienen frases en chino, que para la persona, son garabatos sin significado. Pero tiene en la habitación un “Libro de Chuletas para el Test de Turing Chino”, de manera que al enviarle un escrito, consulta el libro y puede dar como respuesta cierta secuencia de símbolos chinos, cuyo significado, por supuesto, desconoce. Para la gente de fuera de la habitación parecía que la persona encerrada en la habitación entiende chino perfectamente, pero no es así. Estaría pasando el Test de Turing Chino sin saber nada de dicho idioma. Esto es claramente una crítica al TT y a la visión computacional de la mente.

AUTÓMATA FINITO

Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.

Este modelo está conformado por:

  • Un alfabeto
  • Un conjunto de estados finito
  • Una función de transición
  • Un estado inicial
  • Un conjunto de estados finales

Su funcionamiento se basa en una función de transición, que recibe a partir de un estado inicial una cadena de caracteres pertenecientes al alfabeto (la entrada), y que va leyendo dicha cadena a medida que el autómata se desplaza de un estado a otro, para finalmente detenerse en un estado final o de aceptación, que representa la salida.

La finalidad de los autómatas finitos es la de reconocer lenguajes regulares, que corresponden a los lenguajes formales más simples según la Jerarquía de Chomsky.

Formalmente, un autómata finito es una 5-tupla (Q, Σ, q0, δ, F) donde:

Q es un conjunto finito de estados;

Σ es un alfabeto finito;

q0 E Q es el estado inicial;

δ: Q x Σ → Q es una función de transición;

F (perteneciente a Q) conjunto de estados finales o de aceptación.

AUTÓMATA FINITO DETERMINISTA

Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre no más de una transición posible desde ese estado y con ese símbolo.

Es decir, para cada estado q ∈ Q en que se encuentre el autómata, y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).

En un AFD no pueden darse ninguno de estos dos casos:

Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;

Que existan transiciones del tipo δ(q, ε), salvo que q sea un estado final, sin transiciones hacia otros estados.

AUTÓMATA FINITO NO DETERMINISTA

Un autómata finito no determinista (abreviado AFND) es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible. Es el autómata finito que tiene transiciones vacías o que por cada símbolo desde un estado de origen se llega a más de un estado destino.

En un AFND puede darse cualquiera de estos dos casos:

Que existan transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1 ≠ q2;

Que existan transiciones del tipo δ(q, ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada.

LENGUAJE REGULAR

Son los lenguajes formales más simples, con los mecanismos de representación y reconocimiento más estudiados. Su aplicación práctica en la teoría y construcción de intérpretes y compiladores de lenguajes de programación o de especificación o formato de información, especialmente como microcomponentes del analizador lexicográfico que detecta los tókenes como constantes numéricas, cadenas de texto, operadores, palabras reservadas (keywords), separadores, etc. Pero también se puede apreciar su uso en máquinas expendedoras, teléfonos públicos, calculadoras y otros artefactos electromecánicos.

Se dice que un lenguaje es regular si y sólo si se cumple cualquiera de las siguientes proposiciones:

  • Tiene al menos una gramática regular G que lo produce.
  • Puede ser reconocido por un autómata finito A.
  • Existe una expresión regular Er que representa a todas las cadenas de L.

IMPORTANCIA DE LOS LENGUAJES REGULARES

La existencia y formalización de los lenguajes regulares (LR) y su vinculación con otros artefactos lingüísticos-matemáticos ya bien formalizados, estudiados e incluso llevados a la práctica ha sido de vital importancia en el ulterior desarrollo de los mecanismos de procesamiento de lenguajes de computadora, fundamentalmente en los analizadores lexicográficos gracias a la posibilidad de derivar el reconocimiento de los LR mediante autómatas finitos que son fáciles de implementar computacionalmente con mecanismos simples y rápidos, óptimos en la obtención de parsers veloces y robustos que a su vez le ofrecen a los desarrolladores información detallada de los errores léxicos, sintácticos e incluso advierten sobre errores semánticos.

Lo mismo sucede por ejemplo con las expresiones regulares implementadas ya en muchos Lenguaje de programación de propósito general modernos que permiten a los desarrolladores de lenguajes mecanismos muy eficientes para la obtención intuitiva de partes de compiladores que reconocen los tókenes o partículas lexicales del código fuente como fase del proceso completo de interpretación o compilado, según sea el caso.

HISTORIA DE LA TEORÍA DE AUTÓMATAS

Los modelos abstractos de computación tienen su origen en los años 30, bastante antes de que existieran los ordenadores modernos, en el trabajo de los lógicos Church, Gödel, Kleene, Post, y Turing.

Estos primeros trabajos han tenido una profunda influencia no solo en el desarrollo teórico de las Ciencias Computacionales., sino que muchos aspectos de la práctica de la computación que son ahora lugar común de los informáticos, fueron presagiados por ellos; incluyendo la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software y hardware, y la representación de lenguajes por estructuras formales basados en reglas de producción.

El punto de partida de estos primeros trabajos fueron las cuestiones fundamentales que D. Hilbert formuló en 1928, durante el transcurso de un congreso internacional:

1.- ¿Son completas las matemáticas, en el sentido de que pueda probarse o no cada aseveración matemática?

2.- ¿Son las matemáticas consistentes, en el sentido de que no pueda probarse simultaneamente una aseveración y su negación?

3.- ¿Son las matemáticas decidibles, en el sentido de que exista un método definido que se pueda aplicar a cualquier aseveración matemática, y que determine si dicha aseveración es cierta?

Por desgracia para Hilbert, en la década de 1930 se produjeron una serie de investigaciones que mostraron que esto no era posible. Las primeras noticias en contra surgen en 1931 con K. Gödel y su Teorema de Incompletitud: “Todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de (números de Gödel de) axiomas sea recursivo no es completo.”

El siguiente paso importante lo constituye la aparición casi simultanea en 1936 de varias caracterizaciones independientes de la noción de calculabilidad efectiva, en los trabajos de Church, Kleene, Turing y Post. Los tres primeros mostraban problemas que eran efectivamente indecidibles; Church y Turing probaron además que el Entscheidungsproblem era un problema indecidible.

Cuando Turing conoció los trabajos de Church-Kleene, demostró que los conceptos de función λ-definible y función calculable por medio de una máquina de Turing coinciden. Naturalmente a la luz de esto la Tesis de Turing resulta ser equivalente a la de Church.

Posteriormente, se demostró la equivalencia entre lo que se podía calcular mediante una máquina de Turing y lo que se podía calcular mediante un sistema formal en general. A la vista de estos resultados, la Tesis de Church-Turing es aceptada como un axioma en la teoría de la computación, y ha servido como punto de partida en la investigación de los problemas que se pueden resolver mediante un algoritmo.

LIBRO RECOMENDADO: AUTÓMATAS Y LENGUAJES: UN ENFOQUE DE DISEÑO (RAMON F. BRENA PINERO)

Documento útil para entender Teoría de Autómatas.

La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capaces de reconocer.

Un autómata es un modelo matemático para una máquina de estado finito (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos, “salta” a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). En la variedad común “Mealy” de FSMs, esta función de transición dice al autómata a qué estado cambiar dados unos determinados estado y símbolo.

La entrada es leída símbolo por símbolo, hasta que es “consumida” completamente (piense en ésta como una cinta con una palabra escrita en ella, que es leída por una cabeza lectora del autómata; la cabeza se mueve a lo largo de la cinta, leyendo un símbolo a la vez) una vez la entrada se ha agotado, el autómata se detiene.

Dependiendo del estado en el que el autómata finaliza se dice que este ha aceptado o rechazado la entrada. Si éste termina en el estado “acepta”, el autómata acepta la palabra. Si lo hace en el estado “rechaza”, el autómata rechazó la palabra, el conjunto de todas las palabras aceptadas por el autómata constituyen el lenguaje aceptado por el mismo.

https://drive.google.com/open?id=0B4AoAxhlob6VdF9MUWxaUHVWVDg

AyLPortada.png