Uma linguagem de programação que só pode implementar funções bijetivas computáveis?

Existem linguagens de programação (ou lógica) que podem implementar (ou expressar) uma função se e somente se for uma função bijetiva computável? $f:\mathbb{N}\to \mathbb{N}$ $f$

reference-request programming-languages logic reversible-computing Chao Xu
fonte

Alguém me provou que é impossível criar uma linguagem que aceite apenas programas de encerramento. Já que sua pergunta é bem parecida, acho que não.

FUZxxl

Parece improvável que exista essa linguagem de programação, acho que você poderia tentar aplicá-la, mas não seria capaz de fazer coisas simples como classificar, pelo menos não sem que se tornasse terrivelmente complexo e doloroso.

Luke Mathieson

@FUZxxl Isso não captura muitos programas que terminam; de fato, mesmo a função f (x) = 1 é impossível de expressar nesta linguagem. Também sinto que esse tipo de função é capturado pela programação funcional total, pois toda função é uma função total.

Chao Xu

@FUZxxl, não acho isso certo, mas esse idioma teria que ser limitado. Por exemplo, seria garantido que um idioma equivalente aos autômatos determinísticos finitos terminasse, mas seria extremamente limitado no que poderia calcular.

jmite

@FUZxxl, os detalhes dessa declaração são importantes. É fácil projetar uma linguagem de programação na qual todo programa termina. É uma questão diferente projetar uma linguagem que possamos expressar todas as funções computáveis.

Vijay D

Respostas:

Não existe esse idioma.

No entanto, dê uma olhada no Boomerang . É um idioma para escrever bijections entre strings. Não sei a extensão de uma classe de mapas, mas tenho certeza de que você poderá descobrir se pesquisar um pouco.

É razoável exigir de uma linguagem de programação que o conjunto de programas válidos seja reconhecível por um intérprete ou compilador, ou seja, que seja um conjunto computávelmente enumerável. Suponhamos que tivéssemos uma linguagem de programação cujo conjunto de programas válidos fosse computável enumerável e que implementasse com precisão todas as bjeções computáveis . Isso implicaria que podemos enumerar computacionalmente todas as bijeções computáveis (simplesmente enumerar todos os programas válidos nessa linguagem de programação), mas isso é impossível no próximo teorema. $\mathbb{N} \to \mathbb{N}$

Teorema: Suponha que é uma sequência computável de bijections computáveis. Depois, há uma bijeção computável que não está na sequência. $f_0, f_1, f_2, \ldots$

Prova. Construímos uma bijeção seguinte maneira. Para definir os valores e , examinamos : $g : \mathbb{N} \to \mathbb{N}$ $g(2 k)$ $g(2 k + 1)$ $f_k(2 k)$

se então o conjunto e , $f_k(2 k) = 2 k$ $g(2 k) = 2 k + 1$ $g(2 k + 1) = 2 k$
se então o conjunto e . $f_k(2 k) \neq 2 k$ $g(2 k) = 2 k$ $g(2 k + 1) = 2 k + 1$

Claramente, para cada , é diferente de porque . Além disso, é computável e é uma bijeção porque é o seu próprio inverso. QED. $k \in \mathbb{N}$ $g$ $f_k$ $g(2 k) \neq f_k(2 k)$ $g$

Andrej Bauer
fonte

Por que você ainda precisa desse truque de e ? Usar deve ser suficiente.

2 k

$2k$

2 k + 1

$2k+1$

g (k) = f_{k} (k) + 1

$g(k)=f_k(k)+1$

FUZxxl

@FUZxxl: se você usar a função resultante não é surjective

f_{k} (k) + 1

$f_k(k)+1$

Vor

Você precisa ter certeza de que é bijetivo.

g

$g$

21312 Andrej Bauer

A afirmação inicial está errada, existem muitas dessas línguas na literatura.

Nathaniel

Por outro lado, sua prova parece legítima. Talvez eu esteja confuso de alguma forma. Preciso ler o artigo de Axelsen e Glück (veja minha resposta) com cuidado para descobrir o que está acontecendo aqui.

187 Nathaniel