BuK/IIm20/Vorlesung 6 Grüning

Wiki-Quelltext dieser Seite.

<language>Python</language>
= Paar Liste Seite 18/19 =

<code id="608c2edf0290c">
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
</code>
<run id="608c2edf0297a">
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))
</run>

<code id="608c3c0157531">
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
</code>

<run id="608c3c01575bc">
K = [("1", "101"), ("10", "00"), ("011", "11")]
print(find_solution(K))
</run>

= 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.