5.4: Funciones representables y programas informáticos

En esta sección investigaremos la relación entre funciones representables y programas de cómputos. Nuestra discusión será bastante informal y se basará en tu intuición sobre computadoras y cálculos.

Una de las razones por las que debemos ser más bien informales a la hora de discutir el cálculo es que la idea de un cálculo es bastante vaga. A mediados de la década de 1930 muchos matemáticos desarrollaron constructos teóricos que intentaban capturar la idea de una función calculable. Las funciones recursivas de Kurt Gödel (ahora llamadas a menudo funciones computables), las Máquinas Turing de Alan Turing y el\(\lambda\) cálculo de Alonzo Church son tres de los modelos más conocidos de computabilidad.

Una de las razones por las que los matemáticos aceptan estos constructos formales como modelos precisos de la noción intuitiva de calculabilidad es que todos los análogos formales de computación que se han propuesto han demostrado ser equivalentes, y cada uno de ellos también es equivalente a la noción de representabilidad que definimos en la última sección. Así se sabe que una función es Turing computable si y sólo si es recursiva general si y sólo si es\(\lambda\) -computable. También se sabe que estas nociones formales equivalen a la idea de que una función sea computable en una computadora, donde diremos que una función\(f\) es computable en una computadora idealizada si hay un programa de computadora\(P\) tal que si el programa\(P\) se ejecuta con entrada\(n\), el programa hará que la computadora salga\(f \left( n \right)\) y se detenga.

Así la situación es así: Por un lado, tenemos una idea intuitiva de lo que significa que una función sea efectivamente calculable. Por otro lado, tenemos una gran cantidad de modelos formales de cómputos, cada uno de los cuales se sabe que es equivalente a todos los demás:

\[\begin{array}{c||c} \text{Intuitive Notion} & \text{Formal Models} \\ \hline \hline & \text{Representable function} \\ & \text{Computable function} \\ \text{Calculable function} & \lambda-\text{Computable function} \\ & \text{Turing-computable function} \\ & \text{Computer-computable function} \\ & \vdots \end{array}\]

Entonces, ¿por qué decimos que la idea de un cálculo es vaga? Aunque todas las definiciones actuales son equivalentes, por lo que sabemos puede haber una nueva definición de cálculo que se te ocurra esta noche con una cerveza. Esa nueva definición será intuitivamente correcta, en el sentido de que las personas que escuchan tu definición coincidan en que es la definición “correcta” de lo que significa para una persona calcular algo, pero tu definición bien puede no ser equivalente a las definiciones actuales. Este será un desarrollo estremecedor y dará a los lógicos y a los informáticos mucho en lo que pensar en los próximos años.

¡Pasarás a la historia como una persona brillante con gran perspicacia en el funcionamiento de la mente humana!

¡Ganarás muchos premios y serás rico y famoso!

Bien, lo admitimos. No rico. Simplemente famoso.

OK. A lo mejor no es famoso. Pero al menos bien conocido en los círculos de lógica e informática.

Pero hasta que no tengas esa cerveza tendremos que ir con la situación actual, donde tenemos varias definiciones equivalentes que parecen encajar con nuestra comprensión actual de la palabra cómputo. Entonces nuestra idea de lo que constituye un cálculo es imprecisa, a pesar de que hay precisión en el sentido de que mucha gente ha pensado en cuál debería ser la definición, y cada definición que se ha propuesto hasta ahora se ha demostrado (precisamente) ser equivalente a cualquier otra definición que haya sido propuesto.

La Tesis de la Iglesia es simplemente una expresión de la creencia de que los modelos formales de computación representan con precisión la idea intuitiva de una función calculable. Vamos a exponer la tesis en términos de representabilidad, ya que hemos estado trabajando con funciones representables y conjuntos representables.

Tesis de Iglesia

Una función total\(f\) es calculable si y sólo si\(f\) es representable.

Ahora es importante entender que la Tesis de Iglesia es una “tesis” a diferencia de un “teorema” y que nunca será un teorema. Como intento de vincular una noción intuitiva (calculabilidad) y una noción formal (representabilidad) no es el tipo de cosas que jamás se podrían probar. Las pruebas requieren definiciones formales, y si escribimos una definición formal de función calculable, habremos subvertido el significado de la tesis.

Para agregar otra capa a esta discusión, considere la función\(f\) que asigna a cada número natural su número natural raíz cuadrada, si tiene una. Diremos que no\(f \left( n \right)\) está definido si no\(n\) es un cuadrado. Entonces\(f \left( 9 \right) = 3\) y no\(f \left( 10 \right)\) se define. Esta función parcial parece ser calculable, y de hecho aquí hay algún pseudo-código que calcularía los valores de salida para\(f\):

Para ser un poco más precisos, diremos que una función parcial\(f : A \subseteq \mathbb{N} \rightarrow \mathbb{N}\) es calculable si existe un algoritmo o cómputo que, dada la entrada\(n \in \mathbb{N}\), realiza exactamente una de las siguientes:

• Si\(f \left( n \right)\) se define, el algoritmo calcula el valor correcto de\(f \left( n \right)\), salidas\(f \left( n \right)\) y luego se detiene;
• Si no\(f \left( n \right)\) está definido, el algoritmo se ejecuta para siempre sin parar.

Entonces, si la función\(f\) es total y calculable, hay un algoritmo que calculará\(f \left( n \right)\) para cualquier entrada\(n\), pero si\(g\) es parcial y calculable, entonces\(g\) el algoritmo se detendrá cuando\(g \left( n \right)\) esté definido, pero se ejecutará para siempre si no\(g \left( n \right)\) está definido.

Diremos que un conjunto\(S \subseteq \mathbb{N}\) es calculable si su función característica,\(\chi_S\), es calculable. (Véase el Ejercicio 5 en la Sección 5.3 para la definición de\(\chi_S\).)

Dado que el estudio de la computación conduce de manera bastante natural a la investigación de funciones parciales, la Tesis de la Iglesia a menudo se plantea en términos de funciones parciales:

tesis de iglesia

Una función parcial\(f\) es calculable si y sólo si\(f\) es débilmente representable.

El vínculo entre las dos versiones de la Tesis de Iglesia radica en la Proposición 5.3.6. Usando esa proposición, es fácil ver que la versión de función total de la Tesis de Iglesia sigue inmediatamente de la versión de función parcial.

Para un ejemplo del tipo de pregunta que se puede abordar pensando en conjuntos y funciones calculables, considere lo siguiente:

La clase de conjuntos calculables de se\(\mathbb{N}\) puede extender observando la colección de conjuntos de tal manera que haya un programa de computadora que le dirá si un número es un elemento del conjunto, pero no tiene que hacer nada en absoluto si el número no es un elemento del conjunto. Informalmente,\(A \subseteq \mathbb{N}\) se dice que un conjunto es semi-calculable si hay un programa de computadora\(P\) tal que si\(a \in A\), programa\(P\) devuelve 0 en la entrada\(a\), y si\(a \notin A\), programa\(P\) no se detenga cuando se le da entrada\(a\). Se puede comprobar que esto equivale a decir que la función parcial\(\overset{\smallsmile}{\chi}_A : A \rightarrow \mathbb{N}\) que toma el valor 0 por cada elemento de su dominio es calculable.

Si aceptamos la Tesis de Iglesia, es fácil argumentar que conjunto\(A\) es representable si y sólo si ambos\(A\) y\(\mathbb{N} - A\) son semicalculables, como se le pide que haga en el Ejercicio 6. Otros ejercicios proporcionan un poco más de práctica en el trabajo con conjuntos semi-calculables.

El estudio de las funciones computables es un área importante de la lógica matemática, y enfatiza el vínculo entre la lógica y la informática. El capítulo 7 está dedicado a presentar una introducción a las funciones computables que conduzca a una prueba del Teorema de Incompletitud de Gödel. En esta configuración, la sentencia del Teorema de Incompletitud equivale a la afirmación de que la colección de oraciones que son probable-from-\(\Sigma\), donde\(\Sigma\) es una extensión de\(N\) eso es decidible y true-in-\(\mathfrak{N}\), es un conjunto semi-computable que no es computable. Por lo tanto, existe una diferencia significativa entre la colección de conjuntos computables y la colección de conjuntos semi-computables. Otro texto que enfatiza la computabilidad en su tratamiento del Teorema de Gödel es [Keisler y Robbin 96].

Entonces, ¿es cierta la Tesis de Iglesia? Podemos decir que toda la evidencia hasta la fecha parece sugerir que la Tesis de Iglesia es cierta, pero tenemos miedo de que esa sea toda la certeza que podamos tener en ese punto. Contamos con más de 70 años de experiencia desde la declaración de la tesis, y más de 3000 años desde que iniciamos funciones de computación, pero eso solo cuenta como evidencia anecdótica. Aun así, la mayoría, si no todos, de la comunidad matemática acepta la identificación de “computable” con “representable” y así la comunidad acepta la Tesis de la Iglesia como un artículo de fe.

Ejercicios

1. Definimos funciones calculables y conjuntos semicalculables en esta sección, pero las definiciones no se establecen en su propio bloque y se les dan números elegantes, como “Definición 5.4.2”. ¿Por qué no hicimos las definiciones oficiales con ese aspecto?
2. Utilizando la Tesis de Iglesia, mostrar que\(A \subseteq \mathbb{N}\) es calculable si y sólo si\(A\) es representable. Entonces mostrar que\(A\) es semicalculable si y sólo si\(A\) es débilmente representable.
3. (a) Mostrar que\(A \subseteq \mathbb{N}\) es semicalculable si y sólo si\(A\) es listable, donde un conjunto es listable si existe un programa de computadora\(L\) tal que\(L\) imprima, en algún orden u otro, los elementos de\(A\).
   (b)\(A \subseteq \mathbb{N}\) La demostración es calculable si y sólo si\(A\) es listable en orden creciente.
4. Supongamos que eso\(A \subseteq \mathbb{N}\) es infinito y semicalculable y demuestra que hay un conjunto infinito\(B \subseteq A\) tal que\(B\) es calculable.
5. Mostrar que\(A \subseteq \mathbb{N}\) es semicalculable si y sólo si hay una\(\Sigma\) -fórmula\(\phi \left( x \right)\) tal que\(\phi\) defina\(A\).
6. Usa la Tesis de Iglesia para demostrar que un conjunto\(A\) es representable si y solo si ambos\(A\) y\(\mathbb{N} - A\) son semicalculables. [Sugerencia: Primero asuma que\(A\) es representable. Esta dirección es fácil. Para la otra dirección, el supuesto garantiza la existencia de dos programas. Piensa en escribir un nuevo programa que ejecute estos dos programas en tándem: primero ejecutas un programa por un minuto, luego ejecutas el segundo programa por un minuto...]