Hola mundo.
Como siempre, vengo medio atravesado respecto a la corriente.
Mientras ustedes se han encaramado con la prueba del teorema, yo ando entretenido con otras cosas, como por ejemplo meter las definiciones metamatemáticas en un programa real de computadora.
Incluyo esto acá porque quiero contribuir con algo más que con meras quejas y preguntas.
Les cuento brevemente qué anduve haciendo.
Primero una reflexión sobre Máquinas de Turing, Máquina Virtual Java, memoria RAM y lenguajes de programación, terminando con una sospechosa justificación de por qué elegí el lenguaje Python a fin de cuentas.
Las pongo en un Spoiler porque puede no interesarle a todo el mundo.
Spoiler
Primero que nada, tuve que tomar una decisión acerca de qué lenguaje de programación o qué entorno informático usar para emular lo más exactamente posible la característica de trabajar bajo una Máquina de Turing.
Las Máquinas de Turing en su planteamiento básico resultan algo complicado de manejar, debido a que usan operaciones muy elementales de computación: escribir y borrar bits en una cinta hipotética.
La cinta de la máquina de Turing puede reemplezarse por un disco rígido, una memoria RAM, etc.
Sin embargo hay estudios de teoría de la computación que concluyen que cualquier lenguaje de programación moderno, corriendo en una PC de escritorio actual, emula las características de una Máquina de Turing.
Sin embargo, se debe suponer la situación ideal de que la memoria RAM disponible (la famosa ''cinta'') es ampliable tanto como se quiera, o sea, se mantiene finita pero ilimitada, y puede crecer tanto como lo deseemos.
Esa situación sería posible, por ejemplo, si pudiéramos enchufar varios pendrives formando un ''trencito'', y así ampliaríamos la RAM tanto como nos dé la gana.
Pero esa limitación de Hardware no debería preocuparnos tanto como la de Software.
En el pasado hubieron sistemas operativos que no eran capaces de aprovechar toda la RAM disponible.
Hoy día a veces tenemos limitaciones similares.
Pero cualquiera sea el sistema operativo, podemos instalar una Máquina Virtual Java, que es una plataforma especial que permite correr programas Java, claro, pero también permite aprovechar toda la memoria RAM disponible. Si hiciéramos programas inteligentes en Java, se podrían detectar a tiempo las carencias de memoria RAM, y en vez de poner un cartel: ''ERROR: EL SISTEMA SE QUEDÓ SIN MEMORIA'', se podría poner un cartel más optimista: ''LA MEMORIA RAM ESTÁ POR ACABARSE, POR FAVOR AMPLÍELA PARA PODER SEGUIR CON LA EJECUCION DEL PROGRAMA".
Así que, según yo lo veo, la Máquina Virtual Java es ''LA'' Máquina de Turing.
Ahora bien. Resulta que programar en Java lleva su tiempo. ¿Qué alternativas hay?
Me fijé qué pasaba con el lenguaje de programación Python.
Este es un lenguaje interpretado, de manera que trabaja bajo un entorno de comandos.
Python trabaja con listas y cadenas de caracteres de manera bastante natural, de manera que el programador no debe preocuparse en general de las limitaciones de la memoria RAM.
No he investigado sobre este tema, pero da toda la sensación de que uno podría programar inteligentemente en Python para detectar también carencias de memoria, y poner un cartelito que pida más RAM cuando haga falta.
Existen versiones de Python para cualquier plataforma, así que tendríamos, de nuevo, una correcta Máquina de Turing, si es que es verdad que Python es capaz de aprovechar todos los recursos (sobretodo la RAM) que el sistema le brinda.
A pesar de todo esto, no me parecen soluciones demasiado limpias, ni Java ni Python.
Pero al final me volqué por Python porque es sencillísimo programar en ese lenguaje, y así se puede concretar las ideas que uno tiene con mayor rapidez. Uno puede pensar en hacer un esfuerzo mayor más adelante, programando en otro lenguaje, pero en realidad da lo mismo, porque lo que en realidad nos hace falta es una Máquina virtual de Turing, bien diseñada, que dudo que alguien se haya tomado el trabajo de hacer.
Otro punto en contra de Python es que uno no puede hacer una verificación de tipos de datos, de manera que una cadena de caracteres podría entrar como un número o una lista o cualquier objeto posible, con los peligros que eso acarrea.
Aún así, me quedé con Python, porque me permitió terminar en una tarde una lista de funciones para verificar los elementos básicos de la metamatemática.
Las reglas que usé en el programa son las que dio Gustavo, las puse en una clase llamada
language y, dada una
cadena de caracteres s, las operaciones que pueden hacerse sobre
s permiten verificar si:
* s está en el lenguaje L con los signos del mismo,
* s es una constante
* s es una variable
* s es un término sin variables (un átomo)
* s es un término (quizá con variables)
* s es una fórmula
Estas verificaciones son muy fáciles de hacer, siempre y cuando uno no quiera hacer nada más con la cadena s, porque en cuanto uno quiera aplicar axiomas, demostraciones, etc., la cosa se complica un poco más (y aún no he intentado nada con esto último).
No incluyo todavía otro tipo de verificaciones: como por ejemplo si una variable es libre en una fórmula. Pero ya lo voy a hacer en una futura entrega.
Les dejo en el spoiler un volcado de una salida típica del programita que hice (son 5 cadenas distintas, la primera vacía):
Spoiler
ANALISIS METAMATEMATICO DE LA CADENA DE CARACTERES:
está en el lenguaje L? True
es una constante? False
es una variable? False
es un átomo? False
es un término? False
es una fórmula? False
ANALISIS METAMATEMATICO DE LA CADENA DE CARACTERES: x''''''''''''''
X'''''''''''''' está en el lenguaje L? True
X'''''''''''''' es una constante? False
X'''''''''''''' es una variable? True
X'''''''''''''' es un átomo? False
t
X'''''''''''''' es un término? True
t
t
X'''''''''''''' es una fórmula? False
ANALISIS METAMATEMATICO DE LA CADENA DE CARACTERES: Ex'''x=0
EX'''X=0 está en el lenguaje L? True
EX'''X=0 es una constante? False
EX'''X=0 es una variable? False
EX'''X=0 es un átomo? False
EX'''X=0 es un término? False
qX=0
qX=t
qt=t
qf
f
f
EX'''X=0 es una fórmula? True
ANALISIS METAMATEMATICO DE LA CADENA DE CARACTERES: (S((x'''+S((x'''+S(x''''')))))+(x.(x'''+S(S(S(0))))))
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) está en el lenguaje L? True
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) es una constante? False
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) es una variable? False
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) es un átomo? False
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(t))))))
(S((t+S((t+S(t)))))+(t.(t+S(S(S(t))))))
(S((t+S((t+t))))+(t.(t+S(S(t)))))
(S((t+S(t)))+(t.(t+S(S(t)))))
(S((t+t))+(t.(t+S(t))))
(S(t)+(t.(t+S(t))))
(t+(t.(t+t)))
(t+(t.t))
(t+t)
t
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) es un término? True
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(t))))))
(S((t+S((t+S(t)))))+(t.(t+S(S(S(t))))))
(S((t+S((t+t))))+(t.(t+S(S(t)))))
(S((t+S(t)))+(t.(t+S(S(t)))))
(S((t+t))+(t.(t+S(t))))
(S(t)+(t.(t+S(t))))
(t+(t.(t+t)))
(t+(t.t))
(t+t)
t
t
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) es una fórmula? False
ANALISIS METAMATEMATICO DE LA CADENA DE CARACTERES: Ex'''(-----Ax'(S((x'''+S((x'''+S(x''''')))))+(x.(x'''+S(S(S(0))))))=S(S(0))*-x=S(0))
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) está en el lenguaje L? True
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) es una constante? False
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) es una variable? False
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) es un átomo? False
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) es un término? False
q(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0))
q(-----q(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0))
q(-----q(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(t))))))=S(S(t))*-X=S(t))
q(-----q(S((t+S((t+S(t)))))+(t.(t+S(S(S(t))))))=S(S(t))*-t=S(t))
q(-----q(S((t+S((t+t))))+(t.(t+S(S(t)))))=S(t)*-t=t)
q(-----q(S((t+S(t)))+(t.(t+S(S(t)))))=S(t)*-t=t)
q(-----q(S((t+t))+(t.(t+S(t))))=t*-t=t)
q(-----q(S(t)+(t.(t+S(t))))=t*-t=t)
q(-----q(t+(t.(t+t)))=t*-t=t)
q(-----q(t+(t.t))=t*-t=t)
q(-----q(t+t)=t*-t=t)
q(-----qt=t*-t=t)
q(-----qf*-f)
q(-----f*-f)
q(----f*f)
q(---f*f)
q(--f*f)
q(-f*f)
q(f*f)
qf
f
f
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) es una fórmula? True
Los que quieran experimentar con el programita, o modificarlo, etc., se los dejo adjunto en un archivo.
Está con extensión
.txt, pero hay que renombrarlo a
.py para que corra en Python.
La versión es Python 3.0.
En este otro Desplegable les dejo a mano las reglas que Gustavo dio en este mismo Thread, las cuales usé en el programa:
Spoiler
Para definir un sistema formal debemos comenzar por definir los símbolos del lenguaje. El lenguaje tendrá:
1. Símbolos lógicos: \( \exists{} \), \( \Rightarrow{} \), \( - \), \( = \).
(El \( - \) es el símbolo de negación. El \( = \) no siempre se incluye entre los símbolos lógicos, pero en este caso sí lo haremos.)
2. Variables: \( x_1 \), \( x_2 \), \( x_3 \),...
(veremos después que estas variables pueden escribirse usando solamente dos símbolos básicos.)
3. Constante: una sola constante, \( 0 \).
4. Símbolos de funciones: \( S \), \( + \), \( \cdot{} \).
(El uso de la palabra "función" es sólo para darle un nombre común a estos símbolos, no es necesario saber qué es una "función".)
5. Signos de puntuación: \( ( \), \( ) \)
Llamamos expresión a cualquier secuencia finita de símbolos.
Un término se define del siguiente modo:
1. Las variables y la constante son términos.
2. Si \( s \) y \( t \) son términos entonces \( (s + t) \), \( (s\cdot{}t) \) y \( S(t) \) son términos.
3. Todo término se obtiene por aplicaciones sucesivas (una cantidad finita de veces) de las reglas anteriores.
(En relación con el comentario anterior sobre el infinito potencial y el infinito actual, nótese que no hablamos del conjunto de todos los términos sino de una construcción paso a paso.)
(A veces, para aliviar la notación, se omiten paréntesis innecesarios y se escribe \( s\cdot{}t \) en lugar de \( (s\cdot{}t) \).)
Una fórmula se define del siguiente modo:
1. Si \( s \) y \( t \) son términos entonces \( s=t \) es una fórmula.
2. Si \( F \) es una fórmula y \( x_i \) es una variable entonces \( \exists{x_i}F \) es una fórmula.
3. Si \( F \) y \( G \) son fórmulas entonces \( -F \) y \( (F\Rightarrow{}G) \) son fórmulas.
4. Toda fórmula se obtiene por aplicaciones sucesivas (una cantidad finita de veces) de las reglas anteriores.
P.D.: Si no se entiende nada el programa o qué diablos estoy haciendo, a no preocupar, que habrá mejoras en el futuro.
Por hoy me quedé conforme con ver que todo funciona.