Vorlesung 8 Lemke

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Übungsaufgabe S. 4 1.1 Gödelisierungseigenschaften 1.2 Ableitung der 4. Eigenschaft aus den ersten 3 2 Übungsaufgabe S. 11 2.1 Prozeduren für G (Primzahlverschlüsselung) und $G^{−1} : G(A^∗) → A^∗$ 3 Übungsaufgabe S. 13 3.1 f ist eine berechenbare Funktion genau dann, wenn h eine berechenbare Funktion ist 4 Kreativaufgabe 4.1 Ist MU Teil der MIU-Sprache?

Übungsaufgabe S. 4

Gödelisierungseigenschaften

Ableitung der 4. Eigenschaft aus den ersten 3

Übungsaufgabe S. 11

Prozeduren für G (Primzahlverschlüsselung) und $G^{−1} : G(A^∗) → A^∗$

from math import pow from itertools import product ALPHABET = ['a', 'b', 'c'] def generate_words_with_length(length): return ["".join(x) for x in product(ALPHABET, repeat=length)] def generate_wordset(): length = 0 while True: for w in generate_words_with_length(length): yield w length += 1 def is_prime(n): if n == 1: return False elif n == 2: return True for i in range(2, n): if n % i == 0: return False return True def generate_prime_numbers(): n = 2 while True: if is_prime(n): yield n n += 1 def goedel_prime(word): result = 1 primes = generate_prime_numbers() for l in word: p = next(primes) i = ALPHABET.index(l) + 1 result *= pow(p, i) return int(result) def goedel_prime_reverse(goedel_nr): for word in generate_wordset(): if goedel_prime(word) == goedel_nr: return word

wordset = generate_wordset() for i in range(25): w = next(wordset) g = goedel_prime(w) print('w =', w, 'G(w) =', g, 'G-1(G(w) =', goedel_prime_reverse(g))

ausführen

Übungsaufgabe S. 13

f ist eine berechenbare Funktion genau dann, wenn h eine berechenbare Funktion ist

Kreativaufgabe

Ist MU Teil der MIU-Sprache?

Toni: Aber warum muss das den ungerade sein?