Autor Tema: Teorema de Gödel

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

10 Julio, 2009, 07:28 pm
Respuesta #150

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Ahora bien, teniendo en cuenta que el conjunto de las máquinas de Turing es infinito-numerable, entonces ¿cómo se demuestra mediante una función recursiva, un teorema acerca de las máquinas de Turing (por ejemplo el "Halting Problem"?

Un saludo cordial.  :)

Tengo la misma duda... Mi programa en Python tiene hambre de respuestas

11 Julio, 2009, 03:48 am
Respuesta #151

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
Hola Gustavo, yo te estoy siguiendo minuciosamente.

Tus últimas construcciones técnicas empiezan a despejar algunos de mis nubarrones.

Saludos.
Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.

11 Julio, 2009, 04:25 am
Respuesta #152

Gustavo Piñeiro

  • Visitante
Definamos ahora la función g(n) del siguiente modo: \( g(n) = c\'od(\overline{n}) \). es decir, la función g le asigna a cada número n el código de su numeral (el código de su "nombre"). (Recordemos que \( \overline{n} \) se define como \( SS\ldots S0 \) donde la S aparece n + 1 veces.)

Queremos probar que g es expresable. Es decir, que la relación binaria "y = g(x)" es expresable.

Para hacerlo usaremos una variante del Principio Generador. La diferencia es que antes trabajamos con sucesiones de expresiones aritméticas y ahora trabajaremos con sucesiones de pares ordenados de expresiones aritméticas.

En el lenguaje formal al par ordenado de expresiones aritméticas \( (E_i,F_i) \) lo indicaremos como \( E_i\otimes{}\otimes{}F_i \). La sucesión de pares:

\( (E_1,F_1),(E_2,F_2),\ldots ,(E_k,F_k) \)

la escribiremos como:

\( \otimes{}E_1\otimes{}\otimes{}F_1\otimes{}E_2\otimes{}\otimes{}F_2\otimes{}\ldots \otimes{}E_k\otimes{}\otimes{}F_k\otimes{} \)

De manera similar a como lo hicimos para las sucesiones de expresiones aritméticas, se puede probar que:

1. "Ser un par ordenado de expresiones aritméticas" es expresable.
2. "Ser una sucesión de pares ordenados de expresiones aritméticas" es expresable.
3. La relación "El par ordenado de expresiones aritméticas (E,F) aparece en la sucesión H" es expresable.
4. La relación "Los pares ordenados de expresiones aritméticas (E,F) y (E',F') aparecen consecutivamente, en ese orden, en la sucesión H" es expresable.

Diremos que una sucesión de pares ordenados de expresiones aritméticas corresponde a la función g si se cumple que:

1. El primer par de la sucesión es (0,8). (Traducido, claro está, al lenguaje formal, es decir, la sucesión comienza con \( \otimes{}0\otimes{}\otimes{}SSSSSSSS0\otimes{} \). La elección del 8 se debe a que 8 = g(0).)
2. Si (x,y) aparece en la sucesión entonces (x,y) y (Sx,z) son consecutivos en la sucesión, donde z se obtiene de concatenar el código de S con y.

Es fácil ver que "Ser una sucesión de pares ordenados de expresiones aritméticas que corresponde a la función g" es expresable.

Por otra parte, una sucesión que corresponde a g es siempre de este tipo: (0,g(0)), (1,g(1)), (2,g(2)),..., (k,g(k)). Por lo tanto:

"y = g(x)" si y sólo si existe una sucesión que corresponde a g en la que aparece el par (x,y). Como todas estas condiciones son expresables, entonces g es expresable.

Nota: Podemos generalizar el razonamiento que hicimos para g y probar que si f es una función tal que el valor de f(0) es conocido y el procedimiento para calcular f(n + 1) a partir de f(n) es expresable, entonces f es expresable.

11 Julio, 2009, 04:42 am
Respuesta #153

Gustavo Piñeiro

  • Visitante
La función diagonal

Hemos definido antes una función h(n,m), que puede calcularse para todo par (n,m), pero que en el caso particular en que n es el código de una fórmula P(x) y m es el código de un término t entonces h(n,m) es el código de P[t]. (En este párrafo y en todo lo lo que sigue, x representa la variable \( v_| \).)

P[t] es una cierta fórmula que se escribe a partir de t y P. Vimos antes cómo se define, basta recordar aquí que su característica principal es que P[t] es equivalente a P(x/t). Esta equivalencia es sintáctica, es decir, a partir de P[t] (por medio de axiomas lógicos y reglas de inferencia) se puede deducir P(x/t), y viceversa. Esto implica que P[t] es demostrable (a partir de un cierto conjunto de axiomas) si y sólo si P(x/t) es demostrable.

Vimos antes que la función h es expresable.

También hemos definido la función \( g(n)=c\'od(\overline{n}) \) y vimos que es expresable.

Definimos ahora la función diagonal d(n) del siguiente modo: d(n) = h(n,g(n)).

Es claro que la función d es expresable (esto se debe a que que \( d(x) = y \) si y sólo si \( \exists{z}(h(x,z) = y\wedge z = g(x)) \)).

Por otra parte, como g(n) es el código de un término, concretamente es el código del término \( \overline{n} \), tenemos que:

Si n es el código de una fórmula P(x) entonces d(n) es el código de \( P[\overline{n}] \).


<<                >>

11 Julio, 2009, 12:37 pm
Respuesta #154

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Vaya. Es cierto que, por la tesis de Church-Turing, cualquier teorema que se demuestra en matemáticas debería ser calculable  por una función recursiva.

Ahora bien, teniendo en cuenta que el conjunto de las máquinas de Turing es infinito-numerable, entonces ¿cómo se demuestra mediante una función recursiva, un teorema acerca de las máquinas de Turing (por ejemplo el "Halting Problem"?

Un saludo cordial.  :)

No, no es que todo teorema pueda demostrarse a través del cálculo de una función recursiva; no estoy diciendo que todo teorema sea un caso particular de cálculo de los valores de una función recursiva.

Es simplemente que si has demostrado un teorema puedes programar una máquina para que lo haga, basta con que reflexiones sobre los recursos que has empleado en la demostración y los reprresentes en un sistema formal axiomático; dado un sistema formal axiomático, existe siempre un programa que enumera sus teoremas.

Tomemos el teorema de Turing. Naturalmente Turing utilizó unos axiomas (explícitos o implícitos; es decir, unas proposiciones que asumió como verdaderas y que utilizó en la prueba) y unas leyes lógicas de inferencia. Estos axiomas pueden implicar conjuntos infinitos, incluso no numerables; lo único necesario es que encontremos un lenguaje de programación al que traducirlos. Todos esos axiomas y leyes lógicas pueden hacerse explícitos, y escribirse como un sistema formal. Y entonces podemos programar una máquina para que aplique esas leyes de inferencia a esos axiomas y derive el teorema de Turing.

Y así para cada teorema.

De esto, lógicamente, no puede darse una prueba matemática; se trata sólo de una conjetura extremadamente verosímil.

Naturalmente la máquina no estará realmente demostrando el teorema, sólo estará manipulando símbolos según las instrucciones recibidas. Pero aquellos que conozcan el significado de esos símbolos encontrarán en las manipulaciones de la máquina una prueba del teorema en cuestión. Las máquinas no tienen semántica, sólo sintaxis; para que lo que hacen se convierta en una demostración (o en un simple cálculo) es necesario que un ser con semántica aplique la clave y convierta las ristras de símbolos en pensamientos.

Pero claro, no existe el programa capaz de 'demostrar' todo teorema posible.

Un saludo.

11 Julio, 2009, 01:08 pm
Respuesta #155

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
En cuanto a la meta-meta-meta-...-matemática, me temo que eso es como tú te temes:

[...]

Generalmente se considera que estos sistemas recurrentes se extienden a través de los ordinales conjuntistas hasta un cierto ordinal transfinito que definieron Church y Kleene. La idea de estas iteraciones parte de un artículo de Turing de 1939 y fue retomada por Feferman en los sesenta (creo); Franzén da una visión general en su 'Inexhaustibility. A Non-Exhaustive Treatment'.

Bueno, pero entonces ¿hay algún ordinal donde toda esta recurrencia se termina?
Eso me daría algo de alivio por ahora.
 ???

Bueno, no exactamente. La situación es ésta: la iteración no puede hasta el primer ordinal no constructivo de Church-Kleene (que suele representarse como omega sub 1 elevado a CK). Pero este es un ordinal límite al que te puedes acercar indefinidamente pero que no puedes alcanzar mediante tus iteraciones.

Cuento un poquito más acerca de este ordinal y lo hago de manera muy informal.

Toma cualquier método de notación que te permita dar nombre (o 'construir') ordinales paso a paso desde 0. Cada uno de estos métodos se corresponde con una máquina de Turing y está representado en el cálculo lambda. Dado un método de estos, siempre habrá otro que te lleve más lejos (esto se llama a veces el teorema de Church-Kleene). El primer ordinal no constructivo de Church-Kleene es el menor ordinal que es inalcanzable por un método de construcción de ordinales paso a paso.

Deducimos que este ordinal existe porque hay sólo una cantidad enumerable de tales métodos (de tales máquinas de Turing) y cada uno de ellos sólo puede construir una cantidad enumerable de ordinales; pero hay una cantidad supernumerable de ordinales enumerables, de manera que debe haber un ordinal enumerable que sea inalcanzable por ninguno de esos métodos.

Se supone que al construir sistemas mediante iteración (añadiendo el axioma de consistencia de lo anterior), tienes que construir a la vez paso a paso los ordinales que recorres. Por tanto, no parece que la iteración pueda llevarse hasta el primer ordinal no constructivo. Sin embargo, esto no implica que vayas a encontrar un punto final en tu iteración: cualquiera puede ver que esa iteración de sistemas no puede tener un punto final; cada método se acerca indefinidamente a un ordinal límite sin alcanzarlo, pero además siempre habrá otros métodos de construcción que te lleven más y más lejos.

El que no haya un método para construir paso a paso todos los ordinales constructivos es fácil de ver. Primero: como cada uno de esos métodos sólo construirá una cantidad enumerable de ordinales, habrá siempre ordinales que no construye. Segundo: imagínate que tenemos un método capaz de construir todos los ordinales constructivos; hay dos casos posibles:

1. De estos ordinales hay un máximo: entonces podemos construir su sucesor; contradicción.
2. De estos ordinales no hay un máximo: entonces podemos construir el menor ordinal límite que los sobrepasa a todos, simplemente definiéndolo como la unión de todos los ordinales constructivos; de nuevo contradicción.

La clave está en que podemos ir siempre más allá de cuanto está algorítmicamente objetivado ante nuestros ojos. Este es el fenómeno de la 'inexhaustibilidad'.

Un saludo

11 Julio, 2009, 01:30 pm
Respuesta #156

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Gustavo, la demostración que has hecho de que la función diagonal es expresable es todo un lujo.

Generalmente te definen la función y te dicen que es obviamente recursiva; a continuación se refieren al teorema de que toda función recursiva es expresable y punto.

Imagino que has sustituido P(x/t) por P[t] porque la demostración de la expresabilidad de la función h(n, m) ofrece un camino más fácil para la demostración de que la función diagonal es expresable.

11 Julio, 2009, 03:22 pm
Respuesta #157

Gustavo Piñeiro

  • Visitante
Imagino que has sustituido P(x/t) por P[t] porque la demostración de la expresabilidad de la función h(n, m) ofrece un camino más fácil para la demostración de que la función diagonal es expresable.

Exactamente. (El mérito se le debe atribuir a Raymond Smullyan.)

Saludos!

11 Julio, 2009, 03:30 pm
Respuesta #158

Gustavo Piñeiro

  • Visitante
Un último tecnicismo. El esquema lógico número 4 nos dice que toda fórmula del tipo:

\( \forall{x}P(x)\Rightarrow{P(x/t)} \)

es un axioma. Por otra parte, del esquema lógico número 3, que es:

\( (-Q\Rightarrow{-P})\Rightarrow{(P\Rightarrow{Q})} \)

se puede deducir que toda fórmula del tipo:

\( (Q\Rightarrow{P})\Rightarrow{(-P\Rightarrow{-Q})} \)

es demostrable.

De ambos hechos, deducimos que toda fórmula del tipo:

\( -P(x/t)\Rightarrow{-\forall{x}P(x)} \)

es demostrable. Luego, toda fórmula del tipo:

\( -P(x/t)\Rightarrow{\exists{x}-P(x)} \)

y también del tipo:

\( P(x/t)\Rightarrow{\exists{x}P(x)} \)

es demostrable.

<<                >>

11 Julio, 2009, 03:55 pm
Respuesta #159

Gustavo Piñeiro

  • Visitante
El final de la demostración.

En todo lo que sigue, x es la variable \( v_| \).

Definimos P(z) como la fórmula \( -\exists{y}Dem(y,z) \). (Recordemos que \( Dem(y,z) \) expresa la relación "y es el código de una demostración de la fórmula de código z".)

Definimos Q(x) como \( \forall{z}(z=d(x)\Rightarrow{P(z)}) \).

Sea n = cód(Q(x)). Entonces \( d(n) = c\'od(Q[\overline{n}]) \). Llamamos m = d(n).

Los siguientes enunciados son equivalentes entre sí (esta equivalencia es sintáctica e implica que cualquiera de ellos es demostrable si y sólo si cualquiera de los otros lo es):

1. \( Q[\overline{n}] \)
2. \( Q(x/\overline{n}) \)
3. \( \forall{z}(z=\overline{m}\Rightarrow{P(z)}) \)
4. \( P[\overline{m}] \)
5. \( P(x/\overline{m}) \)

Llamemos G al enunciado \( P(x/\overline{m}) \), es decir, \( -\exists{y}Dem(y,\overline{m}) \).

Vamos a demostrar que ni G ni -G son demostrables.

Recordemos que hemos supuesto que se ha dado un sistema omega-consistente de axiomas aritméticos. (Que sea omega-consistente implica que es consistente.)

Si G es demostrable, entonces (por las equivalencias que mencionamos antes) \( Q[\overline{n}] \) es demostrable. Recordemos que el código de \( Q[\overline{n}] \) es m.

Sea k el código de una demostración de \( Q[\overline{n}] \), entonces \( Dem(\overline{k},\overline{m}) \) es un enunciado verdadero. La palabra "verdadero" se usa aquí en el sentido finitista, ya que \( Dem(\overline{k},\overline{m}) \) es un enunciado que expresa una propiedad de k y m que es verificable en una cantidad finita de pasos.

Como \( Dem(\overline{k},\overline{m}) \) es un enunciado finitista verdadero, entonces (por hipótesis) es demostrable. En consecuencia (por el tecnicismo que vimos antes) \( \exists{y}Dem(y,\overline{m}) \) es demostrable. Pero entonces -G es demostrable (ya que \( \exists{y}Dem(y,\overline{m}) \) es equivalente sintácticamente a -G). Esto contradice que el sistema es consistente, luego G no es demostrable.

Si -G es demostable entonces, por la consistencia del sistema, G no es demostrable. Luego, para todo k, \( -Dem(\overline{k},\overline{m}) \) es un enunciado finitista verdadero y, por lo tanto, demostrable. Por la omega-consistencia entonces \( \exists{y}Dem(y,\overline{m}) \) no es demostrable. Entonces -G no es demostrable. Esto contradice la hipótesis inicial. Por lo tanto, -G no es demostrable.

Vimos así que G no es demostrable, y que -G tampoco es demostrable. El sistema es, entonces, incompleto, Q.E.D.