BuK/IIm18/Vorlesung7
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Javascript</language>
== Eigenschaften der Gödelisierung ==
z.z.: Aus (1), (2) und (3) folgt (4)
(1): Jedem Element aus natürlichen Zahlen wird höchstens ein Element aus A* zugeordnet
(2) G(A*) ist berechenbar -> Es lässt sich eine Prozedur angeben, die G(w) in endlich vielen Schritten berechnet
(3) G(A*) ist entscheidbar -> Es lässt sich für jedes n von N in endlich vielen Schritten feststellen, ob n eine Gödelnummer ist
(4) es existiert eine berechenbare Umkehrfunktion zu allen Elementen in G(A*), um von G(A*) zu A* zu kommen
'''Herleitung von (4)'''
* Menge der natürlichen Zahlen ist aufzählbar -> 0,1,2,3….
** diese lasse ich mir generieren
* zu jedem n kann durch (3) festgestellt werden, ob n Gödelnummer ist
** Wenn ja, muss nun das Wort aus A* für das jeweilige n bestimmt werden
* A* ist ebenfalls aufzählbar -> längenlexigografische Ordnung aller Wörter möglich
** Wir bauen uns eine Generatorfunktion g für alle Wörter aus A*
** Lassen uns potentiell alle Wörter generieren
** Berechnen für jedes Wort durch (2) die Gödelnummer
** Das wird so lange gemacht, bis berechnete Gödelnummer mit unserem n übereinstimmt
** Dann haben wir für dieses n das Wort aus A* gefunden (Lösung erreicht)
* Durch (1) wird sichergestellt, dass für dieses n genau ein Wort aus A* existiert
== Gödelisierung und Umkehrung mittels Primfaktorzerlegung (Java) ==
Hinweis: Zur Berechnung der Primzahlen wurde folgende Maven-Dependency verwendet:
<code id="5d06c9a0486c7">
/*<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-math3</artifactId>
<version>3.6.1</version>
</dependency>*/
</code>
<code id="5d06c9a048769">
/*public class Application {
public static void main(String[] args) {
Alphabet alphabet = new Alphabet('a','b','c');
GoedelisierungPrim goedelisierungPrim = new GoedelisierungPrim(alphabet);
AStern aStern = new AStern(alphabet);
aStern.stream()
.limit(100)
.peek(s -> System.out.print(s + " ")) // Ausgabe Wort aus A*
.map(goedelisierungPrim::getGoedelNumberFromWord)
.peek(i -> System.out.print(i + " ")) // Ausgabe der Gödelnummer
.map(goedelisierungPrim::getWordFromGoedelNumber)
.forEach(System.out::println); // Ausgabe Wort aus A* nach Anwendung der Umkehrfunktion
}
}
public class Alphabet {
private final List<Character> characters;
public Alphabet(Character... characters) {
this.characters = new ArrayList<>(new TreeSet<>(Arrays.asList(characters)));
}
public int getG0ForCharacter(char character) {
if (!characters.contains(character)) {
throw new IllegalArgumentException(
String.format("alphabet %s doesn't contain character '%s'", characters, character)
);
}
return characters.indexOf(character) + 1;
}
public List<Character> getCharacters() {
return characters;
}
public char getCharacterOfG0(int g0){
return characters.get(g0-1);
}
}
public class GoedelisierungPrim {
private final Alphabet alphabet;
public GoedelisierungPrim(Alphabet alphabet) {
this.alphabet = alphabet;
}
public int getGoedelNumberFromWord(String wordFromAStern) {
List<Integer> primeNumbers = PrimeGenerator.generateNPrimeNumbers(wordFromAStern.length());
return IntStream.range(0, wordFromAStern.length())
.map((characterIndex) -> getGoedelFactor(
alphabet.getG0ForCharacter(wordFromAStern.charAt(characterIndex)),
primeNumbers.get(characterIndex))
)
.reduce((left, right) -> left * right)
.orElseThrow(() -> new IllegalArgumentException("could not determine goedel number for word " + wordFromAStern));
}
public String getWordFromGoedelNumber(int goedelNumber) {
List<Integer> primfactors = Primes.primeFactors(goedelNumber);
Map<Integer, Long> countedPrims = countPrimFactors(primfactors);
return getWordOfCountedPrims(countedPrims);
}
private String getWordOfCountedPrims(Map<Integer, Long> countedPrims) {
StringBuilder stringBuilder = new StringBuilder();
for (Long primIndex : countedPrims.values()) {
stringBuilder.append(alphabet.getCharacterOfG0(Math.toIntExact(primIndex)));
}
return stringBuilder.toString();
}
private Map<Integer, Long> countPrimFactors(List<Integer> primfactors) {
return primfactors.stream()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}
private int getGoedelFactor(int g0, int primNumber) {
return (int) Math.pow(primNumber,g0);
}
}
public class AStern {
private Alphabet alphabet;
private List<String> prefixe = new ArrayList<>();
private List<String> words = new ArrayList<>();
private int prefixIndex = 0;
private int alphabetIndex = 0;
AStern(Alphabet alphabet) {
this.alphabet = alphabet;
}
public Stream<String> stream(){
return Stream.generate(this::next);
}
private String next() {
if (prefixe.isEmpty()) {
prefixe.add("");
return next();
}
if (alphabetIndex == alphabet.getCharacters().size()) {
alphabetIndex = 0;
prefixIndex++;
}
String prefix = prefixe.get(prefixIndex);
Character alphabetSign = alphabet.getCharacters().get(alphabetIndex);
String word = prefix + alphabetSign;
prefixe.add(word);
words.add(word);
alphabetIndex++;
return word;
}
}
public class PrimeGenerator {
private int lastNumber = 0;
public static List<Integer> generateNPrimeNumbers(int n) {
PrimeGenerator primeGenerator = new PrimeGenerator();
return Stream.generate(primeGenerator::getNext)
.limit(n)
.collect(Collectors.toList());
}
private int getNext() {
lastNumber = Primes.nextPrime(lastNumber + 1);
return lastNumber;
}
}*/
</code>
<language>Javascript</language>
== Gödelisierung und Umkehrung mittels Primfaktorzerlegung (JavaScript) ==
=== A*-Klasse ===
<code id="5d06cb9a103c3">
class ASternClass {
constructor(alphabet, startsWith) {
this.alphabet = Array.isArray(alphabet) ? alphabet : alphabet.split(",");
this.startsWith = startsWith || "";
this.wordCache = [];
}
getWord(index) {
let set = this.wordCache;
if (index >= this.wordCache.length) {
const length = Math.ceil(Math.log((index / 2) + 1) / Math.log(2)) + this.startsWith.length;
set = this.getWordsUpToLength(length);
}
return set[index];
}
getIndex(word) {
if (!this.isWordInAStern(word))
return -1;
const set = this.getWordsUpToLength(word.length);
return set.indexOf(word);
}
getWordsUpToLength(length) {
let set = [];
Object.assign(set, this.wordCache);
const wordCacheCurrentWordLength = this.wordCache.length ? this.wordCache[this.wordCache.length - 1].length : -1;
if (wordCacheCurrentWordLength >= length) {
const maxIndex = Math.ceil(Math.pow(2, length - this.startsWith.length + 1));
return set.splice(0, maxIndex);
} else {
for (let i = wordCacheCurrentWordLength + 1; i <= length; i++) {
set = set.concat(
this.getWordsWithLength(i)
);
}
Object.assign(this.wordCache, set);
return set;
}
}
getWordsWithLength(length) {
const set = length <= 0 ? ["\u03B5"] : [];
const helper = (prefix) => {
for (let i = 0; i < this.alphabet.length; i++) {
const word = prefix + this.alphabet[i];
if (word.length > length)
break;
if (word.length === length && word.startsWith(this.startsWith))
set.push(word);
helper(word);
}
};
helper("");
return set;
}
isWordInAStern(word) {
if (!word || !word.startsWith(this.startsWith)) return false;
for (let i = 1; i < word.length; i++) {
if (!this.alphabet.includes(word[i])) return false;
}
return true;
}
}
</code>
<run id="5d06cb9a10442">const as = new ASternClass("a,b", "ab")</run>
<run id="5d06cb9a104ad">as.getWord(3)</run>
<run id="5d06cb9a10508">as.getWordsUpToLength(4)</run>
<language>Javascript</language>
=== Prime Number Service ===
<code>
const primeNumberCache = [];
// ==========
function getPrimeAt(index) {
if (primeNumberCache.length <= index) {
generatePrimesUpTo(index);
}
return primeNumberCache[index];
}
function getIndexOfPrime(prime) {
while(primeNumberCache[primeNumberCache.length -1] < prime) {
generatePrimesUpTo(primeNumberCache.length);
}
return primeNumberCache.indexOf(prime);
}
function generatePrimesUpTo(index) {
let currentNumber = primeNumberCache[primeNumberCache.length-1] || 0;
while(primeNumberCache.length <= index) {
isPrime(++currentNumber) ? primeNumberCache.push(currentNumber) : null;
}
}
function isPrime(num) {
for (let i = 2, sqrt = Math.sqrt(num); i <= sqrt; i++)
if (num % i === 0) return false;
return num > 1;
}
</code>
<run >getPrimeAt(10)</run>
<run>getIndexOfPrime(31)</run>
<run>isPrime(31)</run>
=== Funktionen zur Gödelisierung ===
<code id="5d06cbb0b8114">
let aStern = new ASternClass("a,b");
// ==========
function isWordValid(word) {
for (let i = 0; i < word.length; i++) {
if (!aStern.alphabet.includes(word[i])) return false;
}
return true;
}
function isGoedelnumber(number) {
const primeFactors = primeDecoding(number);
let primeIndex = 0;
let numberOfSamePrime = 0;
let isValid = false;
for (let i = 0; i < primeFactors.length; i++) {
if (primeFactors[i] === getPrimeAt(primeIndex)) {
if (++numberOfSamePrime > aStern.alphabet.length) return false;
isValid = true;
} else {
if (!isValid) return false;
isValid = primeFactors[i] === getPrimeAt(++primeIndex);
numberOfSamePrime = 0;
}
}
return primeFactors[primeFactors.length - 1] === getPrimeAt(primeIndex);
}
function getGoedelnumber(word) {
if (!isWordValid(word)) return -1;
let goedelNumber = 1;
for (let i = 0; i < word.length; i++) {
goedelNumber *= primeEncoding(i, word[i]);
}
return goedelNumber;
}
function getWord(goedelnumber) {
goedelnumber = parseInt(goedelnumber);
let index = 1;
let word = aStern.getWord(index);
if (!isGoedelnumber(goedelnumber)) return "\u03B5";
while (getGoedelnumber(word) !== goedelnumber) {
word = aStern.getWord(++index);
}
return word;
}
function primeEncoding(index, char) {
return Math.pow(getPrimeAt(index), aStern.alphabet.indexOf(char) + 1);
}
function primeDecoding(num) {
const primeFactors = [];
let index = 0;
while (index >= 0 && num) {
let prime = getPrimeAt(index);
if (num % prime === 0) {
num /= prime;
primeFactors.push(prime);
} else if (prime > num) {
index = -1;
} else {
index++;
}
}
return primeFactors;
}
</code>
<run id="5d06c9a048b51">isGoedelnumber(90);</run>
<run id="5d06c9a048bc8">getWord(90);</run>
<run id="5d06c9a048c3b">getGoedelnumber("aba");</run>