Vorlesung 6 Lemke

Aus ProgrammingWiki

Archivierte Version vom 2021-04-30T16:31:36+00:00. Aktuelle Version

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

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

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

Vorlesung 6 Lemke

Inhaltsverzeichnis

Übungsaufgabe S. 20

Indexlistenfindefunktion / Lösung des PCP

Übungsaufgabe S. 23

Turingmaschine als Akzeptor

Übungsaufgabe S. 28

Turing-Berechenbarkeit

Turing-Aufzählbarkeit

Turing-Entscheidbarkeit

Suche