Cambalache 3,14 - La vidriera irrespetuosa

Máquina gödeliana

De las muchas máquinas matemáticas que he utilizado para ilustrar la famosa prueba de Gödel, la siguiente es la más sencilla.

La máquina imprime distintas expresiones que se componen de cuatro símbolos: I, N, R, *. Se considera IMPRIMIBLE cualquier expresión que la máquina puede imprimir. FRASE es cualquier expresión de una de las cuatro formas: I*X NI*X IR*X NIR*X dónde X es cualquier expresión construida a partir de los cuatro símbolos. Cada frase se interpreta como sigue: I*X se considera VERDADERA si y sólo si X es imprimible NI*X se considera VERDADERA si y sólo si X no es imprimible (N es una abreviatura de NO así como I es una abreviatura de IMPRIMIBLE) IR*X se considera VERDADERA si y sólo si XX es imprimible (XX se denomina REPETICION de X, de ahí la letra R) NIR*X se considera VERDADERA si y sólo si XX no es imprimiblePartimos de la base de que la máquina es completamente precisa, es decir, cualquier frase impresa por la máquina es una frase verdadera. El problema consiste en encontrar ¡una frase verdadera que la máquina no pueda imprimir!

La solución y el origen del problema, dentro de unos días... o en los comentarios. ¡No vale usar google! (Vale, pero entonces, no comentes el resultado)

2005-10-14 23:30 | Categoría: Autorreferencia | Enlace permanente | Etiquetas: | Y dicen por ahí

Referencias (TrackBacks)

URL de trackback de esta historia http://zifra.blogalia.com//trackbacks/33812

De: Cambalache v.3.14 - La vidriera irrespetuosa

Fecha: 2005-10-17 01:00

NIR*NIR*: «(Respuesta a Máquina gödeliana) NIR*NIR* se traduce como La repetición de NIR* no es imprimible. Por lo tanto, si es verdadera (imprimible) no es imprimible. Y si es falsa (no imprimible) es imprimible. Ya tenemos la paradoja. Y»

Comentarios

De: Salva

Fecha: 2005-10-14 23:50

Jeje, esto lo cuentas el martes... y te los cargas XD

De: Anónimo

Fecha: 2005-10-15 01:33

No intentemos repartir estrellas dos veces...

De: Salva

Fecha: 2005-10-15 13:10

Vaya, perece desde Explorer que no has cerrado bien alguna etiqueta.. quizás < code >

De: fanshawe

Fecha: 2005-10-15 16:20

Eh... lo intento. Juro que lo intento. Pero no he logrado comprender nada. Hasta he buscado los teoremas de Godel (siento la diéresis, no la encuentro en el teclado italiano) en Wikipedia... y sigo sin entenderlo. Pero por favor, valorad mi intención...

Fdo. Un intruso de letras.

De: Fer

Fecha: 2005-10-15 21:22

Oye, la solución es relativamente sencilla (por lo menos para los que somos de letras pero hemos leído a Douglas R. Hofstader).
Pero, ¿quieres que la contemos a tí y te escojonemos el phatos o prefieres contarla tú? (o que la cuente dr. Salva)

De: Mitch

Fecha: 2005-10-16 17:43

He encontrado una solución tan simple que sospecho que me he equivocado.
Existe una solución elegante a la par que sencilla o he metido el zueco?

De: Fer

Fecha: 2005-10-16 19:41

La solución es simple, se trata de crear una paradoja, ¿no es así, doctores?

De: Zifra

Fecha: 2005-10-16 22:47

Correcto, Fer. Cuéntala cuando quieras, que ya han pasado dos días

De: Toni

Fecha: 2007-05-08 06:06

Pues la solución de Salva es correcta pero no así la explicación.
Hemos de probar que NIR*NIR* es verdadera pero no imprimible.
1) Si NIR*NIR* es verdadera, entonces (como es de la forma NIR*X) XX no es imprimible, pero en este caso X es NIR*. Por tanto NIR*NIR* no es imprimible.
En resumen NIR*NIR* sería verdadera y, además, no imprimible.
2) Si NIR*NIR* no es verdadera entonces (como es de la forma NIR*X) sabemos que no es verdad que "XX no es imprimible", o sea que XX es imprimible. Pero si XX es imprimible, entonces debe ser verdadera (pq la máquina es precisa y cualquier frase impresa es verdadera) y como X=NIR* entonces NIR*NIR* es verdadera. Y acabamos por llegar a una contradicción interpretable como que (2) no es posible. O bien, estamos nuevamente en el caso (1) y al aplicar lo dicho tenemos la prueba buscada.