Eine Programmiersprache, die nur berechenbare bijektive Funktionen implementieren kann?

Gibt es Programmiersprachen (oder Logik), die eine Funktion genau dann implementieren (oder ausdrücken) können, wenn eine berechenbare bijektive Funktion ist? $f:\mathbb{N}\to \mathbb{N}$ $f$

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

Jemand hat mir bewiesen, dass es unmöglich ist, eine Sprache zu erstellen, die nur das Beenden von Programmen akzeptiert. Da Ihre Frage ziemlich ähnlich ist, denke ich nein.

FUZxxl

Es scheint unwahrscheinlich, dass es eine solche Programmiersprache geben würde. Ich denke, Sie könnten versuchen, sie durchzusetzen, aber dann wären Sie nicht in der Lage, einfache Dinge wie Sortieren zu tun, zumindest nicht, ohne dass sie schrecklich komplex und schmerzhaft wird.

Luke Mathieson

@FUZxxl Dies erfasst nicht viele Abschlussprogramme. Tatsächlich ist es sogar unmöglich, die Funktion f (x) = 1 in dieser Sprache auszudrücken. Ich habe auch das Gefühl, dass diese Art von Funktionen durch die vollständige Funktionsprogrammierung erfasst werden, da jede Funktion eine Gesamtfunktion ist.

Chao Xu

@FUZxxl, ich denke nicht, dass das richtig ist, aber eine solche Sprache müsste begrenzt werden. Zum Beispiel würde eine Sprache, die endlichen deterministischen Automaten entspricht, garantiert enden, wäre aber in ihrer Berechnung äußerst eingeschränkt.

Jmite

@FUZxxl, die Details einer solchen Aussage sind wichtig. Es ist einfach, eine Programmiersprache zu entwerfen, in der jedes Programm endet. Es ist eine andere Sache, eine Sprache zu entwerfen, in der wir jede berechenbare Funktion ausdrücken können.

Vijay D

Antworten:

Es gibt keine solche Sprache.

Schauen Sie sich jedoch Boomerang an . Es ist eine Sprache zum Schreiben von Bijektionen zwischen Zeichenfolgen. Ich weiß nicht, wie breit eine Klasse von Karten darin ausgedrückt werden kann, aber ich bin sicher, dass Sie herausfinden können, ob Sie ein bisschen suchen.

Es ist vernünftig, von einer Programmiersprache zu verlangen, dass der Satz gültiger Programme von einem Interpreter oder einem Compiler erkannt wird, dh dass es sich um einen rechnerisch aufzählbaren Satz handelt. Angenommen, wir hatten damals eine Programmiersprache, deren Satz gültiger Programme rechnerisch aufzählbar war und die genau alle berechenbaren Bijektionen implementierte . Das würde bedeuten, dass wir alle berechenbaren Bijektionen rechnerisch aufzählen können (einfach alle gültigen Programme in dieser Programmiersprache aufzählen), aber dies ist mit dem nächsten Satz unmöglich. $\mathbb{N} \to \mathbb{N}$

Satz: Angenommen, ist eine berechenbare Folge berechenbarer Bijektionen. Dann gibt es eine berechenbare Bijektion, die nicht in der Reihenfolge ist. $f_0, f_1, f_2, \ldots$

Beweis. Wir konstruieren eine Bijektion wie folgt. Um die Werte und , betrachten wir : $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
quelle

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$

Die anfängliche Aussage ist falsch, es gibt viele solcher Sprachen in der Literatur.

Nathaniel

Auf der anderen Seite scheint Ihr Beweis legitim. Vielleicht bin ich irgendwie verwirrt. Ich muss Axelsens und Glücks Artikel (siehe meine Antwort) sorgfältig lesen, um herauszufinden, was hier los ist.

Nathaniel