Vorlesung 6 Lemke

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Übungsaufgabe S. 20 1.1 Indexlistenfindefunktion / Lösung des PCP 2 Übungsaufgabe S. 23 2.1 Turingmaschine als Akzeptor 3 Übungsaufgabe S. 28 3.1 Turing-Berechenbarkeit 3.2 Turing-Aufzählbarkeit 3.3 Turing-Entscheidbarkeit 4 Übungsaufgabe S. 25 4.1 Durchgehen der Verdopplungs-Turingmaschine mit Beispieleingabewort

Übungsaufgabe S. 20

Indexlistenfindefunktion / Lösung des PCP

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

print(find_index_sequence([('1', '101'), ('10', '00'), ('011', '11')], 20))

ausführen

Übungsaufgabe S. 23

Turingmaschine als Akzeptor

Ü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 zu M gehört, oder in einem Nicht-Endzustand, wenn das Wort nicht zu M gehört.

Übungsaufgabe S. 25

Durchgehen der Verdopplungs-Turingmaschine mit Beispieleingabewort