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), ... eine 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. Definieren Sie eine Ordnungsrelation $p_<$ in $G$.