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>
<language>Javascript</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>
/*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>