Cambalache 3,14 - La vidriera irrespetuosa


Que el mundo fue y será una porquería, ya lo sé.

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 imprimible
Partimos 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 | 9 han comentado esto | Enlace permanente | Etiquetas: | Y dicen por ahí

Referencias (TrackBacks)

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

1
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

1
De: Salva Fecha: 2005-10-14 23:50

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



2
De: Anónimo Fecha: 2005-10-15 01:33

No intentemos repartir estrellas dos veces...



3
De: Salva Fecha: 2005-10-15 13:10

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



4
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.



5
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)



6
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?



7
De: Fer Fecha: 2005-10-16 19:41

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



8
De: Zifra Fecha: 2005-10-16 22:47

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



9
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.



Nombre
Correo-e
URL
Dirección IP: 54.198.245.233 (9cb18a59bf)
Comentario

Busca en Cambalache


Blogalia


Se comenta en Cambalache

  • Anónima en 10 de Marzo de 1991
  • Anónima en Ya nunca juego al ajedrez Años de plomo (la película)
  • Anónima en No, no es la Diada ni son las torres gemelas de Manhattan...
  • Zifra en Olvido
  • Anónimo en Olvido
  • Zifra en Quantum State-Independent Contextuality Requires 13 Rays
  • Anónima en Álgido
  • nfernefer en Álgido
  • Zifra en Álgido
  • Anónima en Álgido
  • Categorías:

    Archivos:

    <Abril 2017
    Lu Ma Mi Ju Vi Sa Do
              1 2
    3 4 5 6 7 8 9
    10 11 12 13 14 15 16
    17 18 19 20 21 22 23
    24 25 26 27 28 29 30
                 


    Lista de Enlaces

    De interés

    E-góticos

    Mis otros

    FotoFlickr


    Blogalia



    Versión para la columna lateral


    zifra. Get yours at bighugelabs.com/flickr
    2003-2006 Zifra – Powered by Blogalia – Estadísticas: Nedstat Basic - Web site estadísticas gratuito El contador para sitios web particulares