BuK/IIm20/Vorlesung 8 Lemke

Wiki-Quelltext dieser Seite.

<language>Python</language>
== Übungsaufgabe S. 4 ==

=== Gödelisierungseigenschaften ===

[[Bild:Goedel_umkehr.jpg]]

=== Ableitung der 4. Eigenschaft aus den ersten 3 ===

[[Bild:Goedel_umkehr2.jpg]]

== Übungsaufgabe S. 11 ==

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

<code id="609fca277f7e4">
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
</code>

<run id="609fca277f861">
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))
</run>

== Übungsaufgabe S. 13 ==

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

[[Bild:Beweis_f_h_berechenbar_aequivalenz.jpg]]

== Kreativaufgabe ==

=== Ist MU Teil der MIU-Sprache? ===

[[Bild:MIU-Grammatik.jpg]]

'''Toni: Aber warum muss das den ungerade sein?'''