¿ Un artículo ?

Escribe Orlando Mazeyra Guillén

U.C.S.M. Programa profesional de Ingeniería de Sistemas

JULIO DEL 2001

“ La noción intuitiva e informal de un procedimiento de símbolos es idéntica a nuestro concepto del que puede ser ejecutado por una máquina de Turing “

HIPÓTESIS DE TURING (1936)

Escribir un artículo puede ser considerada una tarea de titanes para un despistado y mediocre estudiante de ingeniería de sistemas, una verdadera odisea, sobre todo si lo hace a sabiendas de que su “seudo-artículo” no va a ser publicado en ningún medio de difusión escrita y para colmo seguramente ni siquiera va a ser ojeado por el docente que le encomendó tal tarea.

¿ Y porqué escribirlo ? Hay muchas motivaciones, pero mi mejor acicate es que tal vez estas poco armoniosas ( y ojalá no absurdas) líneas me sirvan para aprobar la asignatura, eso sí es importante, así que manos a la obra.

Debe haber quedado muy en claro que el autor de este bodrio no es una eminencia en ciencias de la computación, pero con todas sus limitaciones trata de ofrecer un alcance muy peculiar sobre “Las máquinas de Turing”.

Al ritmo de la moda

Cuando la gente me pregunta: ¿ Qué estudias ?, Yo soy escueto pero rotundo al responder: sistemas. Y el comentario inmediato de mis entrevistadores es: Ah, sistemas, esa carrera está de moda... Uno que otro me dice: Es la carrera del momento... Comentarios que no sé si tendrán algún fundamento, pero de lo que sí estoy seguro es que son una buena “pastilla” que me invita a seguir estudiando esta compleja carrera.

No es pues mi interés debatir o verificar si la carrera que estudio está en boga, pero lo que sí me interesaría es que las “maquinas de Turing” fueran un tema de conversación constante entre los estudiantes de ingeniería de sistemas. Estas máquinas no están en la cresta de la ola y no son los nuevos microcomputadores del siglo XXI, más bien tienen una larga data, cosa que no las hace obsoletas, se las podría considerar como aquel viejo grupo musical que nunca pasa de moda, algo así como los Beatles ( una comparación que no viene al tema).

¿ Por qué las Máquinas de Turing ?

Hace un par de días me enteré de una cosa debería saber desde el primer año de universidad (la culpa es mía o de la “Cato”) :Que una computadora no es más que un autómata finito o una red modular capaz de gobernar su entrada y su salida ...

Queda claro pues que si los estudiantes de sistemas tenemos como herramienta primordial a la computadora, antes de aprender a programar, a diseñar algoritmos o trabajar con estructuras de datos deberíamos hacer un meticuloso estudio de las “máquinas de Turing”.

Llega por sí sola la primera conclusión de la tarde, la currícula de sistemas está mal enfocada pero el “pata” que nunca estuvo mal enfocado fue Alan Mathison Turing (1912-1954), quien fue el pionero en la teoría del ordenador. Allá por 1936 cuando era sólo un estudiante (como yo) publicó un ensayo titulado “Sobre números calculables”, con esto contribuyó a la lógica matemática al introducir el concepto teórico de un dispositivo de cálculo que hoy se conoce como Maquina de Turing.

Lo que tenemos que tener muy en claro es que cualquier cálculo que pueda realizar un computador digital ( que usa un repertorio finito de instrucciones) también puede ser realizado por una máquina de Turing, para mas detalles vamos a dar un par de definiciones que pueden invitar al bostezo pero que son muy importantes en la comprensión de este tema.

“ Una máquina de Turing Z es un autómata finito A, junto con una cinta potencialmente infinita ( que en cualquier momento dado contiene sólo un número finito de símbolos distintos del blanco “#”) dividida en casillas (cada casilla contiene un blanco “#” o un símbolo) y un dispositivo D para examinar una casilla y cada vez, imprimiendo un nuevo símbolo en ella y desplazando la cinta una casilla a la izquierda o a la derecha”

HIPÓTESIS DE TURING Y CONJUNTOS RECURSIVOS

En el curso de diseño de algoritmos de IV semestre aprendí lo que son la funciones recursivas, que definidas en forma sencilla serían aquellas “funciones que se llaman así mismas”. El ejemplo de la primera práctica era la función recursiva del factorial:

int FACTORIAL ( int NUMERO)

{

if (NUMERO==1) return NUMERO;

else return NUMERO* FACTORIAL(NUMERO-1)

}

Ahora es importante aclarar la idea de procedimiento efectivo. Existen ciertos cálculos para los que existen reglas mecánicas, o algoritmos: como por ejemplo el algoritmo recursivo mostrado arriba que halla el factorial de un número entero o el algoritmo euclídeo para calcular el máximo común divisor de dos números enteros. Ciertamente, cualquier cálculo que se pueda realizar mediante computadores electrónicos estará gobernado por reglas que son puramente mecánicas.

Entonces, existe un procedimiento efectivo para realizar esos cálculos.

Hay muchos casos en los que cuando nos dejan hacer una aplicación en prácticas de algún curso (Criptografía, por ejemplo), y pese a no saber cómo escribir un programa para realizar los cálculos deseados en un computador determinado ( cuando no nos sale un programa, una rutina, etc.), pensamos que de seguro existe un procedimiento efectivo para hacerlo.

Pero, no tenemos la sensación de que existe un procedimiento efectivo para predecir de que lado caerá una moneda de un nuevo sol, por ejemplo.

Como ya dije en las líneas anteriores, cualquier proceso que se pueda realizar en una computadora como las flamantes IBM del laboratorio de prácticas también puede realizarse con una máquina de Turing.

Cabe traer a colación nuevamente la hipótesis de Turing : “ La noción intuitiva e informal de un procedimiento efectivo sobre secuencias de símbolos es idéntico a nuestro concepto del que puede ser ejecutado por una máquina de Turing”.

Esta hipótesis no admite una demostración formal, pero podríamos señalar con mucha seguridad que hasta la fecha, julio del 2001, siempre en el desarrollo de la teoría de funciones recursivas era evidente por intuición que existía un procedimiento efectivo, ha sido posible pensar una máquina de Turing que ejecuta con proceso rigurosamente análogo.

Existe pues una reformulación de definiciones, por ejemplo:

Una función es recursiva si existe un procedimiento efectivo para calcularla.

Así también podemos decir, que un conjunto es recursivo si existe un procedimiento efectivo para comprobar si un elemento pertenece o no a él.

Finalmente, un conjunto es recursivamente enumerable si hay un procedimiento efectivo para generar sus elementos, uno detrás del otro.

Eficiencia de algoritmos (¿Cómo?)

Es importante utilizar una representación de máquinas de Turing para expresar en el papel un algoritmo antes de llevarlo a la máquina, sabemos que el costo de un programa está constituido por diversos componentes. Algunos de estos componentes implican el costo del tiempo humano ( el tiempo que se desarrolla, mantiene y usa un programa).

Los otros componentes y que juegan un papel crítico son el costo de la ejecución del programa ( la EFICIENCIA del programa) que se mide por la cantidad de tiempo y espacio de computadora que requiere el programa en su ejecución.

Es difícil realizar un análisis simple de un algoritmo que determine la cantidad exacta de tiempo que se requiere para ejecutarlo. La primera complicación que aparece es que la cantidad exacta de tiempo depende de la implementación del algoritmo, es por eso que cada algoritmo tiene un costo computacional diferente.

Palabra clave: Computabilidad

A continuación presento una explicación sencilla “bajada” de una página de Internet donde se trata de definir la computabilidad:

“ ¿Puede una rana emocionarse ante el Guernica de Picasso? El sentido común a todos nos aconseja responder con un rotundo no; diríamos que el cerebro de la rana es incapaz de:

a) Ver la imagen del cuadro sobre la pared (de hecho la rana detiene su atención en objetos en movimiento) (Jastrow, 1981);

b) Aún en el caso de apreciar el contenido del cuadro, no la creemos capaz de entender la escena que en él se representa y c) dudaríamos de que la rana tuviese también la facultad de horrorizarse con una escena de guerra y violencia. En conclusión, aceptamos que el cerebro de la rana es incapaz, a partir de una entrada de información (imagen visual del Guernica) de procesarla, elaborarla y transformarla hasta conseguir una cierta salida de información tal como un pensamiento triste; decimos que la rana no computa el proceso que se acaba de describir.

Computar significa poner en funcionamiento unas reglas de procesamiento de información o algoritmo que a partir de unos ciertos datos de entrada obtenga un determinado resultado. La rana no computó porque carecía del algoritmo adecuado; además tampoco creemos que el cerebro de la rana sea lo suficientemente sofisticado como para albergar semejante algoritmo.

El concepto de algoritmo es intuitivo y sirve para nombrar muchas cosas, desde una receta de cocina hasta cómo obtener el máximo común divisor de dos números enteros. A veces incluso se puede plantear ante un proceso de entrada/salida la pregunta de si existe un algoritmo que lo compute o simule. Para tratar estos problemas con rigor es necesario formalizar y matematizar la propia idea de algoritmo.

Sin duda, el formalismo más popular y menos abstracto es el ideado por Alan Turing y que se conoce precisamente con el nombre de Máquina de Turing (MT). Aquí sólo se darán algunos esbozos sobre las MT, centrando el interés en los resultados, más que en cómo llegar a ellos; para profundizar en los aspectos formales mejor acudir a Hamilton (1980), Arbib (1964) y muchos otros.

Podemos pues definir la computabilidad de la siguiente manera:

Definición: Una función natural f de variable natural es computable por la máquina Z si siendo n el estado inicial de la cinta, la información de ésta tras la parada de Z coincide con m=f(n).

La existencia de funciones imposibles de evaluar por métodos algorítmicos, o bien que siendo evaluables el tiempo necesario para ello va más allá de lo razonablemente factible, tiene una consecuencia importante para lo que llamamos método científico; algunos problemas sólo pueden ser abordados por técnicas de simulación, de forma que los ordenadores además de servir para hacer operaciones numéricas, también sirven como laboratorios de experimentación (Wagensberg, 1985). Esta consecuencia es especialmente cierta en lo que se refiere al estudio de los Sistemas Emergentes, muchas de cuyas propiedades no será posible deducirlas de forma exacta, con lo que únicamente queda el recurso de la simulación (curso que se lleva en el VIII semestre).

Objetivo: Un nuevo enfoque de la enseñanza

Es innegable que para poder computar necesitamos trabajar con unas reglas de información o algoritmos que a partir de ciertos datos de entrada lleguen a un resultado.

Por tanto, si nosotros queremos computar en todo el sentido de la palabra debemos contar con el algoritmo adecuado, para esto debemos aprender normas básicas antes de programar.

Es pertinente recomendar una modificación de la metodología utilizada hoy en día en la U.C.S.M. ya una de las primeras materias que se debería dictar en nuestra carrera es la de “Máquinas de Turing” o tal vez autómatas , pues se nos debe ensañar primero a pensar a los alumnos, expresando primero un modelo lógico manual de la resolución de un problema, el hecho de pasarlo a un lenguaje de programación podría considerar una actividad de segundo plano.

Antes de programar con objetos, se tiene preludio de la programación estructurada o modular, y hemos visto pues en las clases teóricas de Teoría de Autómatas, que con las máquinas de Turing podemos trabajar en bloques. Según Dijkstra , Divide y vencerás, al diseñar pues un sistema complejo es necesario descomponer las partes más y más pequeñas, de tal manera de irlos refinando independientemente.

Finalmente para terminar cito unas líneas muy interesantes sacadas del prospecto de la U.C.S.M. de 1998 (el año que ingresé a la universidad) donde se indica que para ser Ingeniero de Sistemas se debe contar con las siguientes “características personales”:

@ Actitud crítica, para analizar y comprender la realidad nacional

@ Actitud de superación y autoperfeccionamiento profesional y personal

@ Actitud para la investigación científica y tecnológica

@ Potencialidad para ser agente de cambio

@ Hábito de trabajo en equipo

Yo añadiría una última línea: “mucha imaginación”, la imaginación es un factor crítico en todos los aspectos.

Si nosotros le damos un buen uso a la imaginación podremos innovar, porque innovar es simplemente, ver lo que todos ven pero pensar lo que nadie ha pensado, allí está nuestro reto...

Y como alguna vez dijo un señor que se apellidaba Einstein:

“La imaginación es más importante que el conocimiento”