Vorlesung 10 Lemke

Aus ProgrammingWiki

Ausschroten der Definition der WHILE-Berechenbarkeit

Übungsaufgabe S. 33

Nachweis, dass die Ackermann-Peter-Funktion WHILE-berechenbar ist

def ack(x, y):
	if x == 0:
		return y + 1
	elif y == 0:
		return ack(x-1, 1)
	else:
		return ack(x-1, ack(x, y-1))
		
def ack_while(x, y):
	x1 = x
	x2 = y
	xi = 1
	while xi != 0:
		# if ack doesn't stop and return a result, xi will never be set to 0
		x0 = ack(x1, x2) # is this allowed?
		xi = 0
	return x0

# (3, 4) is maximum, then python cannot deal with the recursion anymore
# (4, 3) is already too much
print(ack_while(3, 4))

Suche