El punto fijo lema es profundo porque revela un
sorprendentemente profunda capacidad en matemáticas para
auto-referencia: cuando una instrucción $A$ es equivalente a
$F(A)$, efectivamente afirma que "$F$ tiene de mí". ¿
sorprendente es encontrar que la auto-referencia, de las cosas de
la paradoja y el absurdo, es fundamentalmente arraigada en nuestra
hermosa la teoría de los números! El punto fijo lema muestra que
todos los elementales de la propiedad $F$ admite una declaración de
la aritmética de la afirmación "esta declaración tiene la propiedad $F$".
La auto-referencia, por supuesto, es precisamente cómo Goedel
demostró el Teorema de la Incompletitud, mediante la formación de los famosos
"esta afirmación no es demostrable" afirmación, la obtención de ella
simplemente como un punto fijo $A$ afirmando "$A$ no es
comprobable". Una vez que usted tiene esta declaración, es fácil ver
que debe ser cierto, pero no demostrable: no puede ser comprobada,
ya que de lo contrario vamos a tener que probó algo falso, y
por lo tanto, es a la vez verdadero y no demostrable.
Pero he compartido su aprehensión en la prueba de la
punto fijo lema, que aunque corto y sencillo, que puede
sin embargo aparecen misteriosamente impenetrable, como un
antigua y mística runa que hemos memorizado. Podemos comprobar
paso-por-paso, pero ¿de dónde provienen?
Así que vamos a tratar de explicarme cómo se podría derivar de este
argumento, o al menos llegar a él por pequeños pasos.
Queremos encontrar una declaración de $A$ que es equivalente a
$F(A)$. Si podríamos esperar una versión fuerte de esta, entonces
nos iba a buscar una $A$ que es equivalente a $F(A)$, y a
$F(F(A))$, y así sucesivamente, que se extendió desde el interior. Tal
proceso conduce naturalmente a la infinitary expresión
Además, este infinitary expresión es en sí mismo un fijo
punto, en un ingenuo manera formal, ya que si $A$ es que
la expresión, entonces la aplicación de uno de los más $F$ resultados en un
con la expresión de la misma forma, como se desee. Este infinitary
la expresión no cuenta como una solución, por supuesto, ya que
buscar finita y bien formado, de expresión, sino que sugiere un
enfoque.
Es decir, lo que queremos hacer es capturar en una sola finito
la expresión de la auto-expansión de la naturaleza de la que infinitary
solución. El deseado declaración de $A$ debe ser equivalente a
la afirmación de que $F$ mantiene cuando se sustituye en $A$
sí. Por lo que introducir una variable auxiliar que se $v$ y
considere la posibilidad de la afirmación de $H(v)$ que afirma que $v$ es como
deseado, es decir, que $F$ sostiene que la declaración de la $v$ códigos,
cuando se sustituye en $v$. Este último auto de sustitución de parte,
acerca de la sustitución de $v$ a $v$, es lo que permite una
la sustitución de la auto-ampliar en dos, y luego tres y así
en, en efecto rizado de la auto-expansión de la infinita cola de
el infinitary expresión en sí misma.
Es decir, si $n$ es el código de $H(v)$, a continuación realizamos la
la sustitución, la obtención de la declaración de $H(n)$, lo que
afirma exactamente eso $F$ sostiene que la declaración de la $n$ códigos
cuando se sustituye en $n$. Pero desde $n$ códigos de $H(v)$, este
significa que $H(n)$ afirma que $F(H(n))$, y tenemos la
deseado de punto fijo.
Permítanme mencionar algunas otras cosas. En primer lugar, es
interesante considerar si todos los puntos fijos de $F$ son
equivalente a unos de otros. Esto es verdad, después de todo al $F$
es tautológica, por ejemplo, desde cualquier punto fijo se
también puede ser lógicamente válido. Del mismo modo, Goedel "yo no soy
comprobable" las declaraciones es equivalente a la afirmación de
que la teoría es consistente, y esto es cómo uno puede
probar el Segundo teorema de la incompletitud. Pero son fijos
puntos para un determinado $F$ siempre equivalentes? La respuesta es no.
Corrección de las declaraciones $A$ e $B$, y deje $F(v)$ ser el
declaración, "si $v=[A]$,, a continuación,$A$, de lo contrario $B$". Tenga en cuenta que
$F([A])$ es equivalente a $A$ e $F([B])$ es equivalente a
$B$, así que ambos son puntos fijos.
Andreas planteó la pregunta muy interesante en el
comentarios a continuación si el punto fijo, $A$ ha $F([A])$
también como un punto fijo. Esto es lo que podemos esperar de la infinitary ejemplo anterior.
El ejemplo del párrafo anterior se muestra, sin embargo, que
no todos los punto fijo tiene esta característica, ya que en ese
ejemplo, $A$ es equivalente a $F([A])$, pero $F([F([A])])$
es equivalente a $B$. Pero en este ejemplo, otros fijos
los puntos tienen la característica. Yo estoy seguro de que, en general, acerca de si debe haber siempre un punto fijo $A$ tal que
$F([A])$ es también un punto fijo.
Por último, me gustaría mencionar que, en esencia, el mismo
el argumento para el punto fijo lema ha sido utilizado para probar
otros teoremas de punto fijo en la lógica. Por ejemplo, la
La recursividad
Teorema de
afirma que para cualquier función computable $f$, actuando en
de los programas, no es un programa de $e$ tal que $e$ e $f(e)$
calcular exactamente la misma función.
Uno puede probar esto en una forma muy similar a la de punto fijo
lema. Es decir, definir H(v,x)={f({v}(v))}(x), donde {e}(x)
significa la salida de programa de correo en la entrada x. Tenga en cuenta que H es
ejecuta el programa de v sobre sí mismo, y, a continuación, la aplicación f, así como
la H en su argumento. Ahora, vamos a ser la función que en
de entrada v, produce un programa para calcular H(v,x), de modo que
{s(v)}(x)=H(v,x). Deja d ser el programa de computación s, y vamos a
e=s(d). Poner esto juntos, hemos
- {e}(x) = {s(d)}(x)= H(d,x) = {f({d}(d))}(x)
= {f(s(d))}(x) = {f(e)}(x).
Así el programa e y f(e) calcular la misma función.
