BuK/IIm18/IIm18-Kreativaufgabe9

Wiki-Quelltext dieser Seite.

== Kernaussagen der Vorlesung ==

* nicht alle total berechenbare Funktionen sind primitv-rekursiv (AP-Funktion)
* man kann keine nicht totale Funktion als primitiv-rekursive Funktion darstellen
* man kann mit dem unbeschränkten μ-Operator μ-rekursive (d.h. partiell-rekursive) Funktionen darstellen. Diese sind so aufgebaut, dass es zu einem Endloszyklus kommen kann, wenn die geforderte Bedingung niemals erfüllt werden kann
* Die Menge der Turing-berechenbaren Funktionen und die Menge der μ-rekursiven Funktionen (partiell berechenbare Funktionen) sind identisch 
* μ-rekursive Funktionen können mit while-Programmen implementiert werden


<language>Java</language>
== μ-Funktion durchdenken mit imaginären Werten ==

* μf(0) = g(1)
** 1 - p(0,0) = 1
** 1 - p(0,1) = 1
** 1 - p(0,2) = 1
** 1 - p(0,3) = 1
** 1 - p(0,4) = 1
** 1 - p(0,5) = 0 -> 5 ist 0. goedelnummer
* μf(1) = g(2)
** 1 - p(g(1)+1, 0) = 1 - p(6,0) = 1
** 1 - p(g(1)+1, 1) = 1 - p(6,1) = 1
** 1 - p(g(1)+1, 2) = 1 - p(6,2) = 1
** 1 - p(g(1)+1, 3) = 1 - p(6,3) = 1
** 1 - p(g(1)+1, 4) = 1 - p(6,4) = 1
** 1 - p(g(1)+1, 5) = 1 - p(6,5) = 1
** 1 - p(g(1)+1, 6) = 1 - p(6,6) = 1
** ...
** 1 - p(g(1)+1, 35) = 1 - p(6,35) = 0 -> 35 ist 1. Gödelnummer
* μf(2) = g(3)
** 1 - p(g(2)+1, 0) = 1 - p(36,0) = 1
** 1 - p(g(2)+1, 1) = 1 - p(36,1) = 1
** 1 - p(g(2)+1, 2) = 1 - p(36,2) = 1
** 1 - p(g(2)+1, 3) = 1 - p(36,3) = 1
** 1 - p(g(2)+1, 4) = 1 - p(36,4) = 1
** 1 - p(g(2)+1, 5) = 1 - p(36,5) = 1
** 1 - p(g(2)+1, 6) = 1 - p(36,6) = 1
** ...
** 1 - p(g(2)+1, 120) = 1 - p(36,120) = 0 -> 120 ist 2. Gödelnummer

== Implementierung der Kreativaufgabe (Java) 🐇==

* Das folgende Programm implementiert die Funktion k. Mit dieser kann das Wort aus dem Alphabet S* für die n-te Gödelnummer (unterliegt Gödelordnung) berechnet werden
* Die Funktion k ruft intern die μ-rekursive Funktion auf, um die i-te Gödelnummer zu berechnen. Mit der Umkehrfunktion der Gödelisierung wird daraus dann das Wort berechnet

<code id="5d06746adf42d">
public class Application {

    public static void main(String[] args) {

        Alphabet alphabet = new Alphabet('a', 'b');
        Goedelisierung3erSystem goedelisierung3erSystem = new Goedelisierung3erSystem(alphabet);
        KFunction kFunction = new KFunction(goedelisierung3erSystem);

        IntStream.iterate(0, i -> i + 1)
                .limit(2000)
                .peek(goedelIndex -> System.out.print(String.format("Goedel-Index: %d \t\t", goedelIndex)))
                .mapToObj(kFunction::getWordForGoedelIndex)
                .forEach(word -> System.out.println(String.format("Word: %s", word)));
    }
}

private final List<Character> characters;

    public Alphabet(Character... characters) {
        this.characters = new ArrayList<>(new TreeSet<>(Arrays.asList(characters)));
    }

    public int getNumberForCharacter(Character character) {
        if (!characters.contains(character)) {
            throw new IllegalArgumentException(String.format("Alphabet doesn't contain character %s", character));
        }

        return characters.indexOf(character)+1;
    }

    public List<Character> getCharacters() {
        return characters;
    }

    public char getCharacterForNumber(Integer number) {
        return characters.get(number-1);
}

public class Goedelisierung3erSystem {

    private final Alphabet alphabet;

    public Goedelisierung3erSystem(Alphabet alphabet) {
        this.alphabet = alphabet;
    }

    public int getGoedelNumberFromWord(String wordFromSStern) {

        char[] chars = wordFromSStern.toCharArray();
        int goedelNumber = 0;
        for (int i = 0; i < chars.length; i++) {
            int charNumber = alphabet.getNumberForCharacter(chars[i]);
            int potenz = chars.length - i - 1;
            goedelNumber += getGoedelSummand(charNumber, potenz);
        }

        return goedelNumber;
    }

    public String getWordFromGoedelNumber(int goedelNumber) {

        Deque<Integer> factorList = new LinkedList<>();
        int dividend = goedelNumber;
        do {
            int rest = dividend % 3;
            if (rest == 0 || rest > alphabet.getCharacters().size()) {
                throw new NotAGoedelNumberException(String.format("%d is not a number for a valid character in alphabet", rest));
            }

            int quotient = dividend / 3;
            factorList.addFirst(rest);
            dividend = quotient;
        } while (dividend != 0);

        StringBuilder stringBuilder = new StringBuilder();
        for (Integer factor : factorList) {
            stringBuilder.append(alphabet.getCharacterForNumber(factor));
        }

        return stringBuilder.toString();
    }

    public boolean isNumberGoedelNumber(int number) {
        try {
            getWordFromGoedelNumber(number);
            return true;
        } catch (NotAGoedelNumberException e) {
            return false;
        }
    }

    private int getGoedelSummand(int charNumber, int potenz) {
        return (int) (charNumber * Math.pow(3, potenz));
    }
}

public class MueFunction {

    private Goedelisierung3erSystem goedelisierung3erSystem;
    private Map<Integer, Integer> gMap = new HashMap<>();

    public MueFunction(Goedelisierung3erSystem goedelisierung3erSystem) {
        this.goedelisierung3erSystem = goedelisierung3erSystem;
    }

    public int muef(int i) {

        // check if value is already in g map
        if (gMap.containsKey(i + 1)) {
            return gMap.get(i + 1);
        }

        // elementar case
        if (i == 0) {
            int n = 0;
            while (1 - p(0, n) != 0) {
                n++;
            }
            gMap.put(1, n);
            return n;
        }
        // all other cases
        else {
            int n = 0;
            while (1 - p(muef(i - 1) + 1, n) != 0) {
                n++;
            }
            gMap.put(i + 1, n);
            return n;
        }
    }

    private int p(int r, int y) {
        if (r <= y && goedelisierung3erSystem.isNumberGoedelNumber(y)) {
            return 1;
        } else {
            return 0;
        }
    }
}

public class KFunction {

    private Goedelisierung3erSystem goedelisierung3erSystem;
    private MueFunction mueFunction;

    public KFunction(Goedelisierung3erSystem goedelisierung3erSystem) {
        this.goedelisierung3erSystem = goedelisierung3erSystem;
        this.mueFunction = new MueFunction(goedelisierung3erSystem);
    }

    public String getWordForGoedelIndex(int goedelIndex){

        int goedelNumber = mueFunction.muef(goedelIndex);
        return goedelisierung3erSystem.getWordFromGoedelNumber(goedelNumber);
    }
}


</code>