revista de cultura científica FACULTAD DE CIENCIAS, UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO
Busca ampliar la cultura científica de la población, difundir información y hacer de la ciencia
un instrumento para el análisis de la realidad, con diversos puntos de vista desde la ciencia.
R09Articulo1   menu2
PDF
   
   
Elisa Viso Gurovich      
               
               

Un campo rico en conocimientos, intereses, problemas y juegos de intelecto

 

El legado de utilización de las computadoras se ha incrementado muchísimo de un tiempo para acá y ya no resulta necesario convencer a la gente se acerque a estas máquinas maravillosas a que les resuelvan sus problemas o simplemente para entretenerse. Aún aquellos con muchísimos años de trabajo en el área computacional no dejan de sorprenderse ante las tareas tan variadas y “asombrosas” que logran realizar las máquinas.

El que no es mérito de las computadoras realizar tan diversas labores, sino de los “programadores” que les indican cómo llevar a cabo las tareas encomendadas, resulta ser algo que continuamente se repite. En estas líneas se tratará de justificar —si se me permite decirlo— el por qué la labor de programar computadoras y, en general, lo relacionado con computación, se siente siempre tan ligado a las matemáticas.

Cuando decimos que vamos a programar una computadora para que realice una tarea, sea ésta un juego, un cálculo, una gráfica, u otro caso, partimos del conocimiento de qué es lo que queremos hacer y qué obtener como resultado de tal fase del programa. Hasta este punto, la tarea puede ser planteada en cualquier terreno, ya sea éste científico, humanístico, artístico, etc. El siguiente paso es proponer el método de solución que consideremos idóneo para realizarla y es ahí donde las cosas empiezas a ponerse más difíciles.

Si se trata de dibujar una gráfica, cualquiera de los lectores puede dar un método de solución que, por ejemplo, sería algo del siguiente estilo:

1. Especifica para cuáles y cuántos valores de x quieres la gráfica.

2. Calcula, para cada una de las x’s el valor de la función.

3. En una hoja cuadriculada, dibuja los ejes cartesianos.

4. Para cada valor de x y de f (x), dibuja un punto en el plano.

5. Une entre sí cada pareja de puntos consecutivos sobre el eje x mediante una recta.

En este caso nuestro método de solución es preciso, claro (para aquellos que pasaron ya por secundaria), presenta un número finito de pasos y estamos seguros que la persona encargada va a concluirlo (¿esto último es cierto?). Tenemos lo que se conoce como un algoritmo. El término algoritmo no está tan íntimamente ligado a las computadoras como pudiéramos creerlo. En la Edad Media ya se hablaba de algoritmos y se refería a la realización de operaciones a mano opuesto a usar un ábaco (estaba implícito en este proceso la repetición de un conjunto de operaciones básicas y reglas). En los años treinta, con la Teoría de Computabilidad se precisó más el término exigiéndole al método de solución que cumpla con:

1. Tener un número finito de pasos (estar especificado en forma finita).

2. Cada paso del proceso debe estar claramente dado y en principio poder ser llevado a cabo por una persona que cuente con papel y lápiz en un tiempo finito.

3. El proceso se puede garantizar que termina.

4. El proceso trabaja con cero o más datos (puede ser que siempre que se ejecute produzca exactamente el mismo resultado).

5. El proceso produce uno o más resultados.

La gente dedicada a la computación parecemos engolosinados con el término algoritmo. Lo mandamos por delante en casi cada oportunidad en la que se menciona a la computación. Este engolosinamiento sin embargo, no es gratuito.

El primer paso a dar si queremos que una computadora realice una tarea, consiste en poder expresarla como un algoritmo. Hay problemas para los cuales no se puede dar un algoritmo para encontrar la solución. Por ejemplo, no es posible dar un algoritmo que, si cualquier persona lo sigue, realice la tarea de producir un cuadro con la creatividad de un gran pintor. Pero éste es un ejemplo demasiado traillado, tampoco podemos dar un algoritmo para decidir si hay 4”5’s seguidos de la expansión de Pi. Cualquier método de solución que yo diera, terminaría en cuanto encontrara los 4”5’s, pero si estos no están, y dado que la expansión de Pi es infinita, nunca pararía pues siempre esperaría a encontrarlos “un poco más allá”.

Siendo los matemáticos individuos a quienes les encanta “jugar”, vemos ya que la Teoría de Algoritmos es una fuente inagotable de juegos y divertimentos para los matemáticos, preguntas tales como: ¿existe un algoritmo que realice ______? ¿Existe un algoritmo mejor para ______?

 
En años recientes se ha desarrollado la computación con dispositivos ópticos. La precisión es relativamente baja, pero en contrapartida las tareas encomendadas se realizan con extrema rapidez.

Es en el área de Computabilidad donde ubicamos a la primera pregunta. Relacionados con ella tenemos, en Computación, la Teoría de Autómatas y Lenguajes Formales dedicada a diseñar máquinas teóricas (modelos matemáticos) computadoras (que puedan hacer cómputos sencillos) para poder dar, a priori, las limitaciones y alcances de estas máquinas. Aquí también se definen las caracterizaciones matemáticas de las tareas que queremos realizar (sumar dos números, traducir un lenguaje de programación, simular un equipo) y los algoritmos para que, dada las caracterizaciones, sea inmediata la construcción de la máquina (real o virtual) que realice esas tareas. Entendemos por una máquina virtual a un programa de computadora que se comporta como si fuera una determinada máquina, aún cuando no podamos tocar sus componentes físicos. Cuando se logra que una máquina real se comporte como otra máquina decimos que la primera está simulando a la segunda.

Los problemas de simulación son mucho muy interesante y han acaparado la atención de los programadores casi desde el inicio de las máquinas y los programas. Entre los problemas de este tipo podemos citar el tratar de reproducir el comportamiento de una galaxia, el funcionamiento de una máquina, la descripción de la forma de atención a clientes en un banco, el funcionamiento de un avión durante un vuelo. En esta forma de aplicaciones se basan, por ejemplo, todos los juegos que presentan una pantalla en la cual están sucediendo varias cosas al mismo tiempo.

En simulación lo importante es “predecir” o “describir” el comportamiento de un sistema, tomando sistema en el sentido de diversas componentes interrelacionadas. Si logramos describir y predecir el comportamiento de un sistema, programarlo en la computadora resulta ser el paso más sencillo. Esta descripción es en términos matemáticos, con funciones, sistemas de ecuaciones, estadística, etc. La gran aportación de la computadora para simular o modelar, consiste en que logra realizar las operaciones lo suficientemente rápido como para que parezca que el tiempo no transcurre y la posibilidad de tener a más de un componente del sistema “funcionando” al mismo tiempo. Este tipo de mediciones era casi imposible antes del advenimiento de las computadoras. Sin embargo, las distintas relaciones entre los componentes del sistema y las funciones que lo rigen son —y han sido siempre— preocupación de los matemáticos, en interacción con especialistas de las distintas áreas del conocimiento que se pretende modelar. Para obtener un buen modelo se necesita, entonces, el conocimiento profundo del sistema que se desea modelar, las matemáticas necesarias para poder describir el sistema y la capacidad de un programador que plasme esta descripción matemática en un programa para la computadora.

 
¿Un sueño irrealizable?: los robots pensantes. Desde su origen el hombre ha planeado todas las actividades de las máquinas electrónicas.

Hay sistemas, sin embargo, que no pueden ser descritos tan precisamente como para poder dar un algoritmo que lo simule. Tal es, por ejemplo, el proceso de aprendizaje o la simplificación de fórmulas algebraicas. En estos casos, el individuo que desea atacar el problema cuenta únicamente con “sugerencias” de cómo funciona el sistema y distintas posibles respuestas ante varias de las preguntas. En estas circunstancias se plantean métodos de solución heurísticos. Un método de solución de este tipo da, en la mayoría de los casos, la respuesta más adecuada, pero sin garantizar que en todos ellos esa sea la mejor respuesta. El problema de simplificación de fórmulas donde la persona que quiere simplificar sencillamente se pone a probar alternativas, es un ejemplo del uso de programación heurística. El campo de Inteligencia Artificial también utiliza típicamente programación heurística.

Otro caso en el que se utiliza la programación heurística es cuando sí tenemos la “fórmula” para obtener el mejor resultado, pero calcular uno de los valores se lleva tanto tiempo o requiere tanto “papel” que desistimos aún antes de empezar. Tal es, por ejemplo, un juego de ajedrez. En este juego el número de posibles respuestas ante una jugada es finito, por lo que en teoría, la computadora podría elegir la mejor jugada con tan sólo evaluar las distintas posibilidades. Sin embargo, en la práctica esto no es aconsejable y se ha elegido mejor el tratar de imitar el juego de un experto, quien lo primero que hace es desechar —en base a su experiencia— un gran número de jugadas posibles. Es en esa “experiencia” donde se aplica la heurística.

Es conveniente diferenciar entre los dos casos anteriores: aquél en el que se opta por una heurística porque no hay algoritmo (no se puede, por ejemplo, especificar claramente cada medida o paso) y aquél en el que el tiempo que va a tardar el algoritmo en proporcionar una respuesta se considera “demasiado”. El primero de ellos —como ya lo dijimos—, cae en el área de Computabilidad la cual está muy relacionada con Lógica Matemática.

El segundo es estudiado por el área de Complejidad: dado un algoritmo se puede decir qué tan complejo es, cuánto va a tardar en ejecutarse. Por supuesto que en la mayoría de los casos la complejidad de un algoritmo es función del número de datos que maneja.

Es interesante, entonces, comparar distintos algoritmos para realizar la misma tarea, como pudiera ser el ordenar una lista de nombres. Hay varias tareas matemáticas involucradas en un proceso de este tipo. Primero, dado el algoritmo debemos demostrar que el algoritmo trabaja, esto es, que produce el resultado que deseamos si le damos los datos que especifica. Estas demostraciones se hacen matemáticamente: por inducción, reducción al absurdo, etc. Segundo, una vez que tenemos un algoritmo que ejecuta lo que queremos hacer, deseamos “medirlo”, para ello, un buen manejo de series y sucesiones en los enteros resulta ser imprescindible. Al medir un algoritmo se trata de determinar la función que va a describir, el tiempo que se va a tardar el algoritmo como función y al menos, denotar el número de datos. Y ya estamos otra vez en Matemáticas.

Muchos de los lectores estarán pensado: “pero si yo he programado y nunca he medido mis algoritmos. Además, he demostrado que funcionan probándolos con distintos juegos de datos y si no ‘truena’ el programa lo doy por bueno”. Esto es cierto en un gran número de casos. Si lo que yo deseo hacer es un programa pequeño que va a trabajar dos o tres veces para mí y en el que tengo muy controlados los datos, no hay necesidad real de demostrar el programa o de buscar el algoritmo más eficiente. Sin embargo, es típico el caso del diseño de programas que en las pruebas de este tipo funcionan muy bien y al meterlo a producción el programa aborta o simplemente se tarda eternidades. Si el programador hubiera tenido una idea de la complejidad del algoritmo que eligió (o diseñó) hubiera podido predecir qué tanto crecería el tiempo al aumentar el número de datos. Por supuesto que si su algoritmo hubiera estado demostrado, no hubiera abortado bajo ningún caso. A esto último se le llama Verificación de Programas y es un área que cada vez adquiere más importancia.

 He estado hablando únicamente de “Computación para Computación” o dicho en otras palabras, cómo nos divertimos los matemáticos cuando nuestro objetivo de estudio son los algoritmos, programas o, en general, problemas y métodos de solución de los mismos. Pero hay muchísimas áreas de “Computación para…” y de “… para Computación”. Las primeras ya las conocemos: en general la programación es utilizada en casi cualquier disciplina de hoy en día. Un área de la computación que ha tomado muchísima importancia es la de Bases de Datos. Casi todos los problemas que se plantean, como el llevar historiales médicos, manejar una biblioteca, estados de cuenta, etc., están relacionados con Bases de Datos. Una Base de Datos es un conjunto de datos agrupados en registros. Los registros comparten entre sí una o más características, como puede ser la de describir a un mismo tipo de objeto, ocupar la misma cantidad de espacio y contener al menos cierta información respecto al objeto. Además, los registros están relacionados entre sí de algún modo que generalmente es el de estar ordenados respecto a uno de sus campos de información. Los Sistemas de Bases de Datos trabajan con conjuntos de registros de información y son capaces de, entre otras cosas, extraer subconjuntos, unir, intersectar y complementar conjuntos, obteniendo de ellos nuevos conjuntos que cumplen con poseer cierto tipo de información.

Se ha conformado toda un área en Computación bajo esta denominación, mientras que hasta hace algunos años simplemente se hacían programas especiales para cada aplicación, lo que tornaba muy lento el desarrollo de cualquier sistema de este tipo en el área denominada de Sistemas de Información. Hoy en día, se cuenta con los Sistemas Manejadores de Bases de Datos. Las operaciones que se realizan con una Base de Datos (o con un Sistema de Información) contempla el listar (extraer) de entre los registros subconjuntos restringidos, reordenar respecto a algún otro campo, combinar distintos conjuntos, listar con un cierto formato, etc. Hoy en día se contempla un Sistema de Bases de Datos como pudiendo tener, entre sus operaciones primitivas, muchas de las que acabamos de citar.

 
La simulación visual ha sido ampliamente utilizada en la preparación de pilotos, con una computadora son reproducidas todas las condiciones físicas de vuelo, así como las imágenes que se observan desde la cabina de un avión.

 También acá para diseñar esta forma de sistemas se hizo uso de las matemáticas. Se describieron modelos, conjuntos de datos, relaciones posibles entre los conjuntos y subconjuntos, transformaciones, etc. Para usar una Base de Datos tal vez no se necesite manejar toda esa información, igual que para sacar raíz cuadrada con una calculadora no es necesario que el dueño de la calculadora sepa sacar raíz cuadrada. Sin embargo, para comprender realmente cómo funciona un sistema de bases de datos o poder diseñar uno, es necesario entender los conceptos matemáticos subyacentes.

Cuando hablamos de “Computación para Química” por ejemplo, estamos hablando fundamentalmente de simulación de procesos químicos. Por supuesto que se debe entender el proceso y poder establecer las ecuaciones que describen al proceso: ¡otra vez matemáticas!

 Veamos el caso más sencillo en el que puedo pensar: manejar una cuenta de cheques. Me van a decir que en este caso las matemáticas requeridas por el programador son mínimas. Si bien esto es cierto, el programador de tal aplicación o de cualquier otra debe tener siempre un pensamiento ordenado. Ha de entender qué es primero y qué es después: en Matemáticas esto se podría traducir como entender cuál es el dominio de su aplicación, cuál es el rango y, sobre todo, si su programa es o no una composición de funciones donde se van creando nuevos dominios y nuevos rangos. A final de cuentas un programa, cualquiera que sea su objetivo, es una función que transforma un conjunto de datos en un conjunto de resultados. Que “calcula” resultados a partir de datos.

Pero hablemos no de las áreas en las que se utiliza la computación como herramienta, sino de aquéllas que por sus objetos de estudio resultan ligadas a la Computación. La Lingüística es la primera que me viene a la mente. La teoría de Lenguajes Formales ha aportado a la Lingüística interesantes enfoques para el tratamiento del lenguaje. Por ejemplo, el lingüista Noam Chomsky propuso en 1959 todo un enfoque matemático para la descripción de lenguajes que es hoy día, materia de estudio en Lingüística.

 
Las computadoras funcionan con base en componentes electrónicos que tienen dos posibles estados: prendido y apagado.

El uso de la Inteligencia Artificial para tratar de describir adecuadamente el proceso de aprendizaje ha aportado a la psicología al menos de enfoques distintos y novedosos respecto a cómo se adquiere el conocimiento, qué es innato y qué no y cuales aspectos forman parte del contexto mental de conocimiento en el que se desarrolla un individuo.

Respecto a las áreas que apoyan a la Computación podemos citar fundamentalmente el área de Electrónica y Comunicaciones que permiten la construcción de máquinas reales en las cuales llevar a cabo todos nuestros juegos. A mi siempre me parece importante mencionar que la Computación ha hecho uso de avances importantes en Electrónico aún cuando estos avances no estuvieran motivados por la Computación, sino por muy diversas causas, como el colocar un cohete en la Luna, hacer un cierto equipo médico, etc. Es mi convicción que si la Electrónica dirigiera a la industria de la Computación, iría más avanzada de lo que va. La industria electrónica y de comunicaciones todavía le lleva una buena delantera a la Computación.

 Si no reconociéramos lo mucho de matemáticas que hay en electrónica o en comunicaciones, todavía nos quedarían matemáticas cuando estamos utilizando una máquina real para colocar en ella un algoritmo y que este algoritmo haga que se ejecuten ciertas operaciones en la máquina. Las computadoras funcionan en su mayoría a base de componentes electrónicos que tienen dos posibles estados: prendido y apagado. Se toman grupos de componentes de este tipo y “codificamos” en estos grupos las distintas operaciones, números, letras, etc., que queremos representar. Y otra vez estamos en matemáticas cuando tenemos que decir cuántas letras distintas puedo representar con grupos de seis y ocho bits, por ejemplo (las permutaciones de dos símbolos tomados de 6 en 6) o cuando decidimos cómo representar números, o describimos qué hace determinada operación de la máquina; o en su caso me entero que las direcciones del lenguaje de máquina son en base ocho o en base dieciséis y tengo que empezar a convertir para ver, en decimal, de qué dirección se trata.

Claro que, otra vez, si todo lo que se quiere hacer es programar cosas sencillas para ser utilizadas exclusivamente por uno mismo, probablemente se puede vivir desconociendo o ignorando todas estas cosas y manteniendo divorciada a la Computación de las Matemáticas. Pero, enmarcada la Computación en Matemáticas, resulta ser un campo muy rico en conocimientos, intereses, problemas y juegos del intelecto, todos ellos lugares comunes en Matemáticas. Por otro lado, es válido afirmar: se enriquece la Computación misma con todo aquello que en Matemáticas son herramientas comunes.

AUTOMATAS Y LENGUAJES FORMALES

El área de Autómatas y Lenguajes Formales está hoy en día muy ligado a la Computación. Como su nombre lo indica tenemos dos aspectos involucrados. Por un lado está lo de autómatas, que contra lo que pudiéramos suponer, no tiene nada que ver con robots, sino con máquinas dotadas de la posibilidad para trabajar “automáticamente” y, por otra parte, de Lenguajes Formales, opuesto este término al de lenguajes “naturales”, los cuales son utilizados por la gente para comunicarse. Abordemos primero este último tema.

En los años posteriores a la Segunda Guerra Mundial surgieron muchísimas inquietudes respecto a si era posible o no realizar una traducción automática de un idioma a otro. Ya durante la guerra este interés se presentó al querer tener una codificación automática de mensajes cifrados. Durante los años cincuenta entre los psicólogos y los lingüistas se llevaron a cabo discusiones respecto a cuáles son los mecanismos que posee la mente humana para reconocer y generar frases correctas de un lenguaje dado. En esos momentos existían (y todavía existen) varias hipótesis siendo una de ellas que la mente humana le era factible recordar, eran patrones y reglas generales para reconocer frases correctas o construir nuevas. En estos años se desarrollaron esfuerzos importantes para determinar cuáles son los mecanismos de generación del lenguaje.

 
El uso de las computadoras en el campo de las artes se ha extendido enormemente. ¿Será que ya trabajan en sus micros los futuros Picassos y Dalíes?

De cualquier forma que esto se dio requirió de una interacción muy fuerte entre los lingüistas, psicólogos y matemáticos sometidos a un esfuerzo para expresar matemáticamente lo que correspondería al lenguaje natural. El trabajo de los matemáticos debería consistir en formular un modelo matemático susceptible de ser automatizado, para la descripción de los distintos lenguajes y los mecanismos inherentes en la producción de construcciones válidas en el lenguaje dado. El trabajo de los lingüistas debería ser el de experimentar y criticar los modelos expuestos para ver si, en efecto, lograban plasmar las posibilidades de un idioma en un modelo matemático. En estos momentos es que surgió el área de Lenguajes Formales, queriendo describir en el nombre el que se trata de una formalización de los lenguajes naturales.

Una vea que se lograra dar un modelo matemático de los lenguajes y de los procesos mediante los cuales la gente construye o forma oraciones válidas del lenguaje, se veía posible el dar un procedimiento algorítmico de traducción.

No fue sino hasta los años sesenta con el uso extendido de las computadoras, que el término Lenguajes Formales se refirió a los lenguajes que se utilizan para comunicarse con la computadora e indicarle algoritmos a llevar a cabo (calcular funciones). Los lenguajes de programación, en efecto, se ajustan bastante más fácil a modelos matemáticos que los lenguajes naturales, por lo que el desarrollo de este campo se ha dado fundamentalmente inscrito en el área de computación ya sea con el manejo automático del lenguaje natural o directamente con lenguajes de programación. Mucho del desarrollo en esta área se debe también a la lógica, pues presenta cantidad de problemas interesantes, contemplado desde este punto de vista.

Un lenguaje natural consiste siempre en un acervo de palabras (un diccionario o vocabulario) y un conjunto de reglas para combinar esas palabras y formar frases o enunciados. Al conjunto de reglas junto con el diccionario es a lo que llamamos la gramática del lenguaje.

Las reglas pueden ser, en general, de dos tipos: que hablen respecto a la forma de los enunciados o bien, respecto al significado o contenido. Lo primero es lo que conocemos como Sintaxis y segundo como Semántica. Se ha avanzado mucho más en el campo de la Sintaxis, respecto a automatización, que en el campo de la Semántica. Aquí hablaremos casi exclusivamente en este terreno.

Podemos pensar en un lenguaje como un conjunto de enunciados. Si el lenguaje es interesante muy probablemente es infinito. Esperamos que cualquier hablante nativo pueda enunciar en un momento dado una frase que si bien nunca antes había sido dicha y si está construida de acuerdo a la gramática con el vocabulario existente, la frase sea correcta. Si pensamos en los lenguajes en este contexto asumimos que, para empezar podemos trabajar con los lenguajes utilizando lo que conocemos de Teoría de Conjuntos.

 En este sentido, el primer problema al que nos enfrentamos es el de dar una descripción finita de conjuntos potencialmente infinitos. Se elige para ello el tratar de dar “propiedades” de los enunciados del lenguaje o bien listar las reglas gramaticales y el vocabulario. Si se desea saber si un enunciado pertenece o no a un lenguaje (a un conjunto) se exhiben las reglas que fueron utilizadas para construir ese enunciado. Si esto último se puede hacer, quiere decir que la frase está bien construida. Si no se puede hacer, existe la posibilidad de que el enunciado no pudiera ser generado con las reglas y no pertenezca a ese lenguaje. Un problema muy interesante en Lenguajes Formales es el de si, dado un lenguaje y un enunciado, podemos o no contestar a la pregunta de pertenencia. Dicho de otra manera, si no puedo encontrar las reglas utilizadas para la construcción del enunciado, ¿puedo o no decir que esto implica que el enunciado no está en el lenguaje? Aclaremos un poco más esta situación más adelante.

 
Un nuevo campo para el uso de la computación: el estudio de los lenguajes naturales.

Al hablar de enunciados en un lenguaje podemos pensar, sobre todo si el lenguaje es escrito, que lo que tenemos son sucesiones finitas de símbolos. A estas sucesiones les llamamos cadenas. Los símbolos pueden ser palabras completas y los enunciados oraciones formadas con esas palabras o bien los símbolos ser letras y dígitos y los enunciados ser sílabas o palabras. Cuando estamos en el contexto de Lenguajes Formales le exigimos al vocabulario o diccionario que sus elementos sean indivisibles y deben, en todo momento, manejarse completos. Dada esta situación, podemos pensar en los símbolos de los alfabetos como representados cada uno de ellos por alguna letra o dígito.

Cuando describimos un lenguaje en términos de las reglas que pueden utilizarse para generar sus enunciados decimos que estamos empleando métodos “generativos”. Las pruebas de pertenencia se llevan a cabo, entonces, generalizando enunciados del lenguaje utilizando esas reglas, en algún orden de ser posible, y aceptamos al enunciado como elemento del lenguaje si éste aparece en algún momento entre los enunciados generados.

Noam Chomsky, lingüista, logró formular en 1959 un modelo matemático de lenguajes. Lo primero que hizo fue tratar de clasificar los lenguajes en más o menos complejos de acuerdo a la “forma” que pudieran tener las reglas de generación o producción, dándoles una forma fija a estas reglas. Definió a una Gramática como un ente matemático (un cuádruplo) que contemplara:

— el vocabulario o diccionario, que en Lenguajes Formales se denomina el alfabeto;

— el conjunto de las reglas de generación o producciones;

— un conjunto de símbolos auxiliares, que denotan a las categorías para ser utilizadas como auxiliares en la generación de enunciados.

Creo que la necesidad de los dos primeros conjuntos es obvia. En cuanto al tercer conjunto, el de símbolos auxiliares, fijémonos un poco en las reglas gramaticales para formar oraciones en un lenguaje natural como el español. Cuando decimos cuál es la estructura de una oración, todos entendemos que oración no es una oración, sino que describe a la clase de las oraciones. Si después decimos que una oración es un “sujeto seguido de un verbo seguido de un complemento”, lo entrecomillado no es una oración, sino que describe a una oración. Las palabras sujeto, oración, complemento son auxiliares o categorías en las que se agrupan elementos del vocabulario y que no aparecen en el conjunto de oraciones que pretendemos construir. Toda gramática que pretenda dar reglas de generación de un número infinito de enunciados debe contar un conjunto finito de símbolos auxiliares para utilizarlos en puntos intermedios de la generación de enunciados. A estos símbolos auxiliares se les conoce como metasímbolos.

En el proceso de generar enunciados, deberemos tener un símbolo auxiliare que represente a la clase de los enunciados. Este símbolo se utiliza siempre como punto de partida en la generación de enunciados y es el cuarto elemento que nos falta especificar en nuestra gramática:

G = (V, N, P, S) una gramática es un cuádruplo donde: V un conjunto finito, el vocabulario, diccionario o alfabeto (en el sentido en que mencionábamos arriba.

N un conjunto finito de símbolos, llamados no terminales, auxiliares o variables o metasímbolos.

P es un conjunto finito de reglas de generación o producción, denominadas producciones.

S es el símbolo privilegiado por el que se empieza siempre la generación de posibles enunciados y se le denomina el símbolo inicial (S de Sentence) algunas veces se le denomina la meta.

En general se utilizan las letras minúsculas hacia el principio del alfabeto y los dígitos para denotar símbolos del vocabulario, mayúsculas hacia el principio del alfabeto para denotar símbolos auxiliares, minúsculas hacia el final del alfabeto para denotar cadenas y mayúsculas hacia el final del alfabeto para denotar vocabularios.

Las reglas de producción o generación tienen, como ya lo mencionamos, formas especiales. Al proceso mediante el cual se obtiene una cadena del lenguaje —utilizando las reglas de producción (en adelante producciones)— se le llama una derivación. Este proceso se lleva a cabo siempre sobre una cadena, que inicialmente consiste únicamente del símbolo inicial. Las reglas de producción tienen la siguiente forma:

α → β

y lo que quiere decir esto es: siempre que en la cadena de derivación aparezca la subcadena a se puede, utilizando esta regla, sustituirla por b para obtener una nueva cadena, a y b son, a su vez, cadenas formadas con símbolos del vocabulario y símbolos auxiliares. Son cadenas de Lenguaje aquéllas que consisten exclusivamente de símbolos del vocabulario. Exigimos que a contenga al menos un símbolo auxiliar. Esto se debe a que en el proceso de derivación lo que se hace en cada paso del proceso es sustituir a una clase (metasímbolo) por un representante de esa clase para obtener instancias particulares de cadenas. De esto se ve que no tiene sentido elegir un representante de algo que no es una clase (un símbolo del vocabulario).

 
Se afirma que los niños pueden tener un “instinto especial” para comprender las máquinas más complejas conocidas hasta ahora. ¿En qué tipo de adultos se convertirán estos niños?

Como mencionamos antes, Noam Chomsky dio una clasificación de Lenguajes de acuerdo a la forma que pudieran tener las producciones y que se conoce hoy día como Clasificación de Chomsky. La clasificación procede a limitar la forma de a y b de tal forma de “acorralar” de alguna manera las derivaciones y poder decir algo respecto al problema de pertenencia que mencionamos antes. Si se logra dar cotas para la duración de derivación de cadenas de una determinada longitud con una gramática dad, pasada esa cota podemos siempre decir su la cadena está o no en el lenguaje generado por esa gramática. La clasificación de Chomsky es la siguiente:

1. La gramática es regular o tipo 3 si cumple con que

α = A    un solo metasímbolo y
β = aB    consista de un símbolo terminal y un metasímbolo o únicamente un símbolo terminal.

2. La gramática es libre del contexto o tipo 2 si cumple con que

α = A    como en el caso anterior y
β    consista de un símbolo terminal y un metasímbolo o únicamente un símbolo terminal.

3. La gramática es dependiente del contexto o tipo 1 si las producciones cumplen con:

α    contiene al menos un metasímbolo y
β    tiene al menos el mismo número de símbolos que a.

4. Por último, las gramáticas son generales o tipo 0 si
α    contiene al menos un metasímbolo.

Los nombres de cada una de estas clases se derivan de la forma en que se pueden emplear las producciones en los procesos de derivación. En el caso de las gramáticas regulares generan lenguajes que pueden ser representados también por expresiones regulares. En las derivaciones en gramáticas libres del contexto, como el antecedente de cada producción es un solo símbolo, este símbolo puede ser sustituido por el consecuente de la producción independientemente del contexto en el que está apareciendo. En el caso de las gramáticas dependientes del contexto, el antecedente de la producción nos dice que si el metasímbolo se encuentra —en la cadena de derivación— dentro de un contexto dado (las subcadenas que lo rodean) entonces puede ser sustituido por el consecuente de esa producción.

La clasificación de los lenguajes se deriva de aquella de las gramáticas, diciendo que un lenguaje es de tipo “i” si se tiene una gramática del tipo correspondiente que lo genere. Por supuesto que siempre se intenta tener una gramática lo más restringida posible (para que cumpla con las propiedades) al generar un determinado lenguaje.

 
Cadena de derivación que contiene un valor único de transición en cada arco y sigue un solo camino.

De la especificación de las producciones se puede ver que las gramáticas de tipo “i” cumplen con las propiedades de los tipos mayores que “i”. Se tiene que la clase de lenguajes regulares está contenida propiamente en la de los lenguajes libres del contexto que a su vez está contenida propiamente en la de los lenguajes dependientes del contexto y está en los lenguajes generales.

Es importante notar que con las gramáticas tenemos una forma de denotar conjuntos de cadenas (lenguajes) infinitos. Sin embargo, no todos los lenguajes infinitos podrán ser denotados a través de gramáticas; pues habrá lenguajes que sólo puedan ser delineados mediante descripciones infinitas. Para ponerlo en términos de Computabilidad: pensemos en un alfabeto dado y construyamos el lenguaje que consiste de todas las posibles cadenas finitas que se pueden construir con ese alfabeto. Este lenguaje es infinito, Cualquier lenguaje que se construya con símbolos de ese alfabeto, sea finito o no, será un subconjunto del que acabamos de construir. De lo anterior, el número de lenguajes que puede tener con símbolos de un cierto alfabeto resulta ser el número de subconjuntos de un conjunto infinito, que podemos poner en correspondencia con los números reales. Conclusión: el número de lenguajes sobre un alfabeto tiene la misma cardinalidad que los números reales (hay tantos como números reales).

Las gramáticas, en cambio, son descripciones finitas. Puedo organizarlas de tal forma que las ponga en correspondencia con los enteros. Por lo que la cardinalidad de las gramáticas es la misma que la de los enteros. De todo esto, tengo más lenguajes que descripciones finitas, por lo que habrá lenguajes para los que no pueda dar una descripción finita.

Como mencionamos al principio, las gramáticas no las queremos utilizar tanto para generar lenguajes como para, dada una gramática y una cadena, poder decir si esa cadena puede o no ser generada por esa gramática (si pertenece o no al lenguaje). Se ve claro que en los problemas de la traducción automática lo primero que querríamos poder hacer es decidir si lo que estamos tratando de traducir está escrito, en efecto, en el lenguaje que sabemos traducir. En computación, donde los lenguajes de programación pueden ser descritos generalmente a través de gramáticas libres del contexto, lo primero que queremos es ver si nuestro programa tiene la forma adecuada.

El problema de si una cadena está o no en un lenguaje no siempre es decidible. Para el caso de los lenguajes de tipo 1 o tipo 3 sí lo es, pero no así para los lenguajes generales, y ello se debe al tipo de producciones que permitimos. Esto no quiere decir que para un lenguaje particular de tipo 0 no podamos decir todo lo que queremos respecto a él, sino que en general no podemos demostrar que podemos hacerlo para todos los lenguajes de ese tipo.

El decidir si una cadena está o no en un lenguaje puede verse también como una descripción de lo que es un lenguaje.

Podemos pensar en que tenemos una caja negra a la que le “alimentamos” la cadena. Esa caja está pensada para reconocer a todas las cadenas que pertenezcan a un cierto lenguaje (dado que estamos pensado en realidad en un “mecanismo” capaz de llevar a cabo una tarea, en adelante nos referiremos a la caja negra como una máquina o autómata). Si la cadena que le alimentamos está en ese lenguaje, el autómata “contesta” que si y no está contesta que no. Existe, sin embargo, la posibilidad de que el autómata se tarde mucho en “digerir” la cadena, o, como ya habíamos dicho, que nunca suspenda su proceso para decir que si la cadena está o no está.

Contrapuesto a los métodos generativos de lenguajes, entre los que se encuentran las gramáticas formales, se hallan los métodos reconocedores, a través de autómatas finitos. Tratemos de precisar un poco más el concepto de un autómata reconocedor.

En general, cuando se habla de máquinas todos tendemos a pensar en un objeto físico, construido sólidamente y capaz de realizar un cierto trabajo. Sin embargo, podemos pensar en una máquina “conceptual”, no sólo concretizada y centrar nuestra atención en las labores que esperamos realice la máquina: evaluarla de acuerdo a su comportamiento y no a su forma. Este enfoque no es tan fuera de lo común. Cuando, en la vida diaria, describimos una máquina, generalmente decimos lo que la máquina es capaz de hacer y no la descripción exacta de cada uno de los componentes. O también sucede que mencionemos el “nombre” de la máquina y ese nombre implica las labores que la máquina puede ejecutar.

Los autómatas son máquinas capaces de reconocer lenguajes o realizar otro tipo de tareas como el cálculo de valores, sumas, multiplicaciones, traducciones, etc. Es interesante hacer notar que aún en una multiplicación no puede verse como manipulación de lenguajes que involucran traducción. A la máquina se le alimentan dos cadenas, cada una de ellas representando a un número y la máquina produce una nueva, la traducción de la entrada (que consiste de dos cadenas) y que cumple con ser lo que nosotros llamaríamos el producto de esos dos números. Por ello no distinguiremos entre máquinas capaces de realizar operaciones y las que son capaces de reconocer o traducir, pues corresponden simplemente a puntos de vista distintos para el mismo proceso.

 
Diagrama de un autómata que reproduce lo que lee, retrasado dos unidades de tiempo.

Clasificaremos a los autómatas, vistos como máquinas reconocedoras, según el tipo de operaciones que pueden ejecutar y el equipo con el que cuentan para auxiliarse en sus operaciones. Las operaciones son realmente muy sencillas: leer de una cinta en la que viene escrita la cadena o palabras a reconocer, “recordar” lo que ha visto, la posibilidad de escribir o no en la cinta en las que están escritos sus datos.

Es claro que toda máquina debe ser capas de leer de la cinta en la que se encuentran sus datos. Si esto no fuera cierto, cómo decidiría si lo que está ahí escrito es aceptado o rechazado. En cuanto a la posibilidad de “recordar”, la cantidad o tipo de información que el autómata puede o no recordar es precisamente lo que le da su lugar en la clasificación.

Los autómatas cuentan en realidad con dos disposiciones donde pueden recordar. El primero de ellos es lo que se conoce como el estado del autómata. Un autómata consiste de un conjunto finito de posibles estados, donde cada estado representa una situación particular. Por ejemplo, el estado inicial en el que se encuentra un autómata es el de no “recordar” nada pues nada ha sucedido. De ahí en adelante, conforme va leyendo símbolos de su cadena de entrada, se transfiere o cambia a estados que registren los símbolos vistos. No es lo mismo ver un sustantivo al principio de una oración, en cuyo caso pasaríamos a un estado que registrara al sujeto, que ver un sustantivo en el predicado: el papel que juegan ambos sustantivos es totalmente distinto y esto lo registra el autómata cuando, después de ver a cada uno de estos sustantivos, se encuentra en estados diferentes.

Además del estado que le indica al autómata que se llevó a cabo una cierta sucesión de transiciones, algunos modelos cuentan con una “memoria” o cinta auxiliar donde anotan algo de lo que han visto. Por supuesto que es más poderoso un autómata con memoria auxiliar que uno que no la tenga. Por último, podemos combinar la cinta donde se encuentran los datos de entrada con la memoria auxiliar y conseguir de esta forma el modelo que se conoce como Máquina de Turing.

Mencionamos tres modelos principales de autómatas que sin agotar todas las posibilidades son los que más nos interesan desde el punto de vista de autómatas de reconocedores. Estos modelos cumplen con lo siguiente:

1. Tienen un número finito de estados posibles.

2. Trabajan con cadenas construidas a partir de un alfabeto finito.

3. En todos ellos se especifica un estado inicial.

4. Realizan transiciones de un estado a otro dependiendo del estado en el que se encuentren y del símbolo que en ese momento estén observando.

 
Árbol de derivación de frases en español. El diagrama muestra cómo se usan las reglas de la gramática para generar la expresión.

De acuerdo, entonces, a los mecanismos con que cuentan los autómatas para recordar nos interesan entre los distintos modelos los siguientes:

1. Autómatas con un número finito de estados. El único mecanismo con que cuentan para recordar estas máquinas es el de los estados. Como se podría esperar, son limitados los tipos de reconocimiento que pueden hacer. Se puede demostrar que pueden reconocer a los lenguajes regulares y que dado un autómata finito se puede dar una gramática regular que genere al lenguaje reconocido por el autómata finito.

2. Autómatas con stack. En este tipo de autómatas, además de un número finito de estados, la máquina cuenta con una cinta, potencialmente infinita, en la cual puede escribir símbolos que le ayuden a recordar lo que ha visto. Aunque el uso de la cinta no es irrestricto pues debe ser en un cierto orden y bajo reglas muy definidas, esto, como se puede suponer, amplía el poderío de la máquina posibilitándola a reconocer lenguajes más complicados. También está demostrado que todo lenguaje libre del contexto puede ser reconocido por una máquina de stack y que todo lenguaje que es reconocido por una máquina de stack puede ser generado por una gramática libre del contexto.

3. Máquinas de Turing. Estos autómatas corresponden al modelo más poderoso de entre los autómatas con un número finito de estados. Como ya lo mencioné, tiene la posibilidad de reescribir en su cinta de entrada y esto prácticamente sin ninguna restricción, por lo que terminamos con un modelo más poderoso que el anterior. Es una tesis (la tesis de Church) el que una máquina de Turing puede llevar a cabo todo proceso que se especifique como un procedimiento, con un número finito de pasos y cada paso lo suficientemente simple como para ser ejecutado, en principio, por un hombre con papel y lápiz.

Empezaremos por describir el modelo más sencillo: el autómata con un número finito de estados (a quien denominaremos autómata finito). Cuando decimos “autómata” nos referimos a un modelo matemático, cuyas propiedades y comportamiento podemos observar y que podemos simular con un programa de computadora. Estos autómatas han sido estudiados en muy diversas disciplinas como Diseño de Computadoras, Neurofisiología, Comunicaciones, Lingüística y la Teoría de Computación. Son bastante conocidos y comprendidos. Este modelo surge en situaciones físicas en las cuales se procesan señales que conllevan información.

El término “autómata finito” se usa en muchos sentidos y tiene asociadas distintas definiciones formales. Todas estas definiciones conllevan en común aceptar que los autómatas finitos pretenden modelar instrumentos de cómputo que tiene una cantidad fija de memoria y que leen sucesiones construidas a partir de un conjunto finito de símbolos. Consiste de un conjunto de estados Q y un conjunto de transiciones de estado a estado que ocurren cuando al autómata se le alimentan símbolos de un alfabeto ∑. El autómata finito es determinístico, esto es, que de cada estado (que puede ser en el que estaba). El autómata tiene un estado inicial en cual el autómata arranca siempre. Algunos estados son designados como estados finales o estados que aceptan.

Podemos pensar en el funcionamiento del autómata como una sucesión de movimientos (o transiciones) cada una de ellas en un instante dado de tiempo t, t = 0 representa el momento en el que el autómata no ha empezado aún a trabajar. La distancia entre t = i y t = i + 1 es arbitraria. En t = 0 el autómata es inicializado a un estado inicial. En cada momento t, M recibe un símbolo s en ∑. La capacidad de la máquina para retener información respecto a símbolos anteriores reside en el conjunto de estados. En este sentido, lo que recuerda el autómata respecto al pasado es que “lo que ha visto” lo obligó a entrar en un cierto estado. Cuando se le alimenta un símbolo al autómata se produce en él un cambio de estado, que depende exclusivamente del estado en el que está y el símbolo que está viendo. A este cambio de estado se le llama una transición.

Si al terminar de alimentarle al autómata una sucesión, la última transición fue a un estado final, entonces decimos que el autómata acepta a la sucesión. Si, por el contrario, el estado en el que terminar no es el final decimos que el autómata rechaza a la sucesión.

Un autómata finito puede ejecutar (o reconocer) únicamente operaciones que requieren una cantidad fija de memoria. Sin embargo, hay muchas operaciones que no pueden ejecutarse bajo estas restricciones como lo son el checar si una expresión tiene el mismo número de a’s que de b’s o checar si los paréntesis de una expresión están bien emparejados, la multiplicación de dos números, etc.

Para obtener máquinas más poderosas, lo que se necesita es eliminar la restricción sobre la finitud de la memoria. Para esto se utiliza un mecanismo de almacenamiento, muy común en computación, llamado un stack. El stack es una memoria donde la última información que entró es la primera que sale (First In First Out o FIFO), y se incorporan o sacan símbolos del stack de uno en uno, mediante operaciones de PUSH para meter y POP para sacar. Se dice también que la información más reciente está en el tope del stack. También es relevante el “fondo” del stack donde se encuentra la primera información que se metió. En ningún momento se puede “ver” o utilizar nada que no se encuentre en el tope. En general, diremos que si el stack está vacío no podemos “ver” nada en él, o bien podemos tener la convención de un símbolo que aparezca en el “fondo” del stack, y que al verlo, sepamos que ya no hay más símbolos dentro de él que pudiera intentarse sacar.

Un autómata con stack tiene la capacidad de recordar a través de sus estados, como lo hace el autómata finito, pero incorpora la capacidad de recordar en el stack. Por ejemplo, si quiere reconocer a la cadena

ancbn

(cadenas de a’s y b’s con el mismo número de a’s que de b’s y todas las a’s al principio seguidas de todas las b’s), todo lo que hace es tener dos estados, para saber si está en la fase de contar a’s o b’s. En el estado 1, por ejemplo, por cada a que ve mete un símbolo (digamos un cero) al stack. En cuanto reconoce el símbolo c, pasa al estado 2, donde por cada b que ve saca un cero del stack. De esta forma, sabemos que la cadena estaba bien construida si al terminarse la cadena de entrada el autómata termina con el stack vacío. La cadena no está bien construida en cualquiera de los dos casos siguientes:

a) Se termina la cadena de entrada y todavía hay ceros en el stack. En este caso, hubo más a’s que b’s.

b) Todavía no se acaba la cadena de entrada y, sin embargo, ya no hay ceros en el stack. En este caso, hubo más b’s que a’s.

Podemos sintetizar las reglas bajo las que opera un autómata de stack (AFS) de la siguiente manera:

1. La máquina empieza con una cierta configuración inicial en el stack. En el caso anterior, el stack deberá tener únicamente el símbolo del “fondo” del stack.

2. La máquina empieza a funcionar en un cierto estado inicial. En el caso anterior, el estado inicial es el que “mete” ceros al stack.

3. El funcionamiento del AFS estará dado por un conjunto de reglas que especifican, dado un estado, un símbolo de entrada, y un símbolo en el tope del stack, el estado al que debe transferirse, lo que debe hacer el autómata con la cadena de entrada y lo que debe hacer el autómata con el stack.

4. El autómata puede hacer con el stack una de tres operaciones:

POP    (sacar)

PUSH    (meter)

(no hacer nada)

5. El AFS puede hacer con la cadena de entrada una de las dos operaciones siguientes:

AVANZA    (coloca la cabeza lectora en el siguiente símbolo)

(no avanza la cabeza de lectura)

6. Cualquier combinación (estado, entrada, stack) que no esté especificado respecto al autómata finito, ocasiona que el AFS interrumpa su operación.

7. Decimos que un AFS acepta una cadena si al interrumpir su operación después de haber examinado a toda la cadena de entrada, termina con el stack vacío.

Los autómatas de stack pueden, como ya mencionamos, determinar si una expresión aritmética está o no bien construida, a su vez determinan si una cadena dada es “capicúa” (o espejeada respecto a su mitad) y muchas otras operaciones más. Se puede construir un autómata de stack para reconocer a cualquier lenguaje que pueda ser generado por una gramática libre de contexto y se puede dar una gramática libre del contexto que genere a un lenguaje que es reconocido por una máquina de stack. En Computación tienen mucha importancia, pues casi todos los lenguajes de programación se pueden describir mediante gramáticas libres del contexto y muchos de los métodos de traducción se pueden apoyar en resultados respecto a estos autómatas.

Por último, la Máquina de Turing (MT), planteada por Allen M. Turing en 1936, ha sido propuesta como un modelo matemático para describir procedimientos. Dado que es difícil representar procedimientos, se dificulta también demostrar que estos dos conceptos son equivalentes. Sin embargo, de la definición de una Máquina de Turing quedó suficientemente claro que cualquier cómputo que se pueda describir con una de ellas puede ser llevado a cabo mecánicamente. También se puede demostrar que cualquier cómputo que se pueda llevar a cabo en una computadora digital, como las que conocemos hoy en día, puede ser descrito a través de una Máquina de Turing.

 
Dos posibles árboles de derivación para la cadena ababab.

Hay muchas otras formalizaciones de procedimiento que se pueden demostrar son equivalentes a la Máquina de Turing. Esto refuerza la idea de que la definición de su Máquina dada por Turing es suficientemente general como para comprender la idea intuitiva que tenemos de un procedimiento. La tesis de Church nos dice que cualquier proceso que se reconoce naturalmente como procedimiento puede ser llevado a cabo por una MT. No sólo eso, la definición de procedimiento es hoy en día sinónimo de ser computable por una MT. Sin pretender demostrarlo daremos por buena la tesis de Turing de que toda solución algorítmica para un problema puede ser representado por un programa de instrucciones para alguna Máquina de Turing. Aún cuando este hecho sigue siendo una hipótesis, el trabajo de Turing y de muchos otros tiene una consecuencia única e irrebatible: existen problemas bien formulados para los cuales no puede existir una solución algorítmica.

Al describir su máquina, Turing mantuvo presente en su mente las propiedades básicas que ha de tener un procedimiento eficiente: primero, debe estar descrito finitamente; segundo, el procedimiento debe consistir de pasos discretos, cada uno de ellos ejecutable mecánicamente. El modelo básico de Turing contempla estas propiedades.

Pensemos en una MT consistiendo “físicamente” de dos componentes básicos: un control finito y una cinta infinita. La cinta, que contiene a la cadena de entrada, está dividida en celdas. El control finito tiene una “cabeza lectora” capaz de revisar (o posicionarse) en una sola celda a la vez. Podemos pensar que la cinta es infinita únicamente hacia la derecha, y tiene una celda la cual consideraremos la del extremo izquierdo. Es posible demostrar, aunque no lo haremos, que el acortar la cinta por la izquierda no limita en forma alguna la capacidad de cómputo de la MT. Cada celda de la cinta puede contener uno de un conjunto finito de símbolos llamados símbolos de la cinta.

Al empezar a funcionar la MT, las primeras n celdas (las de más a la izquierda), para n mayor que cero finita, contiene la entrada o datos de la máquina consistentes en una cadena de n símbolos, cada uno de ellos de un subconjunto de símbolos, llamados símbolos de entrada, seleccionados del conjunto de símbolos de la cinta. El resto de las celdas, un número infinito, contienen un símbolo especial que no forma parte de los símbolos de entrada, digamos “B” (un blanco). En un movimiento, la MT, dependiendo del símbolo que esté revisando la cabeza lectora y del estado en el que se encuentre el control finito, ejecuta lo siguiente:

1. Cambia de estado.

2. Imprime un símbolo en la celda que está revisando reemplazando al símbolo que había ahí antes y que fue el que determinó, junto con el estado el movimiento de la MT, y

3. Mueve su cabeza lectora a la celda contigua izquierda o derecha (L o R, respectivamente).

El poderío adicional que alcanza la MT se debe principalmente a su habilidad para escribir en la misma cinta de la que está leyendo, donde vienen sus datos.

El tipo de problemas que puede resolver una Máquina de Turing es muy amplio. Sin embargo, también como ya se mencionó, quedan muchos fuera de su ámbito. Otro aspecto importante de una Máquina de Turing se refiere a que es capaz de llevar a cabo toda solución expresada como procedimiento y la diferencia entre un procedimiento y un algoritmo es que el procedimiento puede no ser suficiente (terminar su ejecución). Por ello, habrá procedimientos para los cuales una Máquina de Turing los ejecute pero no suspenda nunca su funcionamiento. Esto querría decir que ante la pregunta fundamental que nos hemos estado haciendo respecto a que si dada una cadena y un lenguaje tenemos o no el dispositivo que nos diga si la cadena pertenece al lenguaje, en el caso de las Máquinas de Turing el reconocimiento, si termina, nos dará una respuesta, pero si no termina no sabremos cuál es esa respuesta.

 
La computación en Matemáticas es un campo rico en conocimientos, intereses, problemas y juegos de intelecto.
 
 articulos
 
       
       
____________________________________________________________
     

Elisa Viso Gurovich
Departamento de Matemáticas, Facultad de Ciencias, UNAM.

como citar este artículo

     

de venta en copy
Número 134
número más reciente
 
134I


   
eventos Feriamineriaweb
  Presentación del número
doble 131-132 en la FIL
Minería

 


novedades2 LogoPlazaPrometeo
Ya puedes comprar los 
ejemplares más
recientes con tarjeta
en la Tienda en línea.
   

  Protada Antologia3
 
Você está aqui: Inicio revistas revista ciencias 9 El por qué de la computación en matemáticas