Autor Tema: Teorema de Gödel

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

12 Junio, 2009, 01:47 pm
Respuesta #40

Fernando Revilla

  • Administrador
  • Mensajes: 10,851
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • Las matemáticas son demasiado humanas (Brouwer).
    • Fernando Revilla
Añadir que las reglas de deducción en el sistema formal \( \mathcal{L} \) del cálculo de predicados son:

(1) Modus ponens: De \( \mathcal{A} \) y  \( (\mathcal{A}\rightarrow{\mathcal{B}}) \) se deduce \( \mathcal{B} \) siendo \( \mathcal{A} \) y \( \mathcal{B} \) fórmulas bien formadas cualesquiera de \( \mathcal{L} \).

(2) Generalización: De \( \mathcal{A} \) se deduce \( (\forall{x_i})\mathcal{A} \) siendo \( \mathcal{A} \) cualquier fórmula bien formada de \( \mathcal{L} \) y \( x_i \) cualquier variable.

Junto con los axiomas de \( \mathcal{L} \) hacen que todo teorema de \( \mathcal{L} \) sea fórmula lógicamente válida en cualquier interpretación (por el Teorema de corrección). También que si

\( \mathcal{A}_1,\mathcal{A}_2,\ldots,\mathcal{A}_k,\ldots\mathcal{A}_n \)

es una demostración de \( \mathcal{L} \), también lo es:

\( \mathcal{A}_1,\mathcal{A}_2,\ldots,\mathcal{A}_k \)

Dado que la fórmula \( \mathcal{A}_k \): \( (0+x=SSS0) \) no es verdadera (ni falsa), no puede ser un teorema de \( \mathcal{N} \) suponiendo que este tiene un modelo, con lo cual no existe la hipotética contradicción a la que se refiere Lauluna.

Saludos.

12 Junio, 2009, 01:51 pm
Respuesta #41

Gustavo Piñeiro

  • Visitante
Lo cierto es que yo estoy más acostumbrado a trabajar con sistemas que sólo usan fórmulas cerradas.

Releo esta frase y comprendo entonces tu "desconfianza" hacia la regla de generalización (que es útil solamente si se trabaja con fórmulas con variables libres). Como dije antes, todo es cuestión de gustos y de conveniencia, se pede trabajar todo el tiempo con enunciados (o fórmulas cerradas) e incluir reglas de sustitución de variables y de términos (o axiomas adecuados que las representen) que permitan pasar, por ejemplo, directamente de \( \forall{x}P(x) \) a \( \forall{y}P(y) \) o bien aceptar entre las fórmulas con valor de verdad a las fórmulas con variables libres (más la regla de generalización) y hacer:

\( \forall{x}P(x) \)
\( \forall{x}P(x)\Rightarrow P(y) \) (axioma lógico)
\( P(y) \) (modus ponens)
\( \forall{y}P(y) \) (generalización)

En realidad, la cuestión de si incluir, o no, a las fórmulas con variabes libres entre aquellas fórmulas que admiten valor de verdad fue tema de reflexión con Guillermo Martínez durante la escritura del libro. Y por el modo en que finalmente definimos la noción de verdad (lo comentaré después) llegamos a la conclusión de que necesitábamos incluir a las fórmulas con variables libres.

dado que la fórmula \( \mathcal{A}_k \): \( (0+x=SSS0) \) no es verdadera (ni falsa), no puede ser un teorema

Todo depende de la definición que se adopte. Según mi definición, la fórmula es falsa para la interpretación usual.

Gracias y saludos a ambos!

<<                >>

12 Junio, 2009, 02:06 pm
Respuesta #42

Fernando Revilla

  • Administrador
  • Mensajes: 10,851
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • Las matemáticas son demasiado humanas (Brouwer).
    • Fernando Revilla
Todo depende de la definición que se adopte. Según mi definición, la fórmula es falsa para la interpretación usual.

Cierto, lo que hace que \( \mathcal{A}_k:\;(0+x=SSS0) \) no sea un teorema de \( \mathcal{N} \) es que \( \mathcal{A}_k \) no sea verdadera para toda valoración \( v \) en su hipotético modelo \( \mathbb{N} \), independientemente de como se la llame.

Saludos.

13 Junio, 2009, 12:57 am
Respuesta #43

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)

2. Si \( F \) es una fórmula y \( x_i \) es una variable entonces \( \exists{x_i}F \) es una fórmula.

Definición: decimos que la variable \( x_i \) tiene una aparición libre en la fórmula \( F \) si esa aparición no está afectada por el cuantificador \( \exists{} \) (es decir, si no está precedida por un \( \exists{x_i} \). En principio omito aquí la definición formal del concepto de variable libre.)


Definición: un enunciado es una fórmula en la que ninguna variable tiene apariciones libres (en particular esto sucede si la fórmula no tiene variables).


Pregunta sobre lo que marqué con rojo:
Voy a considerar a la variable \( x_1 \) por ejemplo, y voy a suponer que tengo una fórmula F.
Por la regla de construcción dada, resulta que \( \exists{x_1}F \) también es una fórmula, a la cual denoto con G.
Si aplico de nuevo la misma regla así como está escrita, con la misma variable \( x_1 \), resulta que \( \exists{x_1}G \) también es una fórmula, a la cual puedo llamar H.
Si ''desenrollo'' un poco la fórmula H, obtengo la fórmula \( \exists{x_1\exists{x_1}}F \).
¿Es lícito formar fórmulas en donde el/un cuanfiticador aparezca dos veces afectando a la misma variable?
¿Y si no, cuál es el modo más sencillo de evitarlo usando las formalidades del caso?


Pregunta sobre lo que marqué con verde:
Cuando una variable no está afectada por el cuantificador existencial, ¿cómo ''conviene'' ser interpretada? ¿Una constante quizás, o qué?
Además, las fórmulas tenemos que imaginarlas en un contexto interesante donde hay muchas otras fórmulas, relaciones entre ellas, inferencias, etc. No termino de comprender el papel que juegan las variables libres en un contexto como este, dentro de la metamatemática. ¿Hay algún riesgo o complicación, o se usan fórmulas con variables libres sin inconvenientes?

Creo que la duda tiene que ver con la última definición que está en púrpura, la de enunciado.
¿Por qué se destacan las fórmulas sin variables libres? ¿Son fórmulas deseables?
¿Las proposiciones lógicas que vamos a aceptar tienen que ser enunciados?

No sé en realidad precisar bien la duda, pero lo puedo resumir así: siento comezón en las fórmulas con variables libres, y no sé cuál es la mejor forma de rascarme.

13 Junio, 2009, 03:12 am
Respuesta #44

Gustavo Piñeiro

  • Visitante
Pregunta sobre lo que marqué con rojo:
¿Es lícito formar fórmulas en donde el/un cuanfiticador aparezca dos veces afectando a la misma variable?

Sí, es lícito.

Pregunta sobre lo que marqué con verde:
Cuando una variable no está afectada por el cuantificador existencial, ¿cómo ''conviene'' ser interpretada? ¿Una constante quizás, o qué?
Además, las fórmulas tenemos que imaginarlas en un contexto interesante donde hay muchas otras fórmulas, relaciones entre ellas, inferencias, etc. No termino de comprender el papel que juegan las variables libres en un contexto como este, dentro de la metamatemática. ¿Hay algún riesgo o complicación, o se usan fórmulas con variables libres sin inconvenientes?

Creo que la duda tiene que ver con la última definición que está en púrpura, la de enunciado.
¿Por qué se destacan las fórmulas sin variables libres? ¿Son fórmulas deseables?
¿Las proposiciones lógicas que vamos a aceptar tienen que ser enunciados?

No sé en realidad precisar bien la duda, pero lo puedo resumir así: siento comezón en las fórmulas con variables libres, y no sé cuál es la mejor forma de rascarme.

Las fórmulas con variables libres expresan "relaciones" o "propiedades" (más exactamente, expresan conjuntos). Las variables libres actúan como variables en el mismo sentido que se le da al término cuando se trabaja con funciones. De hecho, a las fórmulas con variables libres, Bertrand Russell las llamaba "funciones proposicionales", que tienen un cierto valor de verdad dependiendo de qué valores se asignen a las variables. Por ejemplo \( x + y = 5 \) expresa el conjunto de todos los pares \( (x,y) \) cuya suma es 5 o también la relación "la suma de \( x \) más \( y \) es 5". Una fórmula con variables libres no es verdadera ni falsa en sí misma, depende de qué valores adopten las variables.

Una fórmula sin variables libres (o fórmula cerrada) es en sí misma verdadera o falsa. Ejemplos son "2 + 4 = 10" o \( \exists{x}\exists{y}(x + y = 5) \).

A veces (contradiciendo un poco lo anterior, pero el contexto en cada caso debería servir para evitar confusiones) al escribir axiomas y demostraciones escribiremos fórmulas con variables libres a modo de abreviaturas de enunciados. Por ejemplo, muchas veces escribirermos \( x + y = y + x \) queriendo decir \( \forall{x}\forall{y}(x + y = y + x) \).  No todos adoptan esta práctica (LauLuna ha dicho que él no lo hace). Como ya dije, es cuestión de gustos y conveniencia.

Saludos!

<<                >>

13 Junio, 2009, 03:54 am
Respuesta #45

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
OK Gustavo, como siempre muy claro.

En cuanto a lo de las fórmulas ''cerradas'', me parece que si algo como x+y=y+x puede dar lugar a cierta ambigüedad (aunque has explicado que no habrá confusión en cada caso), entonces sería mejor evitarlo, y escribir todos los cuantificadores que realmente están presentes en la expresión, sin recurrir a abreviaturas.

Yo tiendo a ser redundante, y hay algunas personas allegadas que me lo critican.
Estoy entre los que prefieren escribir todo el tiempo \( \forall{x}\forall{y}(x + y = y + x) \), aunque resulte algo pesado, en vez de una abreviatura como \( x + y = y + x \).
Y no tanto por el fanatismo de ''lo correcto'', sino que este terreno de la metamatemática da pie para caer fácilmente en ambigüedades y confusiones, sobretodo para quienes estamos poco familiarizados con el tema.
A lo mejor estoy exigiendo lo que es una conveniencia para mí particularmente, porque como he manifestado, todos los pasos que se dan, y todas las construcciones que se hacen me generan dudas.
Como no tengo práctica en el tema, todavía ''siento'' que todo está en el aire, y prefiero la exactitud tanto como sea posible.

Pero está bueno que por lo menos se expliquen y se comenten todas las alternativas que hay dando vueltas por ahí.

Saludos.

P.D.: Lo de cuantificar dos veces la misma variable en una misma fórmula me sigue pareciendo extraño. Pero si está entre las posibilidades que uno puede construir, me la banco.

13 Junio, 2009, 01:32 pm
Respuesta #46

LauLuna

  • Experto
  • Mensajes: 544
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Tal como Gustavo dice, yo, al igual que Argentinator, prefiero trabajar con fórmulas cerradas, es decir, con enunciados.

Las fórmulas abiertas no son enunciados o proposiciones en sentido estricto, por tanto, no tienen valor de verdad en sí mismas. Uno se pregunta entonces qué pintan en las deducciones, porque parece que las deducciones deberían partir de enunciados y llegar a enunciados a través de enunciados.

Sin embargo, es una práctica muy extendida la de admitir fórmulas abiertas (es decir, con variables libres) en los sistemas deductivos. Está así en Gödel, en Kleene, más recientemente en Mendelson y en muchísimos otros. Torkel Franzén ('Inexhaustibility. A Non Exhaustive Treatment' AK Peters 2004, un libro muy recomendable para quien desee profundizar en algunos aspectos de la incompletitud de Gödel y esté dispuesto a estudiar en serio) introduce la regla de Generalización de esta manera (p. 103, traduzco y sustituyo símbolos por lenguaje informal):

"Si la fórmula phi es deducible de un conjunto gamma de fórmulas y x no está libre en ninguna fórmula de gamma, entonces '(para todo x) phi(x)' es deducible de gamma."

Y añade:

"Esto está de nuevo de acuerdo con el razonamiento matemático usual. Si queremos deducir a partir de un conjunto M de premisas queparatodo número real x vale A(x), lo hacemos generalmente razonando para un número real r arbitrario que no especificamos y mostrando que A(r) vale. El paso final expresado en la regla de arriba: 'como r era un real arbitrario, se sigue que A(x) vale para todo real x', suele dejarse implícito [en el razonamiento matemático informal, nota de LauLuna]"

Entonces, la función de las variables libres en el curso de las derivaciones formales parece ser la de reproducir el razonamiento para objetos escogidos al azar, por así decirlo. Por eso las variables libres hacen estrecha pareja con la regla de Generalización, según yo lo veo.

De todas maneras, hay que tener en cuenta que los sistemas que permiten trabajar con fórmulas abiertas permiten probar como teoremas fórmulas abiertas (porque nada nos obliga a dar un paso más y aplicar Generalización) y esto parece una imperfección: deducimos fórmulas que no poseen en sí mismas un valor de verdad en la interpretación usual.

En la mayoría de los textos de Lógica Formal, por lo que yo sé, se evita hoy en día el trabajar con fórmulas abiertas. Para el razonamiento sobre objetos arbitrarios de cara a introducir el cuantificador universal se permite pasar de

'P(a)'

donde 'a' es una constante, a

'(para todo x) P(x)'

si 'a' no aparece en las premisas ni en ninguna suposición no cancelada, lo que garantiza que 'a' denota un objeto arbitrario.

Me pregunto si no sería también deseable introducir esta práctica en los sistemas formales matemáticos.

Un saludo.

13 Junio, 2009, 02:07 pm
Respuesta #47

Fernando Revilla

  • Administrador
  • Mensajes: 10,851
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • Las matemáticas son demasiado humanas (Brouwer).
    • Fernando Revilla
Las fórmulas abiertas no son enunciados o proposiciones en sentido estricto, por tanto, no tienen valor de verdad en sí mismas.

Algunas formulas abiertas si lo son y otras no. Es precisamente por eso por lo que yo prefiero distinguir entre fórmulas verdaderas, falsas y ni verdaderas ni falsas. Esto es una distinción clara entre los lenguajes \( L \) del cálculo de enunciados y el \( \mathcal{L} \) del cálculo de predicados.

Por supuesto que son las fórmulas cerradas en las que tenemos que hacer especial hincapié pues si son verdaderas en todo modelo de un sistema de primer orden \( S \) son teoremas de \( S \).   

Saludos.

13 Junio, 2009, 03:13 pm
Respuesta #48

Gustavo Piñeiro

  • Visitante
Hola,

P.D.: Lo de cuantificar dos veces la misma variable en una misma fórmula me sigue pareciendo extraño. Pero si está entre las posibilidades que uno puede construir, me la banco.

En realidad, el único riesgo es el de ser redundante, ya que, por ejemplo, \( \exists{x}\exists{x}(x = 6) \) es equivalente \( \exists{x}(x = 6) \). Creo que no se ponen reglas especiales para evitar este uso para no complicar innecesariamente las reglas sintácticas del lenguaje, dado que, precisamente, no hay "peligro" en repetir cuantificadores. Sin embargo, no habría ningún cambio esencial en poner reglas que lo eviten.

Por otra parte, considerando el consenso favorable a evitar el uso de fórmulas abiertas para indicar enunciados, no tengo problemas en adoptar esa convención (que, admito, tiende a evitar confusiones). A partir de ahora, entonces, las fórmulas abiertas denotarán siempre relaciones (o funciones proposicionales, término que usaba Ruseell, hoy en desuso, pero que a mí me parece muy descriptivo) y las cerradas, enunciados.

Modificaremos entonces los esquemas lógicos 6, 7 y 8. El 6 ahora dirá: \( \forall{x}(x = x) \), análogamente se modifican el 7 y el 8. El esquema lógico 4 puede dar lugar a fórmulas no cerradas, pero esto no es problema (véanse las definiciones de más abajo).

Supongamos ahora que se propone un conjunto A de axiomas para la Aritmética, es decir, un conjunto de enunciados escritos en el lenguaje formal. (Normalmente, nos interesarán sólo los conjuntos recursivos de axiomas, los cuales están definidos a través de un programa. En la práctica, este programa, a su vez, suele tener la forma de un conjunto finito de esquemas, similar al que dimos para los axiomas lógicos.)

Tenemos así axiomas lógicos y axiomas propios de la teoría (estos últimos son los axiomas del conjunto A, la distinción es la misma que la que hacía Euclides entre nociones comunes y postulados). Podemos dar la siguiente definición:

Definición: una demostración es una sucesión finita de fórmulas en la que cada una de ellas es, o bien un axioma (propio o lógico), o bien se dedude de fórmulas anteriores por aplicación de las reglas de inferencia.

Definición: una fórmula es demostrable si es la última fórmula en una demostración.

Es cierto, como dice LauLuna, que el esquema lógico 4 permite que haya fórmulas abiertas demostrables (no estamos obligados a usar la regla de generalización para agregar los cuantificadores que faltan). Una forma de lograr que esta circunstancia no complique el desarrollo de las ideas es la siguiente:

Definición: una fórmula es demostrable si es la última fórmula en una demostración y es un teorema si es un enunciado demostrable.

Admito que es una definición que acabo de sacarme de la manga, no sé si esta distinción entre "fórmulas demostrables" y "teoremas" existe en la literatura (donde, normalmente, ambas expresiones se toman como sinónimos). Propongo la distinción como modo de compatibilizar las reglas que hasta ahora hemos venido consensuando con el hecho de que sólo los enunciados representen expresiones con valor de verdad.

Me parece que, en este caso, la distinción, lejos de crear confusiones, puede ser útil y, de paso, reserva la palabra "mágica" teorema sólo para los enunciados.

Saludos!

<<                >>

13 Junio, 2009, 05:02 pm
Respuesta #49

Gustavo Piñeiro

  • Visitante
Definición: Un conjunto A de axiomas es recursivo si existe un algoritmo (que trabaja a nivel sintáctico, es decir, solamente manipula signos sin tomar en cuenta su eventual significado) que, dada una secuencia finita símbolos del lenguaje, reconoce si esa secuencia constituye, o no, un axioma.

Los axiomas lógicos forman un conjunto recursivo.

Teorema: Si el conjunto A de axiomas propios es recursivo entonces existe un algoritmo que, dada una secuencia de símbolos del lenguaje, reconoce si esa secuencia constituye, o no, una demostración.

Este teorema es esencial en todo el desarrollo posterior. Es posible tomar un conjunto diferente de axiomas lógicos o diferentes reglas de inferencia, pero estas modificaciones no deben alterra la verdad de este teorema, que está en el corazón mismo del Programa de Hilbert.

Comenté antes que si se agregara la siguiente regla de inferencia:

De los infinitos enunciados \( P(0), P(1), P(2),... \) se deduce \( \forall{x}P(x) \).

Entonces el teorema anterior sería falso y también sería falso el teorema de Gödel.

<<                >>

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

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,272
  • 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

  • Aprendiz
  • Mensajes: 319
  • 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

  • Aprendiz
  • Mensajes: 319
  • 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,272
  • 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

  • Aprendiz
  • Mensajes: 319
  • 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,272
  • 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

  • Aprendiz
  • Mensajes: 319
  • 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,272
  • 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,272
  • 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)