Lenguajes Formales y Automatas: 2007

Muestreo probabilístico

Los métodos de muestreo probabilísticos son aquellos que se basan en el principio de equiprobabilidad. Es decir, aquellos en los que todos los individuos tienen la misma probabilidad de ser elegidos para formar parte de una muestra y, consiguientemente, todas las posibles muestras de tamaño n tienen la misma probabilidad de ser elegidas. Sólo estos métodos de muestreo probabilísticos nos aseguran la representatividad de la muestra extraída y son, por tanto, los más recomendables. Dentro de los métodos de muestreo probabilísticos encontramos los siguientes tipos: El método otorga una probabilidad conocida de integrar la muestra a cada elemento de la población, y dicha probabilidad no es nula para ningún elemento. Los métodos de muestreo no probabilisticos no garantizan la representatividad de la muestra y por lo tanto no permiten realizar estimaciones inferenciales sobre la población. (En algunas circunstancias los métodos estadísticos y epidemiológicos permiten resolver los problemas de representatividad aun en situaciones de muestreo no probabilistico, por ejemplo los estudios de caso-control, donde los casos no son seleccionados aleatoriamente de la población.) >
Métodos de muestreo no probabilísticos

A veces, para estudios exploratorios, el muestreo probabilístico resulta excesivamente costoso y se acude a métodos no probabilísticos, aun siendo conscientes de que no sirven para realizar generalizaciones, pues no se tiene certeza de que la muestra extraída sea representativa, ya que no todos los sujetos de la población tienen la misma probabilidad de se elegidos. En general se seleccionan a los sujetos siguiendo determinados criterios procurando que la muestra sea representativa.

Teoria de la computabilidad

La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing. La teoría de la computabilidad se interesa a cuatro preguntas:

• ¿Qué problemas puede resolver una máquina de Turing?

• ¿Qué otros formalismos equivalen a las máquinas de Turing?

• ¿Qué problemas requieren máquinas más poderosas?

• ¿Qué problemas requieren máquinas menos poderosas?

La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen de diversos recursos en diversos tipos de máquina.

¿Qué problemas puede resolver una máquina de Turing?

No todos los problemas pueden ser resueltos. Un problema indecidible es uno que no puede ser resuelto con un algoritmo aún si se dispone de espacio y tiempo ilimitado. Actualmente se conocen muchos problemas indecidibles, como por ejemplo:

• El Entscheidungsproblem (problema de decisión en alemán) que se define como: Dada una frase del cálculo de predicados de primer orden, decidir si ella es un teorema. Church y Turing demostraron independientemente que este problema es indecidible.

• El Problema de la parada, que se define así: Dado un programa y su entrada, decidir si ese programa terminará para esa entrada o si correrá indefinidamente. Turing demostró que se trata de un problema indecidible.

• Un número computable es un número real que puede ser aproximado por un algoritmo con un nivel de exactitud arbitrario. Turing demostró que casi todos los números no son computables. Por ejemplo, la Constante de Chaitin no es computable aunque sí que está bien definido.

¿Qué otros formalismos equivalen a las máquinas de Turing?

Los lenguajes formales que son aceptados por una máquina de Turing son exactamente aquellos que pueden ser generados por una gramática formal. El cálculo Lambda es una forma de definir funciones. Las funciones que pueden ser computadas con el cálculo Lambda son exactamente aquellas que pueden ser computadas con una máquina de Turing. Estos tres formalismos, las máquinas de Turing, los lenguajes formales y el cálculo Lambda son formalismos muy disímiles y fueron desarrollados por diferentes personas. Sin embargo, ellos son todos equivalentes y tienen el mismo poder de expresión. Generalmente se toma esta notable coincidencia como evidencia de que la tesis de Church-Turing es cierta, que la afirmación de que la noción intuitiva de algoritmo o procedimiento efectivo de cómputo corresponde a la noción de cómputo en una máquina de Turing.

Los computadores electrónicos, basados en la arquitectura Eckert-Mauchly así como las máquinas cuánticas tendrían exactamente el mismo poder de expresión que el de una máquina de Turing si dispusieran de recursos ilimitados de tiempo y espacio. Como consecuencia, los lenguajes de programación tienen a lo sumo el mismo poder de expresión que el de los programas para una máquina de Turing y en la práctica no todos lo alcanzan. Los lenguajes con poder de expresión equivalente al de una máquina de Turing se denominan Turing completos. Entre los formalismos equivalentes a una máquina de Turing están: •Máquinas de Turing con varias cintas

•Máquinas de Turing con cintas bidimensionales (o una infinidad de cintas lineales)

•Máquinas de Turing con número limitado de estados y símbolos para la cinta

•Máquinas de Turing con solo dos estados

•Autómatas finitos con dos pilas

•Autómatas finitos con dos contadores

•Gramáticas formales

•Sistemas de correspondencia de Post

•Cálculo Lambda

•Funciones recursivas parciales

•Casi todos los lenguajes de programación modernos si dispusieran de memoria ilimitada

•Autómatas celulares

•El Juego de la vida de John Conway

•Máquinas de Turing no determinísticas

•Máquinas de Turing probabilísticas

•Computador cuántico

Los últimos tres ejemplos utilizan una definición ligeramente diferente de aceptación de un lenguaje. Ellas aceptan una palabra si cualquiera, cómputo acepta (en el caso de no determinismo), o la mayoría de los cómputos aceptan (para las versiones probabilística y cuántica). Con estas definiciones, estas máquinas tienen el mismo poder de expresión que una máquina de Turing.

¿Qué problemas requieren máquinas más poderosas?

Se considera que algunas máquinas tienen mayor poder que las máquinas de Turing. Por ejemplo, una máquina oráculo que utiliza una caja negra que puede calcular una función particular que no es calculable con una máquina de Turing. La fuerza de cómputo de una máquina oráculo viene descrita por su grado de Turing. La teoría de cómputos reales estudia máquinas con precisión absoluta en los números reales. Dentro de esta teoría, es posible demostrar afirmaciones interesentes, tales como «el complemento de un conjunto de Mandelbrot es solo parcialmente decidible».