Existe uma noção de computabilidade em conjuntos diferentes dos números naturais?

Existe uma noção de computabilidade em conjuntos diferentes dos números naturais? Por uma questão de argumento, vamos dizer em conjuntos $S$ que biject com $\mathbb{N}$ .

É tentador dizer "sim, eles são aquelas funções da forma , onde g é qualquer bijection N → S e f é qualquer função computável N → N ". Sou cauteloso com essa definição por dois motivos.$g \circ f \circ g^{-1}$$g$$\mathbb{N} \to S$$f$$\mathbb{N} \to \mathbb{N}$

1. Privilegia sobre outros conjuntos contáveis. Por que N é especial quando se trata de definir computabilidade? Eu gostaria de uma definição "livre de coordenadas" de computabilidade sem referência a qualquer conjunto privilegiado da mesma maneira que eu gostaria de uma definição "livre de coordenadas" de um conceito de álgebra linear sem referência a nenhuma base privilegiada.$\mathbb{N}$$\mathbb{N}$

2. Isso levanta questões sobre a escolha de . Suspeito que seja possível encontrar contradições por escolhas particularmente patológicas de S e g . Por exemplo, se eu escolher S = N e g, alguma bijeção não computável é realmente o caso em que g ∘ f ∘ g - 1 é computável para todos os f computáveis ?$g$$S$$g$$S = \mathbb{N}$$g$$g \circ f \circ g^{-1}$$f$

   É tentador exigir na definição que seja computável, mas infelizmente isso está implorando para a pergunta.$g$

Existe alguma maneira geral de descrever a computabilidade em conjuntos contáveis ​​diferentes de ?$\mathbb{N}$

Esta pergunta não é de nível de pesquisa, mas como está recebendo respostas, eu gostaria de oferecer uma resposta que possa esclarecer um pouco as coisas e fornecer referências.

Existe toda uma área da ciência da computação teórica que estuda a computabilidade em análise, álgebra e topologia. De importância central é a noção de computabilidade para números reais. De fato, o artigo original de Turing sobre máquinas de Turing começa com a seguinte frase:

Os números "computáveis" podem ser descritos brevemente como os números reais cujas expressões em forma decimal são calculáveis ​​por meios finitos.

Às vezes vale a pena voltar à fonte.

Existem várias maneiras de configurar a computabilidade em conjuntos gerais, dentre as quais uma das mais gerais é a teoria da realizabilidade . A idéia da teoria da realizabilidade remonta ao artigo de Kleene Sobre a Interpretação da Teoria dos Números Intuicionistas, de 1945, mas desde então foi generalizada e desenvolvida em um mini ramo da computabilidade, com uma boa mistura de teoria das categorias, veja, por exemplo, o livro de Jaap van Oosten "Realizabilidade: uma introdução ao seu lado categórico" (Estudos em Lógica e os Fundamentos da Matemática, vol. 152, Elsevier, 2008).

Deixe-me descrever a idéia de realização muito brevemente e discutir seu requisito de "coordenação livre" posteriormente. Comece com um modelo de computação, como máquinas de Turing, o $\lambda$ cálcio, uma linguagem de programação ou qualquer outra álgebra combinatória parcial (você pode até considerar certos espaços topológicos como "modelos de computação", essas coisas são gerais ). Para concretude, vamos considerar as máquinas de Turing. Codificamos as máquinas de Turing por números naturais, mas note que eu poderia ter adotado outro modelo de computação, portanto, você não deve assumir que o uso de $\mathbb{N}$ é essencial aqui. (Outras possibilidades incluem: o conjunto de números naturais, sequências infinitas de números naturais, a sintaxe dos números não digitados$\lambda$ -calculus, certas categorias de jogos, etc.)

Uma estrutura de computabilidade em um conjunto $X$ é dada por uma relação $\Vdash_X$ entre $\mathbb{N}$ e $X$ , chamada de relação de realizabilidade , de modo que para cada $x \in X$ existe $n \in \mathbb{N}$ tal que $n \Vdash_X x$ . Chamamos essas estruturas de montagens . Essa definição corresponde diretamente à idéia intuitiva de que algum dado $n$ representa ou realiza um elemento $x \in X$. (Por exemplo, certas seqüências de bits representam listas finitas de pares de cadeias de caracteres.)

Dadas duas montagens $(X, {\Vdash_X})$ e $(Y, {\Vdash_Y})$ , um mapa $f : X \to Y$ é realizado (ou "computável") se houver uma máquina de Turing $T$ , de modo que, sempre que $n \Vdash_X x$ , $T(n)$ termina e $T(n) \Vdash_Y f(x)$. Novamente, essa é uma transliteração direta do que significa informalmente "programar" uma função abstrata $f$ : a máquina de Turing correspondente faz para representar dados o que $f$ faz com os elementos correspondentes.

Os assemblies podem ser estendidos para um topos de realização . Um topos é um modelo de matemática intuicionista de ordem superior. Isso nos diz que todos os tópicos de realização (existe um para cada modelo de computação) contêm muitos objetos interessantes. Por exemplo, ele contém um objeto de números reais, o que nos dá computabilidade em reais. Mas também contém muitos outros objetos, como espaços de Hilbert, espaços de Banach, espaços de mapas suaves, etc. Você solicitou alguma outra estrutura computável, mas obteve algo muito melhor: mundos matemáticos inteiros da computabilidade.

Como a teoria da categoria e as toposes podem ser assustadoras e requerem certa proficiência técnica em teoria da computabilidade, teoria das categorias e lógica, também poderíamos trabalhar em apenas uma topos concreta, mas expressamos tudo de maneiras não-abstratas concretas. Um mundo particularmente bom da computação surge da capacidade de realização de Kleene e é chamado de análise computável .

Deixe-me comentar sobre o requisito "sem coordenadas":

• Alternar entre modelos de computação fornece diferentes tipos de mundos computáveis. É um pouco como alternar entre campos diferentes, fornecendo diferentes tipos de álgebra linear.

• Um conjunto $X$ pode ser equipado com muitas estruturas de computabilidade $\Vdash_X$ , assim como um conjunto de vetores tem muitas bases. No entanto, embora todas as bases sejam equivalentes, nem todas as estruturas de computabilidade em $X$ são computáveis ​​equivalentes.

• Se trabalharmos concretamente com estruturas de computabilidade $(X, {\Vdash_X})$ , é um pouco como trabalhar com matrizes na álgebra linear. Pode ser muito útil, mas não é abstrato.

• Para trabalhar de forma "livre de coordenadas", trabalhamos de forma realizável e aproveitamos o poder da teoria das categorias (sim, é um clichê, mas funciona).

• Podemos até trabalhar de uma maneira "livre do mundo": desenvolver a matemática na lógica intuicionista e depois interpretar os resultados em topos de realização.

Os dois artigos abaixo desenvolvem uma noção de computabilidade para conjuntos arbitrários. Curiosamente, mesmo uma noção de teoria da complexidade pode ser definida para esse modelo de computação.

Funções recursivas dos conjuntos de Cobham e teorias fracas dos conjuntos Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller e Neil Thapen.

Recursão limitada por subconjuntos e um modelo de circuito para funções recursivas de conjuntos de Cobham Arnold Beckmann, Sam Buss, Sy-David Friedman, Moritz Müller e Neil Thapen.

Existe um conceito de complexidade e computação sobre os reais. Um livro que eu diria para você é: https://www.amazon.com/Complexity-Real-Computation-Lenore-Blum/dp/0387982817

Conheço um laboratório que estuda isso especificamente: https://complexity.kaist.ac.kr/

Isso é semelhante à forma como definimos a computabilidade em termos de máquinas de Turing e depois esquecemos prontamente as máquinas de Turing. Como a máquina de Turing tem uma definição tão boa quanto qualquer outra, nós a usamos como uma âncora para toda uma classe de modelos de equivalência e terminamos com a mesma classe, independentemente do elemento em que a gerarmos. Basicamente, esta é a tese de Church-Turing e define o conjunto de cadeias de bits computáveis.

$S$$S$$S$$S$

$S$$S$$\{0,1\}^*$$O(1)$$S$

Então, acho que a resposta para sua pergunta é NÃO. Temos que definir a computabilidade para cada conjunto sobre o qual queremos falar, porque existem definições não equivalentes. Além de uma discussão muito técnica ou pedagógica, isso não seria necessário, pois uma pessoa razoável pode imaginar uma definição razoável de forma independente.

$S$$S$$S$$\{0,1\}^*$

E podemos encontrar várias alternativas desiguais, mas igualmente razoáveis. Suponha que toda árvore tenha um número de folhas vermelhas e um número de folhas verdes, e que para cada$r \in \mathbb{N}$$r$$g \in \mathbb{N}$$g$$23$$23$$\mathbb{N}^2$$\mathbb{N}$$\mathbb{N}^2$$\mathbb{N}$

Portanto, para evitar toda a discussão, deve ser entendido não apenas que existe uma definição razoável de computabilidade no conjunto em questão, mas também que existe exatamente uma classe de definições razoáveis.

$F:\mathbb{N} \rightarrow \mathbb{N}$$\mathbb{N}$$F:\mathbb{N} \rightarrow \mathbb{N}$