Aus ProgrammingWiki

Inhaltsverzeichnis 1 Entscheidbarkeit und Aufzählbarkeit 1.1 Aufgabe 1 1.2 Aufgabe 2 1.3 Aufgabe 3 1.4 Aufgabe 4 1.5 Aufgabe 5 1.6 Aufgabe 6 1.7 Aufgabe 7 1.8 Aufgabe 8 1.9 Aufgabe 9 1.10 Aufgabe 10 1.11 Aufgabe 11 1.12 Aufgabe 12

Entscheidbarkeit und Aufzählbarkeit

Aufgabe 1

Zeigen Sie, dass die beiden Mengen aus den Beispielen entscheidbar sind. Schreiben Sie je eine entsprechende Prozedur für die jeweilige charakteristische Funktion (ProgrammingWiki).

Beispiel 1: endliche Menge

geg.: Menge M aller Wörter aus und

z.z.: M entscheidbar

Lösung:

Die Menge M ist somit entscheidbar.

(define menge1 (lambda (w) (let ((l (string->list w))) (letrec ((helper (lambda (a) (cond [(or (char=? #\a (car a)) (char=? #\b (car a))) (cond [(not (null? (cdr a))) (helper (cdr a))] [else #t])] [else #f]) ) ) ) (cond [(= (string-length w) 3) (helper l)] [else #f] ) ) ) ) )

(menge1 "aba")

ausführen

Beispiel 2: abzählbar unendliche Menge

geg.: Menge M aller Wörter aus und

z.z.: M entscheidbar

Lösung:

Die Menge M ist entscheidbar.

(define menge2 (lambda (w) (let ((l (string->list w))) (letrec ((helper (lambda (a) (cond [(or (char=? #\a (car a)) (char=? #\b (car a))) (cond [(not (null? (cdr a))) (helper (cdr a))] [else #t])] [else #f]))))(cond [(and (not (null? l)) (char=? #\a (car l))) (cond [ (null? (cdr l)) #t] [else (helper (cdr l))] )] [else #f] ) ) ) ) )

(menge2 "abba")

ausführen

Aufgabe 2

Wie viele berechenbare charakteristische Funktionen gibt es?

Hinweis: Potenzmenge unendlicher Mengen

ist eine abzählbar unendliche Menge, d.h. alle sind abzählbar Mengen, entweder endlich oder unendlich.

Die Potenzmenge von ist eine überabzählbar unendliche Menge, wodurch es überabzählbar unendlich viele Mengen gibt.

kann die Werte annehmen.

Die überabzählbare Menge bildet den Definitionsbereich der Funktionen .

Das heißt es gibt überabzählbar viele charakteristische Funktionen , für jede Teilmenge von .

Da es jedoch nur abzählbar unendlich viele Algorithmen gibt, verbleiben überabzählbar unendlich viele -Funktionen, die nicht berechnet werden können. Nur abzählbar unendlich viele charakteristische Funktionen sind somit berechenbar.

Aufgabe 3

Zeigen Sie, dass die Menge der geraden Zahlen G eine aufzählbare Menge ist.

geg.: die Menge der geraden Zahlen und

z.z.: abzählbar, berechenbar

Lösung:

Abzählbarkeit:

Die Menge der geraden Zahlen ist eine Teilmenge der ganzen Zahlen . Wie hier bewiesen, sind die ganzen Zahlen abzählbar unendlich. Die Menge der geraden Zahlen ist somit ebenfalls abzählbar unendlich.

Berechenbarkeit: Mit der Aufzählfunktion

, mit

wird gezeigt, dass ein Algorithmus für dieses Problem existiert, der als Computerprogramm realisiert werden kann.

Aufgabe 4

Zeigen Sie, dass die Menge der Primzahlen P aufzählbar ist.

geg.: Menge P

z.z.: P abzählbar und berechenbar

Lösung:

Wie hier bereits betrachtet, ist die Menge der Primzahlen P eine abzählbar unendliche Menge.

Mit folgernder Funktion kann gezeigt werden, dass die Menge der Primzahlen berechenbar ist.

mit

Die Überprüfung, ob eine Zahl eine Primzahl ist, kann mit mit einer Prozedur ermittelt werden.

Aufgabe 5

Wir wissen, dass $A^*$ eine abzählbar unendliche Menge ist. Zeigen Sie, dass $A^*$ auch aufzählbar ist.

Hinweis: Hierzu ist es notwendig ein Aufbauschema für $A^*$ zu entwerfen und anschließend eine Prozedur dafür zu implementieren.

Das Aufbauschmema sieht vor für jede mögliche Wortlänge alle möglichen Wörter mit den Alphabetzeichen zu bilden. Da die abzählbarkeit schon gegeben ist, muss nur noch noch die berechenbarkeit bewiesen werden. Dazu gibt es einen Algorithmus, der für jede natürliche Zahl, das Wort von A* zurückgibt.

Beispielcode in Java:

int n=10; String[] Alphabet={"a","b","c"};

public int[] gibExponent_Summe(int n, int alphabetlaenge) { int sum=1; int i=0; int ergebnis_pot; int[] Summe_index=new int[2]; while(sum<n) { i++; ergebnis_pot=1; for (int j=1;j<=i;j++) { ergebnis_pot*=alphabetlaenge; } sum=sum+ergebnis_pot; } Summe_index[0]=i; Summe_index[1]=sum; return Summe_index; }

private String getElement(String[][] array, int index) { int zaehler=1; String wort=""; int b=0; for(int i=0;i<array.length;i++) { while(array[i][b]!=null) { zaehler++; if(index==zaehler) { wort=array[i][b]; return wort; } b++; } } return "";

public String a_stern_test() { int laenge_alph = Alphabet.length; int sum=0; if (n==0) { return "nicht definiert"; } int[] Struktur=gibExponent_Summe(n,laenge_alph); int anzWoerter=Struktur[1]; String[][] Woerter = new String[anzWoerter][anzWoerter]; int exponent=Struktur[0]; int i=0; while(i<exponent) { if (i==0) { for(int z=0; z<laenge_alph;z++) { Woerter[i][z]=Alphabet[z]; } } else { int p=0; int h=0; while(Woerter[i-1][p]!=null) { for(int j=0; j<laenge_alph;j++) { Woerter[i][h]=Woerter[i-1][p]+Alphabet[j]; h++; } p++; } } i++; } return(getElement(Woerter,n)); }

a_stern_test();

ausführen

Aufgabe 6

Zeigen Sie, dass jede endliche Menge $M$ aufzählbar ist.

geg.: $M$ endlich

z.z.: $M$ aufzählbar

Lösung:

Abzählbarkeit:

Jede endliche Menge ist per Definition auch abzählbar.

Berechenbarkeit:

Es gibt für jede endliche Menge $M$ eine surjektive, total berechenbare Funktion .

Aufgabe 7

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

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

f ist die Umkehrfunktion der Cantorschen Paarungsfunktion in Teilaufgabe 3.

$$f(n):\begin{cases} y = n-t \\ x =w-y \\ \end{cases} $$

mit $$w(n)= \dfrac{\sqrt{8*n+1}-1}{2} $$

und mit $$t= \dfrac{w(w-1)}{2} $$

2.Definieren Sie eine Ordnungsrelation $p<$ in G

Mittels der in Teilaufgabe 1 gezeigten Funktion können nun jeder natürlichen Zahl ein Koordinatenpaar zugeordnet werden. Diese Zuordnung findet sich in der nachfolgenden Tabelle.

Position	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
Gitterpunkt (x,y)	(0,0)	(0,1)	(1,0)	(0,2)	(1,1)	(2,0)	(0,3)	(1,2)	(2,1)	(3,0)	(0,4)	(1,3)	(2,2)	(3,1)	(4,0)	(0,5)

Daraus kann man nun eine Ordnungsrelation festlegen mit aufsteigenden x- und y-Koordinaten:

$(G, p_<)$ = {(0,0) < (0,1) < (1,0) < (0,2) < (1,1) < (2,0) < (0,3) < (1,2) < (2,1) < ...}

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

Eine Funktion k zur Berechnung der Platznummer ist die Cantorsche Paarungsfunktion, die folgendermaßen definiert ist:

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

Aufgabe 8

Das Halteproblem ist semi-entscheidbar. Beweisen Sie diese Aussage.

Satz: Ob die Ausführung eines Algorithmus zu einem Ende gelangt, ist semi-entscheidbar.

geg.: Menge aller Algorithen

z.z. dass terminiert ist semi-entscheidbar

Lösung:

Somit ist das Problem nur für den Fall, dass der Algorithmus terminiert, entscheidbar.

Aufgabe 9

Geben Sie für die Menge $FIBS$ der Fibonacci-Zahlwörter eine Aufzählfunktion an und begründen Sie deren Berechenbarkeit. Weisen Sie nach, dass $FIBS$ eine semi-entscheidbare Menge ist. Zeigen Sie dass $FIBS$ sogar entscheidbar ist.

geg: Fibbonacci-Funktion $$fib(n)=\begin{cases} 0 & \text{, wenn n=0}\\ 1 & \text{, wenn n=1}\\ fib(n-1)+fib(n-2)& \text{, sonst} \\ \end{cases} $$

z.z. Aufzählprozedur f, semi-Entscheidbarkeit, Entscheidbarkeit

Lösung:

Da es schon eine Bildungsvorschrift für die FIBS-Zahlen gibt, kann man dies als Grundlage für eine surjektive Aufzählprozedur f nehmen:

$$f(n)=fib(n) $$

Für die Entscheidbarkeit muss gezeigt werden, dass es eine total berechenbare charakteristische Funktion chi gibt. Diese kann hier etwa so angegeben werden: $$\chi_{M_{FIBS}}(w) = \begin{cases} wahr, & \text{wenn } w = (String) fib(i), i \in \mathbb{N} \\ falsch, & sonst. \end{cases}$$

Aufgabe 10

Übertragen Sie die vorhergehende Übungsaufgabe sinngemäß auf die Menge der Quadratzahlen $QZ = \{n^2 | n\in\N\}$.

Lösung:

Eine Aufzählfunktion kann folgendermaßen angegeben werden:

Für die Entscheidbarkeit kann eine charakteristische Funktion angeben werden, die total berechenbar ist:

Aufgabe 11

Weisen Sie nach, dass die Menge $M$ aller "Wörter" aus $\{a,b\}^*$, die mit a beginnen, semi-entscheidbar ist.

In Aufgabe 2 wurde die Entscheidbarkeit der Menge $M$ nachgewiesen. Wenn eine Menge entscheidbar ist, ist diese folglich auch semientscheidbar.

Aufgabe 12

Definieren Sie die Menge der geraden Zahlen (Zahlwörter) und die der ungeraden Zahlen (Zahlwörter) und veranlassen Sie das ProgrammingWiki 30 Elemente der Vereinigungsmenge auszugeben.