Autor Tema: Teorema de Gödel

0 Usuarios y 1 Visitante están viendo este tema.

13 Junio, 2009, 05:13 pm
Respuesta #50

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,346
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Aprovecho esto último que has introducido para meter un bocadillo sobre algoritmos y programas.

Me gustaría poner a prueba todo esto en un programa real de computadora.
Pero no sé qué tipo de lenguaje de programación es el "correcto", o cuáles detalles dentro del lenguaje son las que deben usarse y cuáles no.
Estaba pensando en usar Python, por ejemplo, que permite trabajar con listas de longitud que crece tanto como uno necesita.
El lenguaje C admite ingresar listas de signos como arrays de caracteres, pero el problema es que debo especificar un tamaño máximo fijo del array.
Así que habría que usar listas enlazadas, o bien ir a C++ y usar los arrays de tamaño dinámico.

Pero si empiezo a usar herramientas cada vez más potentes, o lenguajes de más alto nivel, comienza a oscurecerse lo que estoy realmente haciendo a nivel de la ''máquina'', y así no sé si estoy aún dentro de los límites en los que debo permanecer para no salirme de la teoría.

Pero para experimentar un poco, no estaría mal usar un lenguaje de alto nivel, al menos para ver qué está pasando.

¿Alguna recomendación?

(No he pedido una definición de ''máquina'' o de ''lenguaje de programación'' o de ''programa'' o de "algoritmo", porque sospecho que la cosa puede complicarse y alejarnos demasiado del tema, pero en realidad eso es lo que me gustaría tener claro)

13 Junio, 2009, 06:11 pm
Respuesta #51

Numerarius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 312
  • Karma: +0/-0
  • Sexo: Masculino
Es posible que me equivoque.

Pero me da la impresión de que demostraciones como la del teorema de Gödel y el "halting problem" de Turing, bueno, son demostraciones que utilizan el método diagonal de Cantor, y que se refieren a conjuntos infinitos. De hecho, el "halting problem" (el problema de la parada de máquina de Turing) nos dice que no hay ningún método para decidir si un programa de ordenador se pierde en un bucle infinito.

Como los programas reales sólo pueden hacer cálculos con conjuntos finitos, me da la impresión de que el teorema de Gödel o el problema de la parada no debe de ser fácil de programar en un ordenador.

pero bueno. doctores tiene la Iglesia, y seguro que otros foreros  podran explicar este punto infinitamente mejor que yo.

Un saludo.

13 Junio, 2009, 06:28 pm
Respuesta #52

Numerarius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 312
  • Karma: +0/-0
  • Sexo: Masculino





(No he pedido una definición de ''máquina'' o de ''lenguaje de programación'' o de ''programa'' o de "algoritmo", porque sospecho que la cosa puede complicarse y alejarnos demasiado del tema, pero en realidad eso es lo que me gustaría tener claro)


Esto no es ningún problema. Existe una definición estandar de algoritmo que se debe a Church y a Turing.

Incluso existen distintos tipos de funciones computables: recursivas primitivas, recursivas totales, recursivas parciales.

Estos temas bienen bien explicados, por ejemplo,  en "Teoría de la computación" de Brookshear y en "Computability" de Cutland.

13 Junio, 2009, 06:35 pm
Respuesta #53

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,346
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
De acuerdo Numerarius, el teorema de godel por sí mismo a lo mejor no pueda abarcarse en un programa de computadora, pero lo que yo deseo poner a prueba son las definiciones básicas de ''expresiones'', ''axioma'', ''demostración'', etc.
Si yo ingreso una cadena de caracteres finita, podré determinar en un número finito de pasos si es una expresión válida, un término, una fórmula, un axioma, etc.

Además, ¿cómo es posible estar hablando todo el tiempo de algoritmos, de programas de computadora, y no poder hacer ni un solo programa?
Hay ''porciones'' de todo este asunto que seguramente se pueden programar en la PC sin dificultad. Son algoritmos del tipo de reconocimiento sintáctico, que estoy seguro que te sabés de memoria.


13 Junio, 2009, 06:52 pm
Respuesta #54

Numerarius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 312
  • Karma: +0/-0
  • Sexo: Masculino

Hay ''porciones'' de todo este asunto que seguramente se pueden programar en la PC sin dificultad. Son algoritmos del tipo de reconocimiento sintáctico, que estoy seguro que te sabés de memoria.



Sí, desde luego. Hay autómatas que sí. Por ejemplo, un autómata finito, no tendría mucha dificultad en ser programado en un ordenador.

14 Junio, 2009, 12:37 am
Respuesta #55

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,346
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Numerarius, no sé si estamos hablando de lo mismo. Me imagino lo que es un autómata finito, pero no estoy seguro de lo que significa con toda exactitud.

Deseo poder expresar algoritmos ''finitarios'' en la PC, asumiendo que la memoria de la computadora puede crecer tanto como sea necesario.
La memoria RAM de una PC es de tamaño fijo, pero puedo pensar que ingreso los datos a través de un dispositivo de almacenamiento externo, como una colección de cintas o discos externos.
Si yo puedo colocar cintas o discos en serie, de modo que la capacidad de almacenamiento de datos vaya creciendo a voluntad, creo que puedo decir que mi ''máquina'' trabaja con longitud de datos potencialmente infinita, tan grande de finita como yo quiera
Tan sólo hay que lograr que la máquina que uno usa sea capaz de reconocer sin problemas que se ha agregado una nueva cinta o disco.
O sea, creo que es posible construir el símil de una máquina con memoria no acotada. ¿No es eso una máquina de Turing?
La cota real me la pondría el Universo mismo, si es que no dispongo de materia suficiente para crear más allá de \( 10^{80} \) discos duros... Pero eso no importaría mucho, porque sería una limitación de hardware y no de software: la máquina estaría configurada lógicamente para aceptar que se pueda agregar siempre un dispositivo más a la cadena en serie de cintas o discos, y se podría acceder secuencialente a ellos con la misma lógica de una lista enlazada.

El siguiente algoritmo en lenguaje C permite reconocer si un string de longitud desconocida, es o no es una expresión de un cierto lenguaje cuyos signos pertenecen al conjunto \( L = \{(,),\exists{},\Rightarrow{},-,=,x,|,0,S,+,\cdot\} \), que son los símbolos que eligió Gustavo:
Código: [Seleccionar]
#define bool unsigned int
#define false 0
#define true 1

bool is_in_L(char c)
{
  #define MAX 10
  const char L[MAX] = "()E*-=0S+."; /* Son los signos de L, y he puesto * para indicar 'flecha'. */
  unsigned short int i;
  
  for (i = 0; (i < MAX) && (c != L[i]); i++)
    ;
  if (i == MAX) return true;
  else return false;
}

bool is_in_language(char *s)
{
  /* La longitud de la cadena s es arbitrario, y en esta subrutina no hace falta especificar cotas */

  while((*s != 0) && is_in_L(*s)) /* Se usa la convención de que una cadena en C termina en su primer caracter nulo */
     ;  
   if (*s == 0) return true;   /* Si terminó la búsqueda tras el último caracter, es que s pertenece al lenguaje */
   else return false;
}

En el código que puse, se habrá notado que la función de reconocimiento no es capaz de darse cuenta si s es una cadena con longitud finita. Eso sería un problema, porque si se introduce una cadena s errónea, el programa podría no terminar.
Yo digo que esto se puede solucionar cambiando el tipo de datos char* por el de un FILE*, o sea, un archivo (de texto), ya que sabemos que los archivos ya tienen longitud finita desde el sistema operativo.
Una forma menos ''sucia'' de solucionar esto, sería irse a C++ y crear una class llamada STRING, que obligue al usuario a inicializarla en "", o sea vacía, y que el único modo de hacerla crecer sea agregando un caracter de uno en uno.
Tendríamos así un tipo de datos controlado, siempre de longitud finita, y que podría crecer tanto como haga falta.
O bien usar MATLAB o Python y aprovechar que ya tienen un manejo de listas. Un string sería una lista de caracteres, y el tamaño podría ser tan grande como haga falta.

Las subrutinas para reconocer fórmulas, enunciados, etc., podrían programarse con una filosofía similar en una computadora comùn y corriente, pudiendo tratar expresiones de tamaño finito aunque arbitrariamente grande.


14 Junio, 2009, 01:03 am
Respuesta #56

Numerarius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 312
  • Karma: +0/-0
  • Sexo: Masculino

Si yo puedo colocar cintas o discos en serie, de modo que la capacidad de almacenamiento de datos vaya creciendo a voluntad, creo que puedo decir que mi ''máquina'' trabaja con longitud de datos potencialmente infinita, tan grande  de finita como yo quiera
Tan sólo hay que lograr que la máquina que uno usa sea capaz de reconocer sin problemas que se ha agregado una nueva cinta o disco.
O sea, creo que es posible construir el símil de una máquina con memoria no acotada. ¿No es eso una máquina de Turing?
La cota real me la pondría el Universo mismo, si es que no dispongo de materia suficiente para crear más allá de [10^{80}] discos duros... Pero eso no importaría mucho, porque sería una limitación de hardware y no de software: la máquina estaría configurada lógicamente para aceptar que se pueda agregar siempre un dispositivo más a la cadena en serie de cintas o discos, y se podría acceder secuencialente a ellos con la misma lógica de una lista enlazada.







Bueno, hay determinados problemas que (al menos, por un procedimiento de fuerza bruta) no podrían decidirse con una memoria finita. o con métodos finitistas.

1) la conjetura Goldbach

2) decidir si en la expansión decimal de Pi existen n 7s seguidos.

En pura teoría, una máquina de Turing, con una cinta infinita, podría seguir funcionando durante toda la eternidad. (desde luego, esto es una idealización. Pero es que el concepto de máquina de Turing es un concepto ideal. desde luego, la memoria de un ordenador real tiene un límite).

Es una discusión interesante...

14 Junio, 2009, 02:02 am
Respuesta #57

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,346
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Entonces puede ser que lo que estoy proponiendo no es una máquina de Turing.
Si la máquina de Turing es una máquina que puede escribir en una cinta ideal infinita... entonces lo que digo es que hablemos de una máquina que está configurada para aceptar una cinta siempre finita pero expandible tanto como se quiera.
Suponer de entrada una cinta infinita para que Mr. Turing escriba todo lo que tenga ganas no es necesario.
Por lo que he visto por ahí, los programas que se le ponen a una Maquina de Turing son finitos, y proceden avanzando y escribiendo siempre por los ''casilleros'' de la ''cinta ideal'' pero tan solo de uno en uno a la vez. 
Si supongo de entrada una cinta infinita, estoy asumiendo un infinito ''actual'',
y por lo que veo, eso es lo que se trata de evitar en el Teorema de Godel, y en toda la metamatemática.
Así que la ''máquina'' tendría que escribir en una cinta ''potencialmente infinita'', o sea finita pero ampliable sin límite.
¿Sigue siendo eso una máquina de Turing?

No quiero desviarme mucho más del tema central, tan sólo deseaba una sugerencia de cómo programar correctamente una rutina de verificación de fórmulas y demostraciones en una PC, manteniendo en todo lo posible las formalidades de la metamatemática.

14 Junio, 2009, 02:13 am
Respuesta #58

Gustavo Piñeiro

  • Visitante
Así que la ''máquina'' tendría que escribir en una cinta ''potencialmente infinita'', o sea finita pero ampliable sin límite.
¿Sigue siendo eso una máquina de Turing?

Las máquinas de Turing, por definición, tienen una cinta potencialmente infinita. Los programas tienen una cantidad finita de instrucciones, cada una de una longitud finita y las entradas son siempre de longitud finita. La salida, si la hay, es finita. Cierto es que a veces una máquina puede entrar en un cómputo infinito, pero mejor sería decir, en un cómputo que nunca termina.

(Es cierto que en su metamatemática Hilbert buscaba evitar todo uso del infinito actual, esto era esencial para sus objetivos.)

Saludos.

<<                >>

14 Junio, 2009, 04:48 am
Respuesta #59

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,346
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
La implementación de una máquina de Turing no tiene por qué ser una computadora propiamente dicha.
Puede ser un sistema operativo bien diseñado, un entorno de programación adecuado, etc.
Creo que la Máquina Virtual Java es un ambiente que sirve como simil de máquina de Turing, ya que las limitaciones del Hardware se ''ocultan'' al programador. El programador cree que puede disponer de tanta memoria como le haga falta, y la máquina virtual se las arregla para ir consiguiendo recursos a medida que hacen falta.
Si la computación se concentrara en este problema, creo que hallaría una salida satisfactoria de diseño Turinguesco, incluso a nivel de Hardware, haciendo que las máquinas acepten conceptualmente tantos dispositivos como hagan falta.
Es una cuestión de diseño.

Si pensamos en memoria de una máquina de Turing como memoria RAM, se acaba el cuento, porque es finita y no crece.
Pero pensada de otra forma, con un diseño más flexible, puede implementarse en la vida real, no sólo como algo ideal.
¿No?...  ;D

(corregí lo de la palabra Java, que antes no se entendía que habia querido poner)