IIm18-Kreativaufgabe9

Aus ProgrammingWiki

< BuK < IIm18

Archivierte Version vom 2019-06-16T22:36:38+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Kernaussagen der Vorlesung
2 μ-Funktion durchdenken mit imaginären Werten
3 Implementierung der Kreativaufgabe (Java) 🐇
4 Implementierung der Kreativaufgabe (JavaScript)

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

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

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;</character>

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

   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&lt;&gt;();
       int dividend = goedelNumber;
       do {
           int rest = dividend % 3;
           if (rest == 0 || rest &gt; alphabet.getCharacters().size()) {
               throw new NotAGoedelNumberException(String.format("%d is not a number for a valid character in alphabet", rest));
           }</integer>

           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&lt;&gt;();</integer>

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

}

Implementierung der Kreativaufgabe (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;
    }
}

Number Converter

function convertNumber(number, fromBase, toBase) {
    const length = number.toString().length;
    let decimalNumber = 0;
    let result = "";

    for (let i = 0; i < length; i++) {
        let digit = number.toString()[length - i - 1];
        if (digit >= fromBase) return "Error";
        decimalNumber += digit * Math.pow(fromBase, i);
    }

    while (decimalNumber > 0) {
        result = (decimalNumber % toBase) + result;
        decimalNumber = Math.floor(decimalNumber / toBase);
    }

    return +result;
}

convertNumber(121, 3, 10)

µ-rekursive Funktion

S = {a, b}
Verschlüsselung im 3er-System mit a -> 1 und b -> 2

var aStern = new ASternClass("a,b");
const gMap = {};

// ==========
 

function isWordValid(word) {
    for (let i = 0; i < word.length; i++) {
        if (!aStern.alphabet.includes(word[i])) return false;
    }

    return true;
}

function getGoedelnumber(word) {
    if (!isWordValid(word)) return -1;
    let number = 0;
    for (let i = 0; i < word.length; i++) {
        if (word.charCodeAt(i) - 96 < 0 || word.charCodeAt(i) - 96 > 2) return -1;
        number += (word.charCodeAt(i) - 96) * Math.pow(10, word.length - i - 1);
    }

    return convertNumber(number, 3, 10);
}

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 getWordAtIndex(index) {
    const goedelNumber = muef(index);
    return getWord(goedelNumber);
}

function isGoedelnumber(number) {
    let convertedNumber = convertNumber(number, 10, 3);
    return /^[1-2]+$/.test(convertedNumber);
}

function p(r, y) {
    return r <= y && isGoedelnumber(y) ? 1 : 0;
}

function muef(i) {
    if (gMap.hasOwnProperty(i))
        return gMap[i];

    if (i < 1) {
        let n = 0;
        while (1 - p(0, n) !== 0) {
            n++;
        }
        gMap[0] = n;
        return n;
    } else {
        let n = 0;
        while (1 - p(muef(i - 1) + 1, n) !== 0) {
            n++;
        }
        gMap[i] = n;
        return n;
    }
}

function generateGoedelOrderedWords(amount) {
    const words = [];
    for (let i = 0; i < amount; i++) {
        let word = getWordAtIndex(i);
        let goedelNumber = getGoedelnumber(word);

        words.push("{" + goedelNumber + ":" + word + "}");
    }
    return words;
}

isGoedelnumber(16);

getWord(16);

getGoedelnumber("aba");

getWordAtIndex(8)

generateGoedelOrderedWords(10)

IIm18-Kreativaufgabe9

Inhaltsverzeichnis

Kernaussagen der Vorlesung

μ-Funktion durchdenken mit imaginären Werten

Implementierung der Kreativaufgabe (Java) 🐇

Implementierung der Kreativaufgabe (JavaScript)

A*-Klasse

Number Converter

µ-rekursive Funktion

Suche