Brainstorming VL03 Luepke

Aus ProgrammingWiki

Entscheidbarkeit und Aufzählbarkeit

ÜA zu Beispiel 1 und 2

$A^* = \{a, b\}^*$ und $M \subset A^* = \{ w \space | \space w \in A^* \space\text{und}\space |w| = 3 \}$.
$M = \{aaa,aba,aab,baa,bab,abb,bba,bbb\}$

A = ['a', 'b'] M = ['aaa','aba','aab','baa','bab','abb','bba','bbb'] def inM(w): return w in M

print(inM('not')) print(inM('a')) print(inM('aba'))

ausführen

$A^* = \{a, b\}^*$ und $M \subset A^* = \{ w = aw' \space | \space w' \in A^* \}$.

Um solche Mengen in einem Programm verfügbar zu machen, kann man das Cantorsche Diagonalisierungsverfahren 1. Art zuhilfe nehmen. Dadurch bekommt man ein Gefühl dafür, wie Wörter durch eine Prozedur sinnvoll aufgezählt werden können.

import itertools from itertools import permutations def generate(f, x): return itertools.accumulate(itertools.repeat(x), lambda v,_:f(v)) def isWord(word): if (word[0] != 'a'): print('False') return if (word == 'a'): print('True') return for index, i in enumerate(generate(lambda x: 1+x, 0)): for aIndex, aPart in enumerate(generate(lambda x: x[0]+x, 'a')): for bIndex, bPart in enumerate(generate(lambda x: x[0]+x, 'b')): perms = ['a'+''.join(p) for p in permutations(aPart+bPart)] perms.append('a'+aPart) perms.append('a'+bPart) if checkWord in perms: print('True') return if (bIndex >= i): break if (aIndex >= i): break

Hier reichen ein oder zwei zusätzliche Zeichen und das Programm kann nur durch manuellen Abbruch oder Absturz der Laufzeitumgebung beendet werden. Ob das Wort valide ist, weiß man auch nach Absturz nicht.

isWord('abbbabaa')

ausführen

Primzahlen

Eine Primzahl ist eine natürliche Zahl, die größer als 1 und ausschließlich durch sich selbst und durch 1 teilbar ist (Wikipedia, 16.04.2020). Da für jede Primzahl $P$ gilt: $P \in \mathbb{N}$, kann eine Prozedur den gedachten Zahlenstrahl der natürlichen Zahlen entlang schreiten und für jede natürliche Zahl eine Aussage treffen. Um eine Aussage für eine Zahl $n \in \mathbb{N}$ zu treffen, muss für jede Zahl $k$ aus dem Intervall $M \in \mathbb{N} \space \text{mit} \space 1 < k < n$ geprüft werden, ob $k \mid P$ also $k$ modulo $P$ = 0. Auch diese endliche Menge natürlicher Zahlen ist aufzählbar. Falls es für ein $n$ kein $k$ modulo $P$ = 0 gibt, dann ist der Rückgabewert True, andernfalls False. Diese Entscheidung kann nacheinander für jede natürliche Zahl getroffen werden. Die Menge der Primzahlen ist eine aufzählbare Menge.