Vorlesung 8 Lemke

Aus ProgrammingWiki

< BuK < IIm20

Archivierte Version vom 2021-05-15T14:43:13+00:00. Aktuelle Version

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

Vorlesung 8 Lemke

Inhaltsverzeichnis

Ü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^∗

Übungsaufgabe S. 13

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

Kreativaufgabe

Ist MU Teil der MIU-Sprache?

Suche