Aus ProgrammingWiki

Inhaltsverzeichnis 1 Paar Liste Seite 18/19 2 TM als Akzeptor Seite 23 3 Verdopplungsmaschine Seite 25 4 Kreativaufgabe Eigenschaften der Rado-Funktion Seite 36

Paar Liste Seite 18/19

def check_solution(K, index_list, p = False): x = "" y = "" for index in index_list: index -= 1 x += K[index][0] y += K[index][1] if p: print(x) print(y) return x == y

index_list = [2, 4, 3, 4, 4, 2, 1, 2, 4, 3, 4, 3, 4, 4, 3, 4, 4, 2, 1, 4, 4, 2, 1, 3, 4, 1, 1, 3, 4, 4, 4, 2, 1, 2, 1, 1, 1, 3, 4, 3, 4, 1, 2, 1, 4, 4, 2, 1, 4, 1, 1, 3, 4, 1, 1, 3, 1, 1, 3, 1, 2, 1, 4, 1, 1, 3] K = [("001", "0"), ("01", "011"), ("01", "101"), ("10", "001")] print(check_solution(K, index_list, True))

ausführen

from itertools import combinations, combinations_with_replacement, permutations, product from math import log def find_solution(K): indexes = list(range(1, len(K) + 1)) # len(indexes) ^ length stop_length = log(4**14, len(indexes)) for length in range(1, int(stop_length + 1)): for combination in product(indexes, repeat = length): if check_solution(K, combination): return combination length += 1

K = [("1", "101"), ("10", "00"), ("011", "11")] print(find_solution(K))

ausführen

TM als Akzeptor Seite 23

Verdopplungsmaschine Seite 25

Band, Zustand, Lese/Schreibekopfposition relativ zum Start

$11, q0, 0$

$\$1, q1, 1$

$\$1\$, q1, 2$

$\$1\$\$, q2, 3$

$\$1\$1\$, q3, 4$

$\$1\$11, q4, 3$

$\$1\$11, q4, 3$

$\$1\$11, q4, 2$

$\$1\$11, q5, 1$

$\$1\$11, q5, 0$

$\$1\$11, q0, 1$

Runde 2

$\$\$\$11, q1, 2$

$\$\$\$11, q2, 3$

$\$\$\$11, q2, 4$

$\$\$\$11\$, q2, 5$

$\$\$\$111\$, q3, 6$

$\$\$\$1111, q4, 5$

$\$\$\$1111, q4, 4$

$\$\$\$1111, q4, 3$

$\$\$\$1111, q4, 2$

$\$\$\$1111, q5, 1$

$\$\$\$1111, q0, 2$

$\$\$\$1111, q6, 3$

Kreativaufgabe Eigenschaften der Rado-Funktion Seite 36

1

$\Sigma(n) < \Sigma(n + 1)$

Man kann einfach $\Sigma(n)$ in $\Sigma(n + 1)$ verwenden und dann noch den zusätzlichen Zustand vor den Endzustand schieben. Dieser Itereriert solange nach rechts oder links bis er ein Bandzeichen findet. Durch den einen zusätzlichen Übergang kann man eine zusätzliche 1 an diese Stelle schreiben und dannach in den Endzustand über gehen.

2

?

Naiver Versuch

Man könnte alle TMs mit n Zuständen generieren. Das sollte funktionieren, da die Tupel an den Übergängen endlich sind. Damit sollte es endlich viele TM geben. Dann könnte man diese alle laufen lassen und die bestimmen, welche die meisten 1 schreibt. (wie trackt man das? man kann ja nachher nicht zählen, da man nie weis, ob noch eine 1 kommt oder unendlich viele Bandzeichen. Jedoch sollte das zur Laufzeit möglich sein).

Jedoch gibt es auch generierte TMs, welche nicht terminieren und dann hängt man wieder bei der Frage, on noch ein Erbeniss kommt oder ob die TM festhängt.

Problematisch mit dieser Herangehensweise ist das Generieren. Nur weil unsere Art zu Generieren nicht funktioniert hat, bedeutet, das nicht, dass es keine Lösung gibt. Man könnte die TMs ja schlauer generieren, damit die nicht haltenden nicht mit dabei sind.