¿Existe una noción de computabilidad en conjuntos distintos de los números naturales?

¿Existe una noción de computabilidad en conjuntos distintos de los números naturales? En aras de la discusión, digamos en los conjuntos que se biject con .$S$$\mathbb{N}$

Es tentador decir "sí, son aquellas funciones de la forma donde es cualquier biyección y es cualquier función computable ". Soy cauteloso con esta definición por dos razones. g N → S f N → $g \circ f \circ g^{-1}$$g$$\mathbb{N} \to S$$f$$\mathbb{N} \to \mathbb{N}$

1. Privilegia sobre otros conjuntos contables. ¿Por qué es especial cuando se trata de definir la computabilidad? Me gustaría una definición de computabilidad "libre de coordenadas" sin referencia a ningún conjunto privilegiado de la misma manera que me gustaría una definición "libre de coordenadas" de un concepto de álgebra lineal sin referencia a ninguna base privilegiada.$\mathbb{N}$$\mathbb{N}$

2. Plantea preguntas sobre la elección de . Sospecho que puede ser posible encontrar contradicciones mediante elecciones particularmente patológicas de y . Por ejemplo, si elijo y alguna biyección no computable, ¿es realmente el caso de que es computable para todos los computables ?S g S = N g g ∘ f ∘ g - 1$g$$S$$g$$S = \mathbb{N}$$g$$g \circ f \circ g^{-1}$$f$

   Es tentador exigir en la definición que sea ​​computable, pero desafortunadamente esa es la pregunta.$g$

¿Hay alguna forma general de describir la computabilidad en conjuntos contables distintos de ?$\mathbb{N}$

Esta pregunta no es de nivel de investigación, pero dado que está recibiendo respuestas, me gustaría ofrecer una respuesta que realmente aclare un poco las cosas y proporcione referencias.

Existe un área completa de informática teórica que estudia la computabilidad en análisis, álgebra y topología. De importancia central es la noción de computabilidad para números reales. De hecho, el artículo original de Turing sobre máquinas Turing comienza con la siguiente oración:

Los números "computables" pueden describirse brevemente como los números reales cuyas expresiones como un decimal son calculables por medios finitos.

A veces vale la pena volver a la fuente.

Hay varias formas de configurar la computabilidad en conjuntos generales, de las cuales una de las más generales es la teoría de la realizabilidad . La idea de la teoría de la realizabilidad se remonta al artículo de Kleene sobre la interpretación de la teoría intuitiva de números de 1945, pero desde entonces se ha generalizado y desarrollado en una mini rama de computabilidad, con una buena combinación de teoría de categorías, ver por ejemplo el libro de Jaap van Oosten "Realizabilidad: una introducción a su lado categórico" (Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008).

Permítanme describir la idea de realizabilidad muy brevemente, y discutir su requisito de "coordenadas libres" más adelante. Comience con un modelo de computación, como las máquinas de Turing, el cálculo , un lenguaje de programación o cualquier otro álgebra combinatoria parcial (incluso puede tomar ciertos espacios topológicos para ser "modelos de computación", esto es general ). Para concretar, consideremos las máquinas de Turing. Codificamos las máquinas de Turing por números naturales, pero tenga en cuenta que podría haber tomado algún otro modelo de cálculo, por lo que no debe suponer que el uso de$\lambda$N λ$\mathbb{N}$es de alguna manera esencial aquí. (Otras posibilidades incluyen: el conjunto de poder de los números naturales, secuencias infinitas de números naturales, la sintaxis del cálculo de tipo, ciertas categorías de juegos, etc.)$\lambda$

Una estructura de computabilidad en un conjunto viene dada por una relación entre y , llamada relación de realizabilidad , de modo que para cada hay tal que . Llamamos a estas estructuras conjuntos . Esta definición se corresponde directamente con la idea intuitiva de que alguna pieza de datos respresents, o se da cuenta , un elemento . (Por ejemplo, ciertas secuencias de bits representan listas finitas de pares de cadenas de caracteres).$X$$\Vdash_X$$\mathbb{N}$$X$$x \in X$$n \in \mathbb{N}$$n \Vdash_X x$$n$$x \in X$

Dados dos conjuntos y , un mapa se dio cuenta (o "computable") si hay una máquina de Turing , de manera que, cuando luego termina y . De nuevo, esta es una transliteración directa de lo que significa informalmente "programar" una función abstracta : la máquina de Turing correspondiente hace para representar datos, lo que sea que haga a los elementos correspondientes.$(X, {\Vdash_X})$$(Y, {\Vdash_Y})$$f : X \to Y$$T$$n \Vdash_X x$$T(n)$$T(n) \Vdash_Y f(x)$$f$$f$

Las asambleas pueden extenderse a un topos de realización . Un topos es un modelo de matemática intuicionista de orden superior. Esto nos dice que cada topos de realizabilidad (hay uno para cada modelo de cálculo) contiene muchos objetos interesantes. Por ejemplo, contiene un objeto de números reales, lo que nos da computabilidad en reales. Pero también contiene muchos otros objetos, como espacios de Hilbert, espacios de Banach, espacios de mapas suaves, etc. Solicitó alguna otra estructura computable, pero obtuvo algo mucho mejor: mundos matemáticos enteros de computabilidad.

Dado que la teoría de categorías y los topos pueden dar miedo y requieren una cierta cantidad de competencia técnica en teoría de computabilidad, teoría de categorías y lógica, también podríamos trabajar en un solo topos concreto, pero expresamos todo de manera concreta y no abstracta. Un mundo particularmente bueno de computación surge de la realizabilidad de la función de Kleene , y se conoce con el nombre de análisis computable .

Permítanme comentar sobre el requisito de "coordenadas libres":

• Cambiar entre modelos de computación da diferentes tipos de mundos computables. Esto es un poco como cambiar entre diferentes campos dando diferentes tipos de álgebra lineal.

• Un conjunto puede estar equipado con muchas estructuras de computabilidad , al igual que un conjunto de vectores tiene muchas bases. Sin embargo, aunque todas las bases son equivalentes, no todas las estructuras de computabilidad en son computablemente equivalentes.$X$$\Vdash_X$$X$

• Si trabajamos concretamente con estructuras de computabilidad , eso es un poco como trabajar con matrices en álgebra lineal. Puede ser muy útil, pero no es abstracto.$(X, {\Vdash_X})$

• Para trabajar de manera "libre de coordenadas", trabajamos de manera realizable para aprovechar y aprovechar el poder de la teoría de categorías (sí, es un cliché pero funciona).

• Incluso podemos trabajar de una manera "libre de mundo": desarrollar las matemáticas en la lógica intuicionista y luego interpretar los resultados en términos de realizabilidad.

Los dos documentos a continuación desarrollan una noción de computabilidad para conjuntos arbitrarios. Curiosamente, incluso una noción de teoría de la complejidad se puede definir para este modelo de computación.

Funciones de conjuntos recursivos de Cobham y teorías de conjuntos débiles Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Recursión limitada por subconjuntos y un modelo de circuito para las funciones recursivas de Cobham Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller, Neil Thapen.

Existe un concepto de complejidad y cálculo sobre los reales. Un libro de texto al que le dirijo es: https://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817

Sé de un laboratorio que estudia esto específicamente: https://complexity.kaist.ac.kr/

Esto es similar a cómo definimos la computabilidad en términos de máquinas de Turing y luego nos olvidamos rápidamente de las máquinas de Turing. Como resulta que una máquina de Turing es una definición tan buena como cualquier otra, la usamos como un ancla para una clase completa de modelos de equivalencia, y terminamos con la misma clase sin importar desde qué elemento la generemos. Básicamente esta es la tesis de Church-Turing y define el conjunto de cadenas de bits computables.

Del mismo modo, para definir computabilidad en un conjunto diferente , anclamos con una función parcial en particular de cadenas de bits a . En realidad, no importa si esta función es una biyección o una inyección o cualquier otro tipo de función (para un caso en el que realmente no queremos que sea una inyección, considere un grupo definido por su presentación donde no tenemos Una representación única para sus elementos). Ni siquiera tiene que ser una sorpresa si permitimos que los conjuntos de singleton sean indiscutibles. Al componer esta función con cualquier biyección computable de cadenas de bits a cadenas de bits (un concepto ya definido), obtenemos una definición de computabilidad para$S$$S$$S$eso es invariable con respecto a la función que elegimos originalmente (siempre que hayamos elegido algo razonable). Es decir, una tesis TC para nuestro conjunto . Pero si no elegimos una función razonable, obtenemos una definición diferente de computabilidad.$S$

Esta función también sirve para definir la computabilidad de otras funciones con dominio o rango igual a . Al cambiar el rango de , manteniendo el dominio como , sino que también obtenemos un definición -invariant de la complejidad de Kolmogorov de . Y finalmente podemos decir que la función que hemos elegido es en sí computable.$S$$S$$\{0,1\}^*$$O(1)$$S$

Entonces creo que la respuesta a su pregunta es NO. Tenemos que definir la computabilidad para cada conjunto del que queremos hablar, porque hay definiciones no equivalentes. Aparte de una discusión muy técnica o pedagógica, no debería ser necesario, ya que una persona razonable puede imaginar una definición razonable de forma independiente.

Pero espera, deja que sea ​​un conjunto infinitamente contable, y eso es todo. ¿Cuál es nuestra definición razonable de computabilidad para ? Saber que el conjunto de biyecciones entre y no está vacío no nos dice cuáles son razonables. No tenemos suerte sin más detalles.$S$$S$$S$$\{0,1\}^*$

Y podemos encontrar múltiples alternativas no equivalentes pero igualmente razonables. Supongamos que cada árbol tiene una cantidad de hojas rojas y otra cantidad de hojas verdes, y que por cada existe exactamente un árbol con hojas rojas, y que por cada existe exactamente un árbol con hojas verdes. Ambas biyecciones son razonables en el sentido de que podemos contar las hojas y distinguir los colores, y podemos caminar sin rumbo por el bosque contando hojas en los árboles hasta que encontremos el árbol con exactamente hojas verdes, o el que tenga$r \in \mathbb{N}$$r$$g \in \mathbb{N}$$g$$23$$23$hojas rojas. No está claro si identificar un árbol utilizando su recuento de hojas rojas o su recuento de hojas verdes, ya que esta elección conduce a definiciones inequívocas de computabilidad para conjuntos de árboles. Si, en cambio, hacemos nuestra definición combinando los recuentos con una función de emparejamiento computable biyectiva de a (que tiene una computabilidad definida adecuadamente en ), que también identifica de forma única cada uno árbol, pero la situación es aún peor porque esto no es una biyección entre árboles y , ¡ahora quizás todos los conjuntos de árboles computables son finitos!$\mathbb{N}^2$$\mathbb{N}$$\mathbb{N}^2$$\mathbb{N}$

Entonces, para evitar toda la discusión, debe entenderse no solo que existe una definición razonable de computabilidad en el conjunto en cuestión, sino también que hay exactamente una clase de definiciones razonables.

Creo que la situación se vuelve mucho más interesante si incorporamos la complejidad del tiempo. Incluso cuando solo consideramos números enteros, nuestras elecciones son más importantes. Por ejemplo, ¿qué pasaría si quisiéramos representar cada número como una suma de cuatro cuadrados? Podemos encontrar dicha representación, comenzando desde una representación base, en el tiempo cuadrático esperado con acceso a aleatoriedad. O, en cambio, como una lista de sus factores primos, que pueden o no ser posibles de calcular en tiempo polinómico. En la medida en que permitimos representaciones duras, perdemos precisión en la complejidad del tiempo. Por ejemplo, no podemos decir de manera significativa que alguna función es computable en tiempo cuadrático si tenemos una representación de$F:\mathbb{N} \rightarrow \mathbb{N}$$\mathbb{N}$eso podría requerir más de un tiempo cuadrático para convertir hacia o desde una representación base. Creo que esta perspectiva revela que la representación base es un estándar algo arbitrario. (Estándar en el sentido de que la representación básica es lo que alguien tiene en mente cuando dice algo como " es computable en tiempo cuadrático", si el modelo subyacente es uno que computa bit cadenas de cadenas de bits y se supone que debemos inferir el significado).$F:\mathbb{N} \rightarrow \mathbb{N}$