Vorlesung 6 Grüning

Aus ProgrammingWiki

Archivierte Version vom 2021-05-01T10:58:48+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Paar Liste Seite 18/19
2 TM als Akzeptor Seite 23
3 Verdopplungsmaschine Seite 25
4 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))

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

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 $

Eigenschaften der Rado-Funktion Seite 36

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

Vorlesung 6 Grüning

Inhaltsverzeichnis

Paar Liste Seite 18/19

TM als Akzeptor Seite 23

Verdopplungsmaschine Seite 25

Eigenschaften der Rado-Funktion Seite 36

Suche