BuK/IIm18/Vorlesung7

Wiki-Quelltext dieser Seite.

== 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

<language>Java</language>
<language>Java</language>
== Java-Programm zur Gödelisierung sowie zur Umkehrung mittels Primfaktorzerlegung ==

Hinweis: Zur Berechnung der Primzahlen wurde folgende Maven-Dependency verwendet:
<code>
 <dependency>
   <groupId>org.apache.commons</groupId>
   <artifactId>commons-math3</artifactId>
   <version>3.6.1</version>
 </dependency>
</code>

<code id="5cd88234a4415">
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
    }
}
</code>

<code id="5cd8829b773c6">
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);
    }
}
</code>

<code id="5cd8829b7743f">
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);
    }
}
</code>

<code id="5cd8829b774ac">
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;
    }
}
</code>

<code id="5cd8829b77515">
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>