Entscheidungsproblem

Ha llovido desde que geniales maestros como Church y Turing demostraron que el problema de la parada es indecidible. Pero decir esto sabe a poco. La deformación profesional nos lleva a los informáticos (sé que se lleva más el término «developers» pero es que me da grima la palabreja) a intentar tomar decisiones mediante algoritmos. Lo bueno de ser humano es que podemos tomarnos la libertad de saltarnos a Peano (no la peana) e inferir una nueva dimensión (gracias Egan), si hace falta varias de ellas para poder alterar la aritmética lambda y solucionar nuestro conflicto.
Oh ! había olvidado mencionar el problema en cuestión. Lo siento, paso a formularlo (perdonad la libertad) en lenguaje no formal de orden el que queráis:
Dado un programa S y un conjunto de datos L, queremos saber si existe un programa G que teniendo como datos S y L compute si es Software Libre (se pare) o no.
Como ya sabemos en el mundo de Peano PW (Pasta World), el problema es irresoluble, así que haciendo la pirula de inventarme un nuevo mundo JW (Jauja World) resulta que sí, que es posible (la demostración la dejo para otro día).
Pero … hay una pega. Para operar en la dimensión extra de J hay que prescindir de la polis P (gracias Egan, Again 🙂 ).
Ya os contaré como me va en JW …