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.234.228.78 (7af1791234)
Comentario
¿Cuánto es: diez mil + uno?

Busca en Cambalache


Blogalia


Se comenta en Cambalache

  • Zifra en Quantum State-Independent Contextuality Requires 13 Rays
  • JJ en Quantum State-Independent Contextuality Requires 13 Rays
  • jmaq en ¿Estudiar para hacer unas oposiciones? ¿Merece la pena? ¿Existen los enchufes y las recomendaciones?
  • Santiago Heredia en España y los gitanos
  • Elena en Resiliencia
  • CARLOS en Tangos con cocaína
  • Anónimo en Procuro olvidarte
  • Emma en ☆☆☆☆☆☆☆☆ Ya nunca juego al ajedrez (23-F)
  • Gustavo Osorio Pagán en Sobre las diferencias entre TABLA y CUADRO y de cómo este último es el término correcto si no se habla de logaritmos o similares
  • Zifra en La canción que nunca grabó Javier Ruibal (borrador)
  • Categorías:

    Archivos:

    <Diciembre 2018
    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
    31            

    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