Extremadamente probable. Los modelos de cómputo que usan pueden parecer completamente diferentes y extraños para nosotros, pero me sorprendería si no son tan poderosos como un UTM .
Mi razonamiento es simple: hemos encontrado que la computabilidad es una propiedad extremadamente robusta. Es decir, el conjunto de problemas que se pueden calcular en una máquina universal de Turing es equivalente al conjunto de problemas que se pueden calcular con todos los demás métodos razonables de cálculo que hemos considerado¹.
Cálculo de Lambda, funciones recursivas generales, combinadores de SKI, su lenguaje de programación favorito², su lenguaje de programación menos favorito², Fractran (que se ejecuta multiplicando fracciones), una computadora con un conjunto de instrucciones, etc. Tienes la idea. Los sistemas a veces se completan accidentalmente.
- ¿Debo continuar las matemáticas con la ciencia actuarial o cambiar a la informática y por qué?
- ¿La comunidad académica evita los intentos de resolver un problema NP-difícil en tiempo polinómico?
- ¿Se pueden modelar todos los algoritmos iterativos de forma recursiva y viceversa?
- ¿Existe un tipo de conjunto que se define al tener un elemento de tipo 'otro' para el resto del conjunto?
- ¿Cómo calculamos la beta de una acción? ¿Por qué diferentes fuentes informan diferentes valores?
Incluso las reglas de Magic: the Gathering están completas en Turing (dados algunos supuestos mínimos): Magic: the Gathering is Turing Complete .
A mi entender, si bien cualquier modelo de cálculo (como un UTM) es intrínsecamente arbitrario, la clase de funciones que pueden ejecutar surge de forma natural . El alcance de la computabilidad es una propiedad de la computación en general , no de un modelo dado.
Esto es, efectivamente, una reformulación de la Tesis de Turing de la Iglesia . Es la hipótesis de que todas las funciones “efectivamente calculables” (es decir, computables) se pueden calcular en una máquina de Turing. (O con el cálculo lambda sin tipo). “Efectivamente calculable” es una noción particular e intuitiva de lo que significa “computable”; la Enciclopedia de filosofía de Stanford define fácilmente un procedimiento [matemático] M [/ matemático] como efectivamente calculable si cumple los siguientes criterios:
- [math] M [/ math] se establece en términos de un número finito de instrucciones exactas (cada instrucción se expresa mediante un número finito de símbolos);
- [math] M [/ math], si se lleva a cabo sin error, producirá el resultado deseado en un número finito de pasos;
- [matemáticas] M [/ matemáticas] puede (en la práctica o en principio) ser llevado a cabo por un ser humano sin ayuda de ninguna maquinaria, excepto papel y lápiz;
- [matemáticas] M [/ matemáticas] no exige ninguna comprensión o ingenio por parte del ser humano que lo lleva a cabo.
1 y 2 aseguran que sea físicamente posible: si nuestros extraterrestres pueden ejecutar un número infinito de pasos en un tiempo finito, todas las apuestas están canceladas. (Si tienen un oráculo mágico que siempre les da la respuesta correcta, todas las apuestas también están canceladas. Veo los dos casos como más o menos comparables).
3 parece referirse a los humanos, pero está ahí para asegurarnos de que no necesitamos ningún truco físico: no hay aritmética de precisión infinita o fuentes de números reales aleatorios o lo que sea que tenga. 4 asegura esto: el humano está allí para llevar a cabo instrucciones directamente, no para usar su inteligencia.
Entonces la pregunta es: ¿funcionará la computadora del extraterrestre de acuerdo con estos cuatro principios, ni menos ni más?
Veo tres formas posibles en que la computadora del alienígena no es:
- Es estrictamente menos poderoso. Creo que esto es increíblemente improbable, pero posible: en la oscuridad que es la computación, realmente tienes que salir de tu camino para no golpear tu espinilla en la mesa de café de la computabilidad. En serio: los sistemas se vuelven Turing completos por accidente.
¿Extranjeros con algún tipo de razón o tecnología que nunca alcanza ese nivel de poder? ¡Improbable!
- Es estrictamente más poderoso. Esto parece prácticamente imposible. Requeriría que su computadora haga algo fundamentalmente más allá de cualquier cosa que podamos imaginar hacer. Veo que los extraterrestres tienen un hipercomputador como marginalmente menos inverosímil que tener un viaje o comunicaciones más rápidos que la luz³.
- Su poder es ortogonal. Puede hacer algunas cosas que un UTM puede hacer, otras que no puede hacer, pero no es estrictamente más poderoso. Ni siquiera estoy seguro de que esto sea significativo: si a veces puede hacer más, ¿no podría simplemente agruparlo con una computadora normal para obtener un hipercomputador? A menos que me falte algo, esto es igual de improbable.
Considerando todo esto, creo que el caso más probable, con mucho, es que los extraterrestres tienen una computadora que funciona con un modelo equivalente en potencia a un UTM.
notas al pie
¹ Bueno, tal vez tendríamos que extender nuestra cuenta para interactuar con el mundo externo, como se argumenta en “La naturaleza interactiva de la informática: refutar la fuerte tesis de la Iglesia-Turing”, pero creo que esa distinción es mucho menos importante que algunas personas lo hacen parecer. Por otra parte, ni siquiera me he molestado en leer todo ese artículo …
² ¡A menos que seas el tipo de persona perversa que nombra “HTML” o “SQL estándar” o algo más tonto para uno de estos! (Coq, Agda y similares son una discusión más complicada).
³ Supongo que la relatividad general podría permitir a las computadoras que realicen un número infinito de acciones en un tiempo finito, dándonos hipercomputadoras (pero aún sin FTL). Encontré un artículo sobre esto, pero desafortunadamente no me acerco a comprender la física necesaria para analizar mucho más que el resumen: “Cálculos que no son de Turing a través del espacio-tiempo de Malament-Hogarth”.
