BuK/IIm18/IIm18-Kreativaufgabe9
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Javascript</language>
== 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
<language>Javascript</language>
<language>Java</language>
<language>Java</language>
<language>Java</language>
== 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="5d06c4c08fbf6">
//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>
== Implementierung der Kreativaufgabe (JavaScript) ==
<language>Javascript</language>
=== A*-Klasse ===
<code id="5d06c1bc78a87">
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;
}
}
</code>
=== Number Converter ===
<code id="5d06bed2418f4">
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;
}
</code>
<run id="5d06bed241961">convertNumber(121, 3, 10)</run>
=== µ-rekursive Funktion ===
* S = {a, b}
* Verschlüsselung im 3er-System mit a -> 1 und b -> 2
<code>
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;
}
</code>
<run>isGoedelnumber(16);</run>
<run>getWord(16);</run>
<run>getGoedelnumber("aba");</run>
<run>getWordAtIndex(8)</run>
<run>generateGoedelOrderedWords(10)</run>