Vorlesung7

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Eigenschaften der Gödelisierung 2 Gödelisierung und Umkehrung mittels Primfaktorzerlegung (Java) 3 Gödelisierung und Umkehrung mittels Primfaktorzerlegung (JavaScript) 3.1 A*-Klasse 3.2 Prime Number Service 3.3 Funktionen zur Gödelisierung

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:

/*<dependency> <groupId>org.apache.commons</groupId> <artifactId>commons-math3</artifactId> <version>3.6.1</version> </dependency>*/

/*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; } }*/

Gödelisierung und Umkehrung mittels Primfaktorzerlegung (JavaScript)

A*-Klasse

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; } }

const as = new ASternClass("a,b", "ab")

ausführen

as.getWord(3)

ausführen

as.getWordsUpToLength(4)

ausführen

Prime Number Service

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; }

getPrimeAt(10)

ausführen

getIndexOfPrime(31)

ausführen

isPrime(31)

ausführen

Funktionen zur Gödelisierung

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; }

isGoedelnumber(90);

ausführen

getWord(90);

ausführen

getGoedelnumber("aba");

ausführen