IIm18-Kreativaufgabe9

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Kernaussagen der Vorlesung 2 μ-Funktion durchdenken mit imaginären Werten 3 Implementierung der Kreativaufgabe (Java) 🐇 4 Implementierung der Kreativaufgabe (JavaScript) 4.1 A*-Klasse 4.2 Number Converter 4.3 µ-rekursive Funktion

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

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)

ausführen

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

ausführen

getWord(16);

ausführen

getGoedelnumber("aba");

ausführen

getWordAtIndex(8)

ausführen

generateGoedelOrderedWords(10)

ausführen