Los programas While: bases para una teoría de la computabilidad

La Teoría de la Computabilidad estudia los límites teóricos de los sistemas computacionales. Uno de sus objetivos centrales consiste en clasificar los problemas en computables e incomputables, donde llamamos computable a un problema si admite solución informática. Para desarrollar estos resultados el modelo abstracto de computador más utilizado históricamente es la Máquina de Turing. Los estudiantes de Ingeniería Informática pueden percibir cierta lejanía entre el modelo teórico y los computadores reales por lo que es más adecuado utilizar un modelo más cercano a la programación como son los programas-while. Los Programas-while permiten resolver los mismos problemas que las máquinas de Turing, pero en cambio son mucho más sencillos de utilizar, sobre todo para personas que tienen una experiencia previa en la informática real, pues toman la forma de lenguaje imperativo clásico. Este texto además utiliza los Programas-while aprovechando sus ventajas y reformulándolos de manera que la computación quede definida en términos de manipulación de símbolos arbitrarios, algo que está mucho más en concordancia con la realidad informática. Además de explicar en detalle qué son los programas while y cómo se utilizan, se justifica por qué no es necesario incorporar otras instrucciones o tipos de datos.

El método de reducción en Teoría de la Computabilidad

La Teoría de la Computabilidad es una disciplina encuadrada en la Informática Teórica que tiene como objetivo establecer los límites lógicos que presentan los sistemas informáticos a la hora de resolver problemas mediante el diseño de algoritmos. Estos resultados proporcionan importantes herramientas que se utilizan para demostrar tanto la computabilidad como la incomputabilidad de muchas funciones relevantes. Los primeros problemas incomputables que se encontraron lo fueron allá por la década de los años 30. El problema de parada es el primer y más conocido ejemplo de problema no resoluble mediante técnicas algorítmicas: ningún ordenador, por muy potente que sea, puede anticipar el comportamiento de los programas en ejecución, y decidir de antemano si terminarán o no. Este problema nos proporciona un soporte intuitivo para anticipar la incomputabilidad de otros problemas relacionados y un procedimiento para resolverlos: el método de diagonalización. Sin embargo para determinados problemas también incomputables hay que recurrir a otros métodos. Este texto incluye una descripción de otra técnica básica de Teoría de la Computabilidad: la Reducción. La base del método estriba en demostrar que ciertos pares de problemas están fuertemente relacionados de modo que si el segundo tiene solución algorítmica entonces el primero debe tenerla necesariamente también. Esta relación se establece por medio de funciones transformadoras computables, que permiten convertir de manera automática las instancias positivas del primer problema en instancias positivas del segundo. Esta técnica se utiliza muy a menudo porque resulta comparativamente más sencilla que la diagonalización, ya que en general requiere menos esfuerzo para demostrar la incomputabilidad de un mismo problema.

Las secuencias didácticas de lengua: una encrucijada entre teoría y metodología

[ES] El objetivo de este trabajo es analizar secuencias didácticas(SD) para enseñar lengua/s diseñadas por profesores de educación primaria y proponer algunos indicadores que guíen a los enseñantes en la confección y validación (o autoevaluación) de las mismas. Entendemos la secuencia didáctica en el sentido de sus creadores ginebrinos, es decir, como una herramienta para la enseñanza del género textual como unidad comunicativa. El diseño de las secuencias estudiadas en este artículo se realiza a lo largo de unas sesiones de formación de profesorado; a la vista de los obstáculos que se observan en su elaboración (dificultades para explicitar la consigna, noción difusa del género textual, etc.), decidimos analizarlas a partir de unos ítems o criterios extraídos básicamente de los principios que rigen las secuencias didácticas. Pensamos que las principales dificultades derivarán de las concepciones teóricas y metodológicas previas que tienen los profesores y de una concepción disociada de la SD y del género textual. Los resultados ponen de relieve cuáles son algunos de los aspectos que merecen especial atención a la hora de diseñar secuencias didácticas y sugieren el interés de contar con unos indicadores que guíen al docente en la confección de las mismas. Eso no significa, sin embargo, que deba tratarse de una lista cerrada y, evidentemente, futuros trabajos habrán de modificarla y completarla. Hasta el momento, estos criterios nos permiten confirmar la importancia de insistir en las bases teóricas y metodológicas de las secuencias didácticas en el marco de las sesiones formativas.