¿Un lenguaje de programación que solo puede implementar funciones biyectivas computables?

¿Existen lenguajes de programación (o lógica) que puedan implementar (o expresar) una función si y solo si es una función biyectiva computable?$f:\mathbb{N}\to \mathbb{N}$$f$

No hay tal lenguaje.

Sin embargo, eche un vistazo a Boomerang . Es un lenguaje para escribir biyecciones entre cadenas. No sé qué tan amplia es una clase de mapas que se puede expresar en él, pero estoy seguro de que puedes averiguar si buscas un poco.

Es razonable exigir a un lenguaje de programación que el conjunto de programas válidos sea reconocible por un intérprete o un compilador, es decir, que sea un conjunto computablemente enumerable. Supongamos entonces que tenía un lenguaje de programación cuyo conjunto de programas válidos fueron computablemente numerable y el que se desarrolla con precisión todos los bijections computables . Eso implicaría que podemos enumerar de manera computacional todas las biyecciones computables (simplemente enumerar todos los programas válidos en este lenguaje de programación), pero esto es imposible según el siguiente teorema.$\mathbb{N} \to \mathbb{N}$

Teorema: supongamos que es una secuencia computable de biyecciones computables. Luego hay una biyección computable que no está en la secuencia.$f_0, f_1, f_2, \ldots$

Prueba. Construimos una biyección siguiente manera. Para definir los valores g ( 2 k ) y g ( 2 k + 1 ) , observamos f k ( 2 k ) :$g : \mathbb{N} \to \mathbb{N}$$g(2 k)$$g(2 k + 1)$$f_k(2 k)$

• si entonces el conjunto de g ( 2 k ) = 2 k + 1 y g ( 2 k + 1 ) = 2 k ,$f_k(2 k) = 2 k$$g(2 k) = 2 k + 1$$g(2 k + 1) = 2 k$
• si , establezca g ( 2 k ) = 2 k y g ( 2 k + 1 ) = 2 k + 1 .$f_k(2 k) \neq 2 k$$g(2 k) = 2 k$$g(2 k + 1) = 2 k + 1$

Claramente, para cada , g es diferente de f k porque g ( 2 k ) ≠ f k ( 2 k ) . Además, g es computable y es una biyección porque es su propio inverso. QED$k \in \mathbb{N}$$g$$f_k$$g(2 k) \neq f_k(2 k)$$g$