Arkaitz's Blog

Bien, otro post sobre teoria de la computacion -a peticion popular de Kalgan y Trun-. En este caso hablo sobre la imposibilidad de decidir si un programa en Python con un input I escribe por pantalla “Hello world” (no tiene por que ser exclusivamente, solo consideramos los primeros 12 caracteres). Asumamos que tenemos un programa H.py que lo hace, y si le pasamos por parametro eje1.py:

print “Hello world”

responde “si”. Que pasaria si en vez de eje1.py usamos eje2.pseudocodigo -considerando que manejamos numeros sufientemente grandes, etc. y escribimos el programa entero en Python-?

for every x,y,z, n>=3:

if (x^n+y^n==z^n):

print “Hello world”

Si reconocemos el ultimo teorema de Fermat, vemos que este programa no escribe por pantalla “Hello world”. Tambien podemos pensar que seria muy dificil para H.py reconocer que no lo escribe por pantalla. Probemos ahora que es imposible:

En vez de H.py consideramo H1.py, con la unica diferencia que en vez de escribir “si” o “no” escribe “si” o “Hello world”. Este programa es equivalente a H.py.

Moviendo un nivel mas arriba, consideremos el programa H2.py que incluye a H1.py. Recordemos que H1.py recibe como parametros el programa P y la cadena de entrada I. Lo que hace H2.py es recibir un unico parametro, el programa P y pasarselo a H1.py. La salida es la de H1.py, “si” o “Hello world”. Esto es, de analizar P(I) pasamos analizamos P(P). Por lo tanto, si pasamos a un programa su codigo como entrada y este escribiria “Hello world” por pantalla, H2.py nos responde “si” al analizar el programa P. En caso contrario, es decir, el programa con entrada su codigo no tiene como salida “Hello world”, H2.py nos responde “Hello world”. Pero, que pasaria si a H2.py le pasamos a si mismo como parametro? Si H2.py no escribe “Hello world”, deberia escribir “Hello world”. Si escribe “Hello world” deberia escribir “si”. Al llegar a esta contradiccion, se demuestra que es imposible escribir un programa que diga que otro escribe “Hello world” -o cualquier otra cosa u salida- o no.

Por lo tanto la verificacion automatica de programas en general es imposible de alcanzar.

Otra vez otro post relacionado con Computher Theory. La verdad es que nunca se me habia ocurrido pensarlo, seguro que alguno ya se lo planteo en su dia en compiladores II (ese JosuKa). Esta vez es una demostracion de como los compiladores correctos no existen, es decir, los compiladores rechazan programas (cadenas) que son validos (existen en el lenguaje).

Los ordenadores al fin y al cabo son DFA (Automatas Finitos Deterministas). Por muy complicados que sean, o por mucha potencia/memoria/disco que tengan, no pueden aceptar lenguajes no regulares. Un ejemplo es L={(a^n)(b^n) con n e N}. Dado que n no esta acotado y puede ser tan grande como se quiera y el automata debe contener estados finitos, no podemos definir un DFA que acepte este lenguaje.

Ahora bien, en muchos lenguajes de programacion hemos visto que la definicion de una expresion se permite el anidamiento en base a parentesis -entre otras, recordamos gramaticas independientes del contexto en compiladores-:

E -> (E)

-> E+E

-> …
Puede un ordenador aceptar este tipo de cadenas {print “Hola estoy en Python”\n (^n 7 )^n | n>=0}? Por ejemplo:

print “Hola estoy en Python”
(((7)))

siendo n el numero de parentesis que tenemos

Este tipos de cadenas existen en el lenguaje Python, pero a partir de un n suficientemente grande, el interprete de Python cascara. Y es imposible tener un interprete correcto, ya que los ordenadores (DFA) tienen memoria (estados) finita.

Otra forma de mirarlo es que las gramaticas independientes del contexto que definen los lenguajes de programacion reconocen mas lenguajes (conjuntos de cadenas) que los regulares (DFA o ER).

Corolario: Los compiladores correctos no existen

O al menos segun mi profesor de Teoria de la Computacion -y la teoria de conjuntos-.

Tomemos como ejemplo solo los programas en Python (cualquier otro vale) que tomen un entero por la entrada estandar y devuelvan un entero por la salida estandar.

Teorema: El numero de programas en Python legales es contable (e infinito). Llamemosle conjunto P
Prueba: El conjunto P esta ordenado si consideramos el tamanyo en bytes que ocupa cada programa. Si ocupan la misma cantidad de bytes consideramos el orden alfabetico (o numerico segun el codigo maquina que genera, por ejemplo). Al existir este orden, el numero de programas que existen es aleph-0 (ya que cardinalidad(P) es semejante a cardinalidad(N)).

Teorema: El numero de funciones matematicas de la forma f:Z->Z es incontable.

Prueba:Nos restringimos a todas las funciones de la forma f: N->{0,1}

Por ejemplo una funcion que nos diga si un numero es primo o no: {(1,0),(2,1),(3,1),(4,0),(5,1),…}
Si consideramos el conjunto de los numeros primos: {2,3,5,7,…} c N calculamos todos los subconjuntos posibles de este conjunto, es decir, el conjunto potencia. Cada uno de ellos representa una funcion matematica de la forma { x | f(x)=1}.
Hallamos la cardinalidad de este conjunto card(2 elevado a N)=2 elevado a card(N)=2 elevado a aleph-0=aleph-1

Si el numero de funciones es incontable (aleph-1) y el numero de programas posibles es contable (aleph-0), cual es la probabilidad de que dada una funcion cualquiera pueda escribir un programa legal en Python que la implemente? Cero

Corolario: Las computadoras son inutiles