Berechenbarkeitstheorie/Entscheidbarkeit und Aufzählbarkeit/Gitterpunkte

Wiki-Quelltext dieser Seite.

<language>Javascript</language>
== Aufzählbarkeit der Menge der Gitterpunkte ==

Die Menge $G$ der Gitterpunkte (0,0),(0,1), ... einer x-y-Ebene ist ''aufzählbar''.

1. Geben Sie eine Funktion $f$ an, die $\NN$ bijektiv auf $G$ abbildet.

'''Cantorsche Paarungsfunktion''', s. auch [https://de.wikipedia.org/wiki/Cantorsche_Paarungsfunktion Wikipedia]

<code id="576a564d03150">
var f = function (z) {
    var w = Math.floor((Math.sqrt(8*z+1)-1)/2);
    var t = w*(w+1)/2;
    var y = z-t;
    var x = w-y;
    return [x,y];
};
</code>

Da $f$ eine bijektive und total berechenbare Funktion ist, kann man die Menge $G$ aufzählen:

<run id="576a564d031ba">
for (z=0; z<10; z++) {
    console.log("(" + f(z) + ")");
};
</run>

2. Geben Sie eine Funktion $k$ zur Berechnung der Platznummer $k(x,y)$ des betrachteten Gitterpunktes $(x,y)$ an.

<code id="576a590266188">
var k = function (x, y) {
    return (x+y)*(x+y+1)/2+y;
};
</code>
<run id="576a5902662d1">
console.log("Platznummer von (1,2): " + k(1,2));
console.log("Platznummer von (2,0): " + k(2,0));
</run>

3. Definieren Sie eine Ordnungsrelation $p_<$ in $G$.

Die folgende Prozedur gibt eine ganze Zahl zurück, die man gemäß Vorzeichen als <nowiki>true</nowiki> bzw. <nowiki>false</nowiki> deutet.

<code id="576a5902661f8">
var p_kleiner = function (a,b) {
    return k(b[0],b[1])-k(a[0],a[1]);
};
</code>
<run id="576a590266333">
console.log(p_kleiner([1,2],[2,0]));
</run>

Für das folgende Beispiel einer endlichen Gitterpunktmenge

<code id="576a59026625e">
var gps = [[ 0, 0 ],[ 2, 0 ],[ 3, 0 ],[ 1, 0 ],[ 0, 3 ],[2, 1],[ 0, 2 ],[ 1, 1 ],[ 1, 2 ],[ 0, 1 ]];
</code>

kann eine aufsteigende Sortierung mit $p_<$ vorgenommen werden:

<run id="576a590266391">
gps.sort(p_kleiner);
gps.reverse();
for (i=0; i<gps.length; i++ ) {
    console.log("(" + gps[i] +")");
};
</run>

4. Geben Sie eine Aufzählprozedur für $G$ an und begründen Sie deren Berechenbarkeit.

$f$ erfüllt die geforderten Eigenschaften und kann als Prozedur (s.o.) implementiert werden.