Bahasa pemrograman yang hanya dapat mengimplementasikan fungsi bijective yang dapat dikomputasi?

Apakah ada bahasa pemrograman (atau logika) yang dapat mengimplementasikan (atau mengekspresikan) fungsi jika dan hanya jika adalah fungsi bijektif yang dapat dihitung? $f:\mathbb{N}\to \mathbb{N}$ $f$

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

Seseorang membuktikan kepada saya bahwa tidak mungkin membuat bahasa yang hanya menerima program terminasi. Karena pertanyaan Anda sangat mirip, saya kira tidak.

FUZxxl

Sepertinya tidak mungkin akan ada bahasa pemrograman seperti itu, saya kira Anda bisa mencoba untuk menegakkannya, tetapi kemudian Anda tidak akan dapat melakukan hal-hal sederhana seperti menyortir, setidaknya tidak tanpa itu menjadi sangat rumit dan menyakitkan.

Luke Mathies

@FUZxxl Ini tidak menangkap banyak program terminasi, Bahkan fungsi f (x) = 1 tidak mungkin diekspresikan dalam bahasa ini. Saya juga merasa bahwa fungsi semacam ini ditangkap oleh pemrograman fungsional total karena setiap fungsi adalah fungsi total.

Chao Xu

@ FuZxxl, saya pikir itu tidak benar, tetapi bahasa seperti itu harus dibatasi. Misalnya, bahasa yang setara dengan automata deterministik Hingga akan dijamin akan berakhir, tetapi akan sangat terbatas dalam hal apa yang dapat dihitungnya.

jmite

@ FuZxxl, detail pernyataan seperti itu penting. Sangat mudah untuk merancang bahasa pemrograman di mana setiap program berakhir. Merupakan hal yang berbeda untuk merancang bahasa yang dapat kita ungkapkan setiap fungsi yang dapat dihitung.

Vijay D

Jawaban:

Tidak ada bahasa seperti itu.

Namun, lihatlah Boomerang . Ini adalah bahasa untuk menulis bijections antar string. Saya tidak tahu seberapa luas kelas peta bisa diekspresikan di dalamnya, tapi saya yakin Anda bisa mengetahui jika Anda mencari sedikit.

$\mathbb{N} \to \mathbb{N}$

$f_0, f_1, f_2, \ldots$

$g : \mathbb{N} \to \mathbb{N}$ $g(2 k)$ $g(2 k + 1)$ $f_k(2 k)$

$f_k(2 k) = 2 k$ $g(2 k) = 2 k + 1$ $g(2 k + 1) = 2 k$
$f_k(2 k) \neq 2 k$ $g(2 k) = 2 k$ $g(2 k + 1) = 2 k + 1$

$k \in \mathbb{N}$ $g$ $f_k$ $g(2 k) \neq f_k(2 k)$ $g$

Andrej Bauer
sumber

2 k

$2k$

2 k + 1

$2k+1$

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

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

f_{k} (k) + 1

$f_k(k)+1$

g

$g$

Pernyataan awal salah, ada banyak bahasa dalam literatur.

Nathaniel

Di sisi lain bukti Anda tampaknya sah. Mungkin saya bingung. Saya perlu membaca makalah Axelsen dan Glück (lihat jawaban saya) dengan cermat untuk mencari tahu apa yang terjadi di sini.

Nathaniel