BuK/IIm20/Vorlesung 6 Lemke

Wiki-Quelltext dieser Seite.

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

=== Indexlistenfindefunktion / Lösung des PCP ===

<code id="608c28d240783">
from itertools import product

def is_valid_index_sequence(
	sequence: list[int], pair_list: list[tuple]
):
	word_x = ''
	word_y = ''
	for index in sequence:
		word_x += pair_list[index][0]
		word_y += pair_list[index][1]
		
	return word_x == word_y
	
def find_index_sequence(pair_list, max_n):
	indexes = [i for i in range(len(pair_list))]
	for n in range(1, max_n):
		sequences = [x for x in product(indexes, repeat=n)]
		for s in sequences:
			if is_valid_index_sequence(list(s), pair_list):
				return s
</code>

<run id="608c28d2407e2">
print(find_index_sequence([('1', '101'), ('10', '00'), ('011', '11')], 20))
</run>

== Übungsaufgabe S. 23 ==

=== Turingmaschine als Akzeptor ===

[[Bild:Trichterbilder-TMAkzeptor.jpg]]

== Übungsaufgabe S. 28 ==

=== Turing-Berechenbarkeit ===

Eine Funktion ist genau dann turing-berechenbar, wenn  eine TM existiert, die für alle Funktionswerte als Eingabewörter in beliebig vielen Schritten zu einem Endzustand kommt

=== Turing-Aufzählbarkeit ===

Eine Menge M ist genau dann turing-aufzählbar, wenn es eine Turingmaschine gibt, die mit mit jedem Wort, was zu M gehört, als Eingabe in beliebig vielen Schritten zu einem Endzustand kommt.

=== Turing-Entscheidbarkeit ===

Eine Menge M ist genau dann turing-entscheidbar, wenn es eine Turingmaschine gibt, die für jedes Wort aus der Wortmenge des Alphabetes von M, nach beliebig vielen Schritten anhält, entweder in einem Endzustand, wenn das Wort zur Menge gehört, oder in einem Nicht-Endzustand, wenn das Wort nicht zu M gehört.