En la "Introducción a los teoremas de Gödel" de Peter Smith, ¿por qué se caracterizan tantas propiedades como "efectivamente"

Question

En "Introducción a los teoremas de Gödel", el adverbio " efectivamente " es casi omnipresente: efectivamente enumerable, efectivamente decidible, efectivamente computable, etc.

He aquí algunos ejemplos de citas:

Una propiedad/relación es efectivamente decidible si existe un procedimiento algorítmico...

Una propiedad o relación numérica es efectivamente decidible si su función característica es efectivamente computable.

Una función total de un lugar $f:\Delta\rightarrow \Gamma$ es efectivamente computable si existe un algoritmo...

Hay un conjunto efectivamente enumerable de números $K$ tal que es el complemento $\bar{K}$ no es efectivamente ennumerable.

para una sintaxis debidamente formalizada $\mathcal{L}$ Debe haber procedimientos claros y objetivos... para decidir efectivamente si una supuesta constante-símbolo es realmente una constante...

¿Por qué no se puede indicar la característica o propiedad sin ninguna modificación?

Gracias

Answer 1

En el contexto de "decidible" y "computable", creo que "efectivamente" es sólo para enfatizar, es una forma de intentar recordar al lector que la afirmación es que tal y tal cosa puede hacerse con una máquina, o siguiendo reglas sin sentido (una vez que esas reglas se han construido adecuadamente de una vez por todas). En contraste con lo que puede hacer un matemático humano suficientemente sabio.

Pero no conozco ningún significado relevante de "decidible" y "computable" que no incluya ya implícitamente esto.

"Efectivamente enumerable" es un poco menos vacía, porque algunos autores (que trabajan en otros campos) pueden utilizar "enumerable" como sinónimo de "contable", mientras que "efectivamente enumerable" apunta inequívocamente al tipo de enumeración que se realiza mediante procesos sin sentido. (Esto se conoce más comúnmente como "recursivamente enumerable", pero esa frase es aún menos comprensible intuitivamente, y sonará fuera de lugar ante el argumento de que esto tiene algo que ver con recursividad se ha llevado a cabo).

Answer 2

Henning, Bram y Carl tienen razón, por supuesto, en que mi "efectivamente" es más que nada para enfatizar, para resaltar el tipo de procedimientos de decisión, enumeraciones, axiomatizaciones, etc., que están en cuestión.

Nos preocupa, por ejemplo, lo que es efectivamente decidible, es decir, decidible mediante un procedimiento algorítmico paso a paso y finito (por lo que queremos enfatizar que la apelación a los oráculos, o a los procesos infinitos de hipercomputación, o a cualquier cosa exótica se descarta como procedimiento de "decisión" del tipo que nos interesa).

Por ejemplo, nos preocupa lo que es efectivamente enumerable, es decir, lo que se puede enumerar mediante un procedimiento algorítmico paso a paso (por lo que queremos destacar que no basta con cualquier función de números a widgets para enumerar los widgets de la manera que queremos).

Por ejemplo, nos preocupan las teorías efectivamente axiomatizadas, es decir, las teorías en las que es efectivamente decidible qué es un axioma (por lo que queremos enfatizar que no cualquier grupo de axiomas servirá para el tipo de teorías que nos ocupa).

Y así es. Puede ser que me haya excedido en el uso repetitivo de "efectivamente". Sin embargo, sin releer el capítulo con detenimiento, creo que es mejor no ser explícitamente repetitivo.

Answer 3

La definición de computabilidad de Turing puede considerarse una formalización de la noción más informal de "método eficaz", que en aquella época se entendía como un algoritmo o unas instrucciones paso a paso que un humano sería capaz de entender y realizar. Por lo tanto, al añadir la palabra "eficaz", supongo que Peter Smith está enfatizando el hecho de que cuando habla de computaciones y procedimientos de decisión, se refiere a ese tipo de computaciones, es decir, las que son compatibles con la definición de Turing, en contraposición a formas más exóticas de computación como las hipercomputaciones.