Teorías Lógicas y Máquinas de Turing

se tiene una presentación detallada de la Lógica de Primer Orden. En esta sección recordaremos los conceptos necesarios para establecer la relación de una teoría lógica en general con los Autómatas de Turing, y en general con la disciplina de Computación.

Una teoría lógica (TL) se define a partir de un conjunto de enunciados dados llamados axiomas, unas reglas de inferencia y un esquema de derivación. A partir de los axiomas y aplicando las reglas de inferencia y el esquema de derivación se infieren los teoremas de la teoría. El conjunto de teoremas de la teoría forman un lenguaje formal.

Si es posible definir una máquina de Turing tal que reconozca al lenguaje de los teoremas, este lenguaje es decidible y la teoría también lo es en consecuencia. Dicho en otras palabras, si el conjunto de teoremas visto como un lenguaje es reconocido por una máquina

de Turing, entonces la TL es decidible. Y viceversa.

Puede hablarse entonces de manera indistinta de teorías lógicas o de lenguajes decidibles, como aquellos para los que existe una máquina de Turing capaz de reconocerlos. Luego, la correspondencia entre la sintaxis de una teoría lógica (lenguaje formal) y el reconocimiento simbólico de la mismo por parte de un autómata queda establecida.

Desde el punto de vista semántico, las interpretaciones de las cadenas del lenguaje se realizan ya sea por el intérprete ó bien por el compilador del lenguaje de programación en el cual se dan las instrucciones (ver Sección de Autómatas de Pila). Las cadenas que resultan en instrucciones realizadas por la computadora pueden considerarse interpretadas como verdaderas y por tanto tienen, al menos, un modelo de la Teoría Lógica formada por tales cadenas.

En particular, los axiomas se consideran teoremas de la teoría, los cuales se derivan aplicando cero veces las reglas de inferencia

No Computabilidad

Se ha visto que los algoritmos son un concepto fundamental de la ciencia de la computación y se ha desarrollado cierto conocimiento interno sobre la forma en que pueden construirse. Se sabe que existen algoritmos para tejer un suéter, construir un modelo de aeroplano, preparar un pastel y ejecutar una sonata de Beethoven. Es conocido que las computadoras pueden controlar señales de tráfico, líneas de producción y plantas químicas. Pueden llevar las revisiones de vuelos en líneas aéreas, controlar robots y producir nominas. Existen algoritmos para preparar una taza de café, determinar cual es el mayor de un conjunto de números, descubrir si un número es primo o no o no primo e imprimir el máximo común divisor de 2 números. Desde la época escolar se recuerda que existen algoritmos para sumar, resta, multiplicar y dividir números enteros y para calcular raíces cuadradas. Sin duda existen algoritmos para calcular logaritmos, determinar la frecuencia de las palabras en un fragmento dado de texto y controlar un submarino nuclear. Existen trabajos que las computadoras no pueden realizar. Hay muchas cosas que una computadora no puede hacer. En realidad, el número de cosas que pueden calcularse o computarse es infinitesimal en comparación con el número de cosas que a uno le gustaría calcular, las computadoras no pueden hacer muchas cosas.

Historia de la Computabilidad

La idea de disponer de un algoritmo, o receta para efectuar alguna tarea, ha existido durante miles de años. También durante muchos años la gente creyó que si cualquier problema podía iniciarse de manera precisa, entonces con suficiente esfuerzo seria posible encontrar una solución con el tiempo(o tal vez una prueba de que no existe solución podría proporcionarse con el tiempo). En otras palabras, se creía que no había problema que fuera tan intrínsicamente difícil que en principio nunca pudiera resolverse.

Uno de los grandes promotores de esta creencia fue el famoso matemático David Hilbert. En cierta ocasión afirmo:

“Todo problema matemático definido debe ser necesariamente susceptible de un planteamiento exacto, ya sea en forma de una respuesta real a la pregunta planteada o debido a la constatación de la imposibilidad de resolverlo, a lo que se debería la falla necesaria de todos los intentos… una de las cosas que nos atrae mas cuando nos dedicamos a un problema matemático es precisamente que dentro de nosotros siempre escuchamos la llamada: e aquí el problema, busca la solución; puedes encontrarla por pensamiento puro, ya que en matemáticas no existe cosa alguna que no pueda conocerse. ”

La meta de Hilbert era crear un sistema matemático formal en el que todos los sistemas pudieran plantearse con precisiones y términos de proposiciones que fueran verdaderas o falsas. Su idea era encontrar un algoritmo que, dada cualquier proposición en el sistema formal, determinara si esa proposición era o no verdadera. Si Hilbert hubiera logrado este objetivo, entonces cualquier problema que estuviera bien definido podría haberse resuelto simplemente al ejecutar el algoritmo. Al decidir la verdad de una proposición dada en el sistema formal, Hilbert lo denominó entscheidungsproblem, considerándolo como un problema abierto fundamental en matemáticas.

Por desgracia para el objetivo de Hilbert, en la década de 1930 se produjo una serie de investigaciones que mostraron que el entscheidungsproblem no es computable. Es decir, no existe algún algoritmo del tipo que buscaba Hilbert. Un cínico podría decir que los matemáticos dieron un suspiro de alivio, porque si hubiera tal algoritmo, todos se quedarían sin trabajo en cuanto se le encontrara. Sin embargo a los matemáticos les sorprendió este notable descubrimiento.

Las primeras noticias del descubrimiento surgieron en 1931 cuando Kurt Gödel publicó su ahora famoso “teorema de la incompletez”. Entre otras cosas, este teorema mostró que no existe algún algoritmo cuya entrada puede ser cualquier no verdad. Siguiendo cerca de Gödel otros matemáticos más tales como Alonso Church, Stephen Kleene, Mil Post, Alan Turing y muchos otros, encontraron más problemas que carecían de solución algorítmica. Tal vez la característica más notable de estos primeros resultados sobre problemas que no pueden resolverse por medio de las computadoras es que se obtuvieron en la década de 1930 antes de que se hubieran construido las primeras computadoras.

Tesis de Church-Turing.

Existe un obstáculo importante al probar que no existe un algoritmo para una tarea específica. Primero es necesario saber con exactitud que significa algoritmo. Cada uno de los matemáticos mencionados anteriormente había superado este obstáculo, cada definiendo “algoritmo” de una manera diferente. Gödel definió un algoritmo con una secuencia de reglas para formar funciones matemáticas complicadas a partir de funciones matemáticas más simples. Church utilizó un formalismo denominado calculo lambda, mientras que Turing empleo una maquina hipotética conocida como máquina de Turing. Turing definió un algoritmo como cualquier conjunto de instrucciones para su máquina simple.

Entonces, ¿por qué debe cualquiera dar atención a resultados acerca de algoritmos definidos en formas tan diversas y oscuras? La respuesta es que todas las definiciones en apariencia diferentes y creadas de manera independiente resultan equivalentes. Esto es, si algo puede calcularse a partir de un algoritmo definido de una forma, entonces también puede calcularse a partir de un algoritmo definido en cualquiera de las otras formas. Conforme los investigadores se dieron cada vez mas cuanta de esta equivalencia en la década de 1930, se creyó en forma amplia en las 2 proposiciones que siguen:

- Todas las definiciones razonables de “algoritmos” conocidas hasta el momento son equivalentes.

- Cualquier definición razonable de “algoritmo” que se legue a dar, a su vez será equivalente a definiciones ya conocidas.

Estas creencias han llegado a denominarse Tesis Church-Turing en honor a dos de los primeros trabajadores que se dieron cuenta de la naturaleza fundamental del concepto que habían definido juntos. Hasta el momento, no ha surgido evidencia en contra y se acepta ampliamente la Tesis de Church-Turing.

La Tesis mencionada tan sólo anuncia que se considera tener una buena definición para lo que es un algoritmo. Cualquiera tiene una sensación intuitiva acerca de lo que significa efectuar una tarea en la forma rutinaria o mecánica. Las personas tienen un manejo intuitivo del concepto de plantear un conjunto de instrucciones o pasos para efectuar alguna tarea y dar después las instrucciones a una persona o máquina para solamente ejecución sistemática. A tal conjunto de instrucciones a lo que se considera como algoritmo y la Tesis Church-Turing asegura que las definiciones precisas de algoritmo que se utilizan en las ciencias de la computación en realidad coinciden con estas ideas informales que poseen las personas. Abreviando, se cree que siempre que se escriba algún conjunto de pasos que se consideren podrían ejecutarse de una manera puramente sistemática, entonces existe un algoritmo formal en el sentido que da la ciencia de la computación a la palabra para la misma tarea.

En un planteamiento moderno, es posible definir algoritmo como cualquier cosa que pueda ejecutarse en una computadora. Por fortuna, la computadora que se elija no importa para la definición, ya que cualquier algoritmo que pueda implantarse en una computadora también puede implantarse en cualquier otra. Esto se cumple debido a que todas las computadoras pueden simularse unas a otras. Es decir, dadas 2 computadoras cualesquiera es posible escribir un programa para una de ellas que pueda comprender y ejecutar cualquier programa escrito para la otra. A tal programa se le denomina intérprete (o simulador o programa universal). La equivalencia entre todas las computadoras modernas, y su equivalencia con las máquinas de Turing y los otros numerosos medios de definir algoritmos, es una evidencia más de la Tesis Church-Turing.

La existencia de intérpretes, según se analizó antes, es en sí misma una propiedad interesante y notable de los algoritmos. Aún no es auto-evidente, es verdadero para cualquier lenguaje de programación que existe un intérprete que, dada la descripción de cualquier programa en el lenguaje, pueda simular ese programa. Por tanto, el intérprete puede efectuar cualquier tarea que cualquier otro programa pueda realizar. Esta notable propiedad de los algoritmos se denomina universalidad.

En términos informales, universalidad significa que cualquier computadora es equivalente a todas las otras en el sentido de que todas pueden efectuar las mismas tareas. Entonces, ¿por qué las personas eligen una computadora y no otra? La razón es que ciertas computadoras corren mas rápido que otras, algunas son más fáciles de programar, otras ya tienen programas escritos para ellas y puede resultar poco económico escribir los programas para otra computadora, y algunas tienen más memoria de manera que pueden ejecutar más programas largos con mayor velocidad. Entonces, aún cuando todas las computadoras pueden realizar las mismas tareas, no necesariamente consumen la misma cantidad de recursos al efectuar una tarea dada.

Problemas No Computables

Problemas de Detención

Existen muchos problemas que son no computables. Esto es, no hay un algoritmo para resolver tal problema. Este es un enunciado muy fuerte. Se esta afirmando algo mucho mas profundo que cuándo se dice que no se conoce un algoritmo para resolver el problema. Se está indicando que nunca se conocerá tal algoritmo: que nunca será posible conocerlo debido a que no existe. Un problema no computable es el de Hilbert y Gödel referente a las superaciones fundamentales

con números. A continuación vamos a describir un problema en apariencia simple de la ciencia de la computación y se prueba que ningún algoritmo puede resolverlo.

Un problema común entre las instalaciones de computadoras de todo el mundo es que al escribir programas las personas cometen errores que a menudo impiden que los programas terminen. En el habla común los programadores dicen “¡mi programa entró en un ciclo infinito!” Resulta claro que seria beneficioso si los programadores pudieran detectar la existencia de ciclos infinitos en sus programas antes de desperdiciar recursos de la computadora al ejecutarlos. Por lo tanto el problema que sería conveniente resolver es el de determinar si un programa arbitrario contiene un ciclo infinito. Planteando esto de otra forma, el problema consiste en determinar si un programa arbitrario se detiene o no. A esto se le denomina problema de detención. Su solución es un algoritmo que, dado un programa arbitrario P y sus datos de entrada D, puedan indicarnos si P con el tiempo se detendrá o no al ejecutarse con los datos de entrada D.

Por el momento la solución al problema de detención que se utiliza en la mayoría de las instalaciones de computadora es registrar el tiempo que tarda cada programa mientras se está ejecutando y abortar de manera forzosa el programa si éste utiliza más tiempo del que se le asignó. Sin embargo, ésta es una solución indeseable por dos razones. En primer lugar, los programas que no terminan desperdiciarán todo el tiempo que se les haya asignado. En segundo lugar, puede suceder en ciertos programas que el programador no pueda calcular el tiempo necesario y por tanto un programa podría abortarse poco antes de que se detuviera con éxito de otra manera.

Entonces, se podría esperar que las instalaciones en todo el mundo invirtieran considerables esfuerzos intentando plantear un algoritmo para resolver el problema de detención. Si lo están haciendo, desperdician su tiempo porque no existe tal algoritmo. El problema de detención es no computable. Esto puede probarse como sigue.

Considérese por el momento que existe un algoritmo para resolver el problema de detención. Denótese este algoritmo como pruebadetención. Como se mencionó antes, el algoritmo tiene dos entradas P y D de manera que pruebadetención (P,D) imprimen la respuesta “bien” si el programa P terminara al ejecutarse con datos de entrada D, e imprime “mal” de otra manera. En la figura de abajo se ilustra la acción de pruebadetención.

P D P

¿Se detiene P(D)? ¿Se detiene P(P)?

Sí No Sí No

Dar salida a “BIEN” Dar salida a “MAL” dar salida a “BIEN” dar salida a “MAL” Y detenerse y detenerse y detenerse y detenerse

Ya que pruebadetención prueba la terminación de un programa P para cualesquiera datos D, es posible utilizarlo para construir un algoritmo más limitado que pruebe la terminación de P cuando los datos son P mismo. Un programa es una representación de un algoritmo y simplemente consta de una secuencia de caracteres (tales como letras y dígitos). Cualquier secuencia de caracteres puede ser la entrada a un programa de computadora. Si el programa puede o no hacer algo razonable con la entrada es otro asunto. En realidad existen muchos programas de interés práctico cuya entrada es una secuencia de caracteres que representan otro programa: son ejemplos de esto compiladores y editores.

Se denotará como prueba detención a esta versión limitada dper uebadetención.

Nuevapruebadetención puede escribirse como

Module nuevapruebadetención(P)

{Verificar si el programa P se detiene si se ejecuta con los datos P}

pruebadetención(P,P)

Si se considera que existe un algoritmo pruebadetención y que por tanto existe nuevapruebadetención, es posible construir el algoritmo que sigue, denominado divertido, que tiene sólo una entrada P.

Module divertido(P)

{A fin de escribir este módulo se considera que existe pruebadetención}

if nuevapruebadetención(P) da como salida “MAL”

then detención

else ciclo interminable

P divertido

¿Se detiene P(P)? ¿Se detiene divertido(divertido)?

Sí No Sí No

Ciclo interminable detención ciclo interminable detención`

En la figura de arriba se ilustra la acción del algoritmo divertido .

Por último, se considera lo que sucede durante la ejecución de divertido(divertido): esto es, durante la ejecución de divertido con su propio texto de programa como entrada P. (Esto es legítimo ya que P puede ser cualquier secuencia de caracteres.) La ejecución de divertido(divertido) se ilustra en la figura anterior. Esta figura demuestra con claridad una contradicción, ya que ilustra por una parte que si divertido(divertido) cae en un ciclo infinito, entonces se detiene. La contradicción sólo puede resolverse al admitir que el algoritmo divertido no puede existir. Sin embargo, la única consideración que se hizo al obtener divertido fue que pruebadetención existía. Por ende si divertido no puede existir entonces tampoco puede existir pruebadetención. Por tanto se ha demostrado que no puede existir algoritmo alguno pruebadetención para resolver el problema de detención y por tanto el problema de detención no es computable. Se ha mostrado que no existe algoritmo que pueda resolver el problema de detención. ¿qué significa esto? Es seguro que existen algunos programas que sean tan simples que resulte obvio si se detienen o no. Desde luego los hay, pero existen muchos otros que de ninguna forma son tan obvios. Por ejemplo, considérese un algoritmo para probar la verdad del último teorema de Fermat. En este teorema se enuncia que no existen enteros positivos a, b y c tales que a_+b_=c_ . Por el momento no se conoce prueba a favor o en contra de este teorema, aunque Fermat afirmó tener una prueba. Un posible algoritmo para probar el teorema es Module fermat(n) {Prueba el último teorema de Fermat con la entrada n } repeat para a = 1, 2, 3,…… repeat para b = 1, 2, 3, …., a repeat para c = 2, 3, 4, …., a + b if a_+b_=c_ then dar salida a a, b, c y 2 y detenerse El algoritmo prueba de forma exhaustiva todos los enteros positivosa , b y c tales que a_+b_=c_. Si el algoritmo se detiene para una entrada específica n<2 entonces se habrá probado que el último teorema de Fermat es falso. Resulta fácil ver que el algoritmo se detendrá cuando la entrada n es 1, ya que cuando a=1, b=1 y c=2 se sabe que a1+b1=c1. De manera semejante, cuando la entrada n es 2 resulta fácil determinar que el algoritmo se detendrá, ya que a+b=c cuando a=3, b=4 y c=5. Cuando la entrada n es 3 no resulta tan fácil determinar si el algoritmo se detendrá o no. Sin embargo, con ingenio es probar que el algoritmo nunca se detendrá. ¿Qué sucede cuando n=37? De nuevo, una gran cantidad de ingenio humano pude mostrar que el algoritmo nunca se detendrá. ¿Qué pasa si n es muy grande? Por el momento nadie lo sabe. El ejemplo ilustra que en algunos casos el problema de detención es fácil de resolver. En otros es muy difícil, y se necesita mucha creatividad. En algunos casos más, tal como una entrada muy grande al algoritmo anterior, el problema de detención aún está por resolverse. El punto importante es que no existe un método puramente mecánico (esto es, no hay un algoritmo) que garantice que resuelva el problema de detención en todo caso. Desde luego, es posible diseñar un algoritmo que resuelva el problema de detención en algunos casos, pero es seguro que el algoritmo fallará con algunas otras entradas. En realidad no es tan difícil mostrar que cualquier algoritmo propuesto para el problema de detención fallará cuando Pág. 7 se tenga una cantidad infinita de entradas, resulta aún más interesante el hecho de que existe un algoritmo que, dado cualquier algoritmo propuesto para el problema de detención, puede producir una entrada en la que fallará el algoritmo propuesto, si no que no es muy difícil determinar en donde fallará. En este análisis se ha manifestado la diferencia entre un algoritmo de rutina y la aplicación de la creatividad humana a la solución de un problema. Descubrir Problemas No Computables Acaba de considerarse un problema que carece de solución algorítmica. El problema de detención no puede resolverse por medio de cualquier programa escrito en cualquier lenguaje para cualquier computadora. La pregunta es espontánea, a la que ahora se pasará es qué otros problemas no son computables. El método de prueba de la sección anterior (diagonalización que está relacionado con la prueba de Cantor de que existen más números reales que enteros), es tedioso y tal vez difícil de seguir. Por tanto, en vez de repetir una prueba semejante para cada problema no computable, tan solo se mostrará que si el problema de que se trata fuera computable, entonces también lo sería el problema de detención. Desde luego se sabe que el problema de detención no es computable por lo que tampoco lo será el problema de que se trate. Recuérdese que el problema de detención consiste en determinar si un programa arbitrario P se detendrá o no al ejecutarse con datos arbitrarios de entrada D. Una cuestión relacionada es si un programa arbitrario P se detendrá o no con todas las entradas. A esto se le denomina problema de totalidad. Se dice que P es total si P(D) se detiene para todos los datos de entrada D. No es sorprendente que el problema de totalidad sea no computable. De otra forma, dados P y D cualesquiera, simplemente se podría construir un programa especial para P y D que no tomara en cuenta su entrada y simulara P(D). Este programa especial se denominará divertidopd y se escribe module divertidopd(I) {I es la entrada, pero el módulo no la emplea} se simula el programa P con la entrada de datos D Ahora preguntar si divertidopd es total equivale a preguntar si P(D) se detiene. De manera que un algoritmo para el problema de totalidad también proporcionaría el algoritmo que sigue para el problema de detención. module pruebadetención(P,D) {A fin de escribir este módulo se considera que existe un algoritmo para el problema de la totalidad} construye el texto del programa divertidopd if divertidopd es total then dar salida a “BIEN” y detenerse else dar salida a “MAL” y detenerse Sin embargo, se sabe que no existe algoritmo para el problema de detención. En consecuencia, la consideración de que existe un algoritmo que resuelva el problema de totalidad es falsa. Por tanto se ha probado que el problema de totalidad no es computable. Otro problema no computable surge en el problema de una compañía que está instalando una nueva computadora. Supóngase que la compañía tiene un gran número de programas que han estado corriendo libres de errores durante años en la computadora anterior. Los programadores acaban de escribir un conjunto de nuevos programas para las mismas tareas que se correrán en la nueva computadora. ¿Cómo es posible que la compañía se asegure de que los nuevos programas sean tan confiables como los anteriores? Resulta claro que la compañía necesita un algoritmo que tome dos programas cualesquiera, uno anterior y uno nuevo, y los compare para determinar si efectúan el mismo trabajo (es decir para la misma entrada produzcan la misma salida). A esto se le denomina problema de equivalencia. Por desgracia, el problema de equivalencia no es computable. Dicho de otra forma, dado cualquier P, podría construirse simplemente para ese P un programa especial que simule P y dé a “13” si P se detiene con el tiempo. (Desde luego si P no se detiene, el programa que efectúa la simulación tan solo continúa simulando P para siempre.) A este programa especial podría denominársele divertidop y escribirse module divertidop(D) {Da salida a “13” si P(D) se detiene alguna vez} simular el programa P con los datos de entrada D {el paso anterior puede entrar en un ciclo interminable, pero si no lo hace entonces…} Pág. 8 dar salida a “13” Considérese ahora un programa simple que siempre da salida a “13” module simple(D) {D es la entrada, pero el modulo no la toma en cuenta dando salida a “13”} salida “13” Ahora preguntar si divertidop es equivalente a simple es lo mismo que preguntar si P es total. La razón es que si P se detiene con toda entrada, entonces divertidop dará salida a “13” con toda entrada, mientras que si existe alguna entrada para la que P no se detiene, entonces divertidop no se detendrá y no dará salida a “13” con esa entrada. De manera que un algoritmo para el problema de equivalencia también proporcionará un algoritmo en el problema de totalidad como sigue: module total(P) {A fin de escribir este modulo se considera que existe un algoritmo para el problema de equivalencia.} construir el texto del programa divertidop construir el texto del programa simple if divertidop y simple son equivalentes then dar salida a “P es total” else dar salida a “P no es total” Sin embargo, se probó antes que no existe un algoritmo para el problema de totalidad. Por tanto la consideración de que existe un algoritmo para el problema de equivalencia es falsa. Por ende se ha probado que no existe algoritmo para resolver el problema de equivalencia. Ya por último, mencionamos los cuatro últimos grupos de problemas: • Dadas dos gramáticas de contexto libre arbitrarias, el asunto de si representan o no el mismo lenguaje de programación es no computable. En realidad, no existe algún algoritmo para indicar si existe o no cualquier secuencia de caracteres que sea gramaticalmente correcta en ambos lenguajes. Al menos podría esperarse que, dada una gramática arbitraria de contexto libre, sea posible determinar si existe cualquier secuencia no gramatical de caracteres. Pero ni siquiera esto es computable. • El problema de la palabra para Grupos.- Dado un subconjunto S de elementos de un grupo G, se trata de decidir si una expresión compuesta por elementos de S y con las operaciones del grupo es igual al elemento neutro del grupo. Durante muchos años se buscaron ejemplos de grupos finitamente presentados para los que este problema fuese indecidible. La existencia de uno de estos grupos fue encontrada por Novikov en 1955 y por Boone en 1957. En el álgebra moderna hay abundantes ejemplos de interesantes problemas no computables; una gran cantidad de ellos sobre propiedades de palabras o generadores semejantes al problema de la palabra para grupos. • Décimo problema de Hilbert. Una ecuación diofántica es la ecuación de los ceros enteros de un polinomio con coeficientes enteros. El décimo problema de Hilbert, propuesto en 1900, pregunta si hay un procedimiento efectivo que determine si una ecuación diofántica tiene o no solución. Y Matiyasevich demostró en 1970 que este problema no tiene solución. • Decibilidad de las teorías lógicas. El desarrollo de la teoría de la computabilidad ha ido íntimamente ligado al desarrollo de la lógica matemática. Esto ha sido así porque la decibilidad de los distintos sistemas lógicos es una cuestión fundamental. Es bastante fácil ver que el cálculo proposicional es decidible. Church y Turing demostraron en 1936 que el cálculo de predicados no era decidible. Por otro lado, para cada una de las distintas teorías se ha ido estudiando su posible decibilidad. Como ejemplo más ilustrativo, Tarski demostró que la teoría de los números reales era decidible. Problemas No Computables desde la Máquina de Turing El Problema de Detención La Máquina de Turing es el modelo matemático formal del concepto de algoritmo. Así que un lenguaje que no se puede resolver por Turing no puede ser resuelto por ningún algoritmo: puede Pág. 9 no haber una forma general y sistemática de expresar que cadenas están en el lenguaje y cuales no. El primer lenguaje que no puede ser resuelto por Turing que encontramos consiste en las codificaciones de ciertas máquinas de Turing; desde un punto de vista práctico, éste es un ejemplo artificial poco satisfactorio. Pero podemos demostrar que, como consecuencia de la no resolución de este lenguaje, una variedad de lenguajes más naturales que describen las máquinas de Turing y gramáticas libres de contexto deben ser también no resolutivas. Según la teoría de Church, la no resolución de estos lenguajes implica que las correspondientes preguntas no pueden ser respondidas mediante algoritmos de ningún tipo. Por ejemplo, siendo K aceptable por Turing, pero no resolutiva por éste, podemos ver K como un diccionario infinito que responde a preguntas del tipo: ¿acepta la máquina de Turing M la entrada w? Ya que no hay ninguna máquina de Turing que decida K, podemos concluir que no hay algoritmo que resuelva, , para una máquina de Turing arbitraria y una entrada w, si M acepta o no w. Éste es uno de los problemas no computables más famosos: el problema de detención(halting problem) para máquinas de Turing. Nótese que este resultado imposible de resolver de ninguna manera implica que no puede haber ciertas circunstancias bajo las que es posible predecir si una máquina de Turing parará en una cadena de entrada. Podríamos examinar la codificación de la máquina, por ejemplo, para comprobar si el estado de parada h esta representado en algún lugar; si no, la máquina no puede aceptar ninguna cadena de entrada. Estoe y otros análisis más ejemplos podrían ofrecer más información; pero los resultados de esta sección afirma que cualquiera de estos análisis deben finalmente ser interminables u ofrecer resultados incorrectos: no hay ningún método completamente general que resuelva todos los casos correctamente. Además, hay ciertas máquinas particulares para las que no hay un método general para decir, dada una entrada, si la máquina aceptará o parará en tal entrada. Esto surge del hecho de que K es aceptable por Turing pero no resolutiva. Así que si M es una máquina de Turing que acepta K, entonces no puede existir una máquina de Turing que resuelva si una entrada arbitraria dada es aceptada por M o no. A partir de esto podemos afirmar: • No hay ningún algoritmo para determinar, dada una máquina M y una entrada w, si M acepta a w. • Para cierta máquina de Turing fijada M, no hay ningún algoritmo para determinar, dada una entrada w, si M acepta a w. Otros Problemas que No Pueden Ser Resueltos por Máquinas de Turing Los siguientes problemas sobre máquinas de Turing no son computables: • Dada una máquina de Turing M, ¿parará en la cinta vacía? • Dada una máquina de Turing, ¿hay una cadena en la que M parará? • Dada una máquina de Turing M,¿parará en cada cadena de entrada? • Dadas dos máquinas de Turing M1 y M2, ¿pararán en las mismas cadenas de entrada? • Dada una máquina de Turing M, ¿es el lenguaje M libre de contexto? ¿Es resolutivo por Turing? Casi ninguna pregunta no trivial que alguien podría preguntar sobre máquinas de Turing es improbable tener una respuesta que venga dada por un algoritmo. Ya que hemos considerado las máquinas de Turing como versiones formales de algoritmos, esto supone que muchas preguntas sobre algoritmos no pueden ser respondidas por algoritmos. Una pregunta típica de este tipo es la última. Traducida a términos más generales, ésta dice que cualquier tipo de lenguaje puede ser usado para expresar todos los procedimientos computacionales, y no hay forma sistemática de decir si un conjunto de instrucciones dado realmente describe un procedimiento que garantiza terminar y ofrecer una respuesta, no importa que entrada se dé. Evidentemente, resultados implican que las posibilidades son inherentemente limitadas para programas computacionales que analizan y predicen el comportamiento de otros programas computacionales. Por ejemplo, el problema de verificación del programa, que es, determinar si un programa computacional funciona correctamente bajo todas circunstancias, no puede resolverse en general, aunque se ha empleado mucho esfuerzo en el desarrollo de métodos para verificar tipos de programas restringidos. Problemas No Computables Sobre Gramáticas Libres de Contexto Debido a la estrecha relación entre gramáticas y máquinas de Turing, la no resolución de algunos problemas sobre gramáticas es fácil de demostrar. Cada uno de los siguientes problemas son no computables: Pág. 10 • Para una gramática arbitraria dada G y una cadena w, determinar si w pertenece a L(G). • Para cierta gramática fijada G y una cadena arbitraria w, determinar si w ι L(G). • Para dos gramáticas arbitrarias G1 y G2, determinar si L(G1)=L(G2). • Para una gramática arbitraria G, determinar si L(G)= Λ Cualquier procedimiento de decisión de estos problemas inmediatamente implicaría la resolución de un problema no computable sobre máquinas de Turing. Por ejemplo, supongamos que el primero fuera computable. Entonces podríamos proceder como sigue a determinar, para cualquier máquina de Turing M y una cadena w, si M acepta a w. Simplemente produciríamos una gramática G tal que L(G) sea el lenguaje aceptado por M. Entonces en vez de preguntar si M acepta a w, preguntar si w ι L(G); las dos preguntas tienen la misma respuesta. Así que la resolución del problema primero contradiría el teorema que dice que el siguiente problema, antes expuesto, no es computable: dada una máquina de Turing M y una entrada w, ¿para M en la entrada w?. Ocurriría lo mismo con el resto de los problemas.

Estoy invitando a todos los maestros y profesionales de esta area y/o carrera a colaborar construyendo este sitio dedicado a esta hermosa y util profesion aportando el material apropiado a cada uno de los mas de 1,000 temas que lo componen.

Tambien los invito a aportar material a los mas de 30,000 temas que constituyen las 30 carreras profesionales que se imparten en los Institutos Tecnologicos de Mexico y se encuentran en este sitio.

www.MiTecnologico.com es un esfuerzo personal y de muchos amigos de MEXICO y el Mundo Hispano por devolver algo de lo mucho que hemos recibido en el proceso de la educacion superior, saludos Prof Lauro Soto, Ensenada, BC, Mexico

PARA EMPEZAR SOLO USAR OPCION edit ABAJO Y EMPIEZA A CONSTRUIR , SALUDOS Y MUCHAS GRACIAS

Competencias Digitales (Tic’s Basicas) a practicar con este TEMA:

  • Usar (click en )www.Google.com para buscar y localizar UN material academico apropiado y que se pueda recomendar para el tema, ver VIDEO BUSQUEDAS abajo en esta pagina.
  • En el post ( o tema ) apropiado en el Libro de Blogger, pegar el material localizado y que se recomienda para este tema, ver VIDEO BLOGGER abajo en esta pagina.

pd: Recordar incluir la fuente del tema usando el formato de citacion apropiado, ver VIDEO WIKIPEDIA abajo en esta pagina.

  • En el editor de Blogger usar colores para destacar los parrafos mas importantes y usar subrayados para las citas mas relevantes.
  • En el post ( o tema ) apropiado en el libro en Blogger, para incluir ecuaciones o notacion matematica se debera usar el icono del editor de Blogger IMAGE y construir esta notacion matematica con imagenes Latex, ver VIDEO LATEX ABAJO.
  • Construir al final y despues de la fuente del material, un breve resumen ( no mas de 2–3 parrafos) explicando palabras propias el contenido del tema.

pd: Se pueden usar alguna de las citas que encontradas dentro del tema, solo recordar encerrarla entre comillas.

pd: Se pueden usar tambien cambios en fonts para darle mas visibilidad, consistencia y relevancia al resumen del tema.

  • PUNTOS EXTRAS Si se usa una segunda fuente valiosa de informacion y recordar encadenar los dos materiales mediante uno o dos parrafos apropiados.
  • Enviar a el maestro o compañeros un correo electronico que incluya la liga a el tema en blogger para revision, recomendacion, sugerencias y evaluacion, ver VIDEO LIGAS GMAIL abajo.
  • Sacar una cuenta (click en)http://docs.google.com, usando el correo de Gmail y tratar de conseguir el mismo usuario que se construyo en Gmail y Blogger ver VIDEO GOOGLE DOCS abajo en esta pagina.

pd: Si ya se tiene una cuenta ignorar esta competencia digital.

pd: Google Docs es el equivalente a OFFICE pero con la caracteristica que todos sus componentes ( procesador de palabras, presentacion electronica y hoja de calculo) estan completamente en internet, es decir todos los archivos o material estaran en linea, seguros y siempre disponibles, ademas de que se pueden trabajarlos desde cualquier pc, ya sea la personal, la del laboratorio de la escuela o la de un lugar publico como la biblioteca o un cafe internet.

  • Construir una Presentacion Electronica ( usando muy pocos slides) del tema en GOOGLE DOCS e incrustrarla en el tema de bloger ver VIDEO GOOGLE DOCS en esta pagina abajo.

pd: Recordar que una presentacion electronica, es solamente un resumen muy condensado del tema ( o mapa o guia mental ), que ayuda a recordar los elementos y conceptos mas basicos del tema, cuando se estan exponiendo frente a un grupo.

pd: No olvidar incluir un primer slide con el titulo de la presentacion electronica, un segundo slide con un indice de la presentacion electronica y un ultimo slide con dos o tres parrafos de conclusiones y bibliografia.

  • Buscar en Google Imagenes o www.Flickr.com o www.PhotoBucket.com una galeria de fotos o de imagenes apropiadas al tema actual,
  • Para los casos de Photobucket y Flicker, ambos sitios proporcionan ligas a sus imagenes y tambien objetos (los recuerdan??), que se pueden incluir en el tema del libro apropiado en Blogger.

pd: para estos sitios deberan obtener una cuenta usando el correo de gmail y de preferencia obtener el mismo usario que se ha venido manejando a lo largo del curso.

pd: Tratar de usar resoluciones y tamaños de imagenes chicos o medianos, recordar que todo este material termina en el post del tema en Blogger y esa pagina no tiene mucho espacio para desplegar fotos o imagenes.

pd: El formato apropiado para fotos o imagenes es JPG, tratar de no usar otros formatos.

pd: Se puede construir y conseguir esta coleccion o galeria de imagenes con:

1) Usando Google Imagenes, recordar conseguir solo imagenes que tengan permiso de publicacion abierto, no usar imagenes o fotos que tengan derechos reservados.

pd: Estas fotos almacenarlas en un folder en el desktop o escritorio de su computadora y subirlas a el post en blogger usando el icono IMAGE del editor de Blogger.

2) Flickr y Photo Bucket tambien tienen una gran cantidad de imagenes que se pueden usar o mejor dicho enlazar a el tema o post en Blogger.

3) Tambien se puede usar la camaras digitales o las camaras de sus telefonos celulares.

4) Tambien se puede usar el programa o aplicacion llamado Srip32.exe( solo buscar srip32 en google) bajarlo e instalarlo, este programa permite capturar una pantalla de la pc, es decir si se encuentra un sitio con imagenes o incluso texto apropiado o relevante al tema, capturar la pantalla con srip32 y ya se tendra la imagen, ver VIDEO Srip32 abajo.

  • Incluir al menos una imagen de cada uno de los dos sitios (flickr y Photobucket) en el tema o post que se esta construyendo en Blogger.
  • PUNTOS EXTRAS Si se incluyen una galeria completa de imagenes apropiadas desde cualquiera de estos sitios de FLICKR o Photobucket.
  • Sacar una cuenta (click en)www.DivShare.com, usando el correo de Gmail y tratar de conseguir el mismo usuario que se consiguio en Gmail y Blogger y Flickr ver VIDEO DIVSHARE abajo en esta pagina.

pd: Si ya se tiene una cuenta ignorar esta competencia digital.

pd: Usar Divshare para almacenar material en audio (MP3) apropiado a el tema ( no usarlo para almacenar material comercial o les suspenden la cuenta)

pd: El material en Audio, con formato MP3 se debera producir usando un microfono en la pc y programas de aplicacion apropiados, llamados editores de audio, un ejemplo de ellos es el SOUND RECORDER que ya viene en Windows, pero se recomienda usar mejor AUDACITY ( solo buscar en google AUDACITY) bajarlo e instalarlo, ver VIDEO AUDACITY abajo.

  • Crear al menos dos archivos de audio mp3:

1) El primero de ellos sera la lectura completa de este tema en voz apropiada. ( o aprender a editar con audacity la voz)

2) El segundo de ellos sera un resumen del tema. ( buena voz o editarla con audacity)

3) Ambos archivos subirlos a Div Share (recordor que tienen que ser MP3) y el reproductor que proporciona gratis Div Share, ver VIDEO DIVSHARE abajo e insertarlo en el lugar apropiado del tema que se esta construyendo en Blogger.

4) Ejemplo del reproductor incrustado en una pagina:

  • Sacar una cuenta (click en)www.YouTube.com, usando el correo de Gmail y tratar de conseguir el mismo usuario que se consiguio en Gmail y Blogger y Flickr.

pd: Si ya se tiene una cuenta ignorar esta competencia digital.

  • Para producir video se pueden usar tres fuentes:

1) Localizar Videos apropiados en Youtube.

2) Usar nuestras camaras digitales o nuestros telefonos celulares para producir video.

3) Producir un video de la propia pantalla de la computadora ( muy similar a lo que se hizo con Srip32) pero usando un programa especializado en video, tal como CAMSTUDIO (click en www.CamStudio.org) bajar e instalar ( no olvidar bajar e instalar el CODEC que esta abajo en el mismo sitio.

3.1) para Usar Camstudio solo recordar que es muy similar a Srip32 Solo que el resultado final es un archivo de video AVI.

  • Producir un video de resumen del tema (usar camstudio con el fondo de la pagina con el tema e irlo comentando en voz apropiada)
  • Producir un video en vivo con la exposicion del tema ( pueden usar la presentacion electronica de fondo o cualquier otro material, pizarron, filminas, rotafolios, etc.)
  • Subir los videos a su cuenta en Youtube e incluirlos o ligarlos en la pagina en Blogger, tambien los pueden subir directamente a BLOGGER ver VIDEO BLOGGER VIDEO abajo.

Saludos y suerte prof Lauro Soto, Ensenada, BC, Mexico.