Máquina godeliana

El siguiente problema es la anotación #65 del libro 5000 años adC y otras fantasías filosóficas, una de las mejores obras del lógico matemático, mago, taoísta, pianista y fabricante de telescopios Raymond Smullyan. Y profesor en la Universidad de nueva York, en la calle 4. Me encantaría haber estudiado lógica con él y allí.

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!