BuK/IIm20/Vorlesung 3 Grüning

Wiki-Quelltext dieser Seite.

<language>Python</language>
== Einfache Beispiele für $\chi_M$ ==
== Seite 9 ==
'''Beispiel 1'''

<code id="6066ffdbf35ec">
def x_m(word):
    return len(word) == 3
</code>
<run id="6066ffdbf36fc">
print(x_m("a"))
</run>


'''Beispiel 2'''

<code id="6066ffdbf3673">
def x_m(word):
    if not word:
        return False
    return word[0] == 'a'

</code>
<run id="6066ffdbf3776">
print(x_m("babababab"))
</run>


== Seite 10 ==
'''Wie viele berechenbare charakteristische Funktionen gibt es?'''

Gibt es zu jedem M mindestens ein $\chi_M$ oder auch $\chi_M$ muss nicht entscheidbar sein?

Die Menge aller Teilmengen in A* ist überabzähbar unendlich (Potenzmenge Beweis siehe Vorlesung 2). Dadurch gibt es unendlich viele Mengen M. Dann gibt es mindestens


== Seite 15 ==

'''Gerade Zahlen sind aufzählbar:'''
<code id="60671267a7107">
def even_enumerable(number):
 return 2*number
</code>
Ist bijektiv (lineare Funktion ist bijektiv), total ($\forall x \in \mathbf{N}$) und berechenbar (da in Python Code)

'''Prim Zahlen sind aufzählbar:'''
<code id="60671267a716c">
import math

def is_prime(n):
    def helper(t):
        if t > math.sqrt(n):
            return True
        if n % t == 0:
            return False
        return helper(t + 2)

    if n == 2:
        return True
    if n <= 1 or n % 2 == 0:
        return False
    return helper(3)

def next_prime(n):
    n += 1
    while not is_prime(n):
        n += 1
    return n


def prim(n):
    if n == 0:
        return 2
    return next_prime(prim(n - 1))
</code>

<run id="60671267a71d3">
for i in range(20):
    print(prim(i))
</run>

'''A* ist aufzählbar'''

<code id="60671bbce098c">
import copy

def make_words(length, alphabet):
    if length == 0:
        return []
    words = copy.copy(alphabet)
    if length == 1:
        return words

    def word_append(word):
        new_words = []
        for letter in alphabet:
            new_words.append(word + letter)
        return new_words

    for word in words:
        for new_word in word_append(word):
            if len(new_word) > length:
                return words
            words.append(new_word)

    return words

def make_a_star(n, alphabet):
    length = 1
    a = []
    if n == 0:
        return alphabet[0]
    while len(a) < n:
        for words in make_words(length, alphabet):
            if len(a) == n:
                return a[n - 1]
            else:
                if words not in a:
                    a.append(words)
        length += 1
    return a[n - 1]
</code>
<run id="60671bbce0a22">
print(make_a_star(5, ["a", "b", "c"]))
</run>

Anmerkung: make_a_star ist nur surjektiv (das reicht ja aber auch), da 0 und 1 auf den gleichen Wert abgebildet werden.


== Seite 16 ==
'''Endliche Mengen aufzählbar'''

Man kann ganz einfach eine Python Prozedur angeben, welche die Werte vorher zugewiesen hat. Alle anderen aus $\mathbf{N}$ die größer als $|M|$ sind werden dem gleichen Element zugewiesen.

<code id="60671ebad7767">
def finite(n):
    M_finite = [...]
    if n == 1:
        return M_finite[1]
    
    if n == 2:
        return M_finite[2]
    ...
    if n == len(M_finite):
        return M_finite[len(M_finite)]
    
    return M_finite[0]
</code>


Alternativ könnte man auch auch $|M|$ Restklassen bilden und diese auf die Elemente zuweisen.


'''Die Menge G der Gitterpunkte (0, 0), (0, 1), ... einer x-y-Ebene ist aufzählbar.'''

(0, 0)
(1, 0)
(0, 1)
(0, -1)
(1, 1)
(-1, 0)

[[Bild:Outreigning_1_cantor.png]]

<code id="606c53778b7b3">
def whole_numbers(n):
    if n == 0:
        return 0
    if n % 2 == 0:
        return int(- (n + 1) / 2 + 0.5)
    else:
        return int((n + 1) / 2)

</code>
<run id="606c53778b84b">
for i in range(20):
    print(whole_numbers(i))
</run>

<code id="606c5d9024f36">
def gitter(n):
    x = 0
    y = 0
    dots = [tuple((whole_numbers(x), whole_numbers(y)))]

    while len(dots) < n:
      x += 1
      dots.append(tuple((whole_numbers(x), whole_numbers(y))))
      while x > 0:
        x -= 1
        y += 1
        dots.append(tuple((whole_numbers(x), whole_numbers(y))))
      y += 1
      dots.append(tuple((whole_numbers(x), whole_numbers(y))))
      while y > 0:
        x += 1
        y -= 1
        dots.append(tuple((whole_numbers(x), whole_numbers(y))))
    return dots
    #0 0
    #1:
    #dann +1 +0
    #solange x -1 +1 bis x = 0
    #dann +0 +1
    #solange +1 -1 bis y = 0    
    #goto 1


def order_gitter(li):
  def compare_tuple(x):
    return (abs(x[0]) + abs(x[1]))

  return sorted(li, key=compare_tuple)


def k(x, y):
  max_value = max(abs(x), abs(y))
  gitter_number = (2 * max_value + 1)**2
  li = gitter(gitter_number)
  li = order_gitter(li)
  print(li)
  for count, value in enumerate(li):
    if value[0] == x and value[1] == y:
      return count
</code>

<run id="606c5d9025057">
print(k(0, -1))
</run>



== Seite 20 ==

'''Halte Problem:''' Gibt es eine Turingmaschine die festellen kann ob, ein gegebener Algorithmus A für jede mögliche Eingabe x terminiert?

Nicht allgemein entscheidbar $\rightarrow$ aber semi-entscheidbar.

Wenn der Algorithmus für alle Eingaben nach endlicher Zeit terminiert, kann man das Halteproblem für diese Aussage mit "JA" beantworten. Wenn das Programm für auch nur eine Eingabe nicht terminiert kann die Turingmaschine nicht immer feststellen, ob der Algorithmus einfach lange rechnet oder für die Engabe nicht terminieren wird.


'''FIBS'''
<code id="606c415f6c590">
def FIBS(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2
    return FIBS(n-1) + FIBS(n-2)
</code>

<run id="606c415f6c63b">
for i in range(10):
    print(FIBS(i))
</run>

Eine Zahl n kann auf Enthalten sein in der Menge FIBS getestet werden. Da die das nächste Element aus FIBS größer oder gleich dem Vorgnänger ist, kann man nach dem auflisten aller Zahlen aus FIBS die kleiner oder gleich n sind genau feststellen, ob n in FIBS ist oder nicht.


'''Quadratzahlen QZ'''

<code id="606adaddc26d8">
def quad(n):
    return n**n
</code>

Jedem x aus X ($\mathbf{N}$) kann sogar genau ein y aus $D_f$ angegeben werden. QZ ist berechenbar, da eine Pythonprozedur angegeben wurde.
QZ ist entscheibar, da es eine Notbremse gibt, welche als unmittelbares Abbruchkriteritum gilt. Für eine gegebene Zahl a kann entschieden werden, ob es eine Qudaratzahl ist, da man alle Qudaratzahlen aufzählt die kleiner oder gleich a sind (endliche Menge). Ist a in dieser Menge ist die Antwort "TRUE" andernfalls "FALSE".

Wenn entscheibar, dann ist es auch semi-entscheibar und berechenbar.


'''Wörter $\{a, b\}^*$ mit a beginnend semientscheibar'''

Da jeder entscheidbare Algorithmus auch semi-entscheidbar ist und schon oben gezeigt wurde, dass die Menge aller "Wörter aus $\{a, b\}^*$, die mit 'a' beginnen" entscheidbar ist, ist sie auch semi-entscheidbar.


== Seite 23 ==

<code id="606adaddc2757">
def even(n):
    return int(2 * n)

def odd(n):
    return int(2 * n + 1)

def unite(i, f, g):
    if i % 2 == 0:
        return f(i / 2)
    else:
        return g((i-1) / 2)
</code>
<run id="606adaddc27d0">
for i in range(30):
    print(unite(i, even, odd))
</run>

== Kreativ Aufgabe Seite 24 ==
'''Satz: Die Durchschnittsmenge M1 $\cap$ M2 zweier aufzählbar unendlicher Mengen  $M1,M2 \subseteq A^*$ ist eine aufzählbare Menge.'''

Es ergeben sich drei Szenarien über die Anzahl der Elemente im Schnitt von M1 und M2:

Schnitt ist leer
Dann ist er per Definition aufzählbar.


Durch die Semi-Entscheidbarkeit der Frage $x \in M1$ bzw. $x \in M2$ kann man den Schnitt nicht so einfach feststellen. Wenn man das Festellen kann, dann würde man überprüfen ob f1(0) in M2 wenn ja: 0 -> f1(0) dann würde man prüfen, ob f2(0) in M1 ist, wenn ja 1 -> f2(0) und so weiter.

''Überlegungen:''

Kann man wenn man $f^-$ bilden kann festellen, ob f1(x) auch in M2 ist und umgegehrt?
Durch die Surjektivität von f1 und f2 muss es jedoch nicht unbedingt eine Umkehrfunktion geben.

'''Satz aus Vorlesung 4:''' Eine Menge M ist genau dann aufzählbar, wenn sie semi-entscheidbar ist.

Damit ein Word $w$ im Schnitt enthalten ist, dann ist es mindestens in M1 enthalten.

Man zählt M1 auf und überprüft mit $\chi'_{M2}$, ob $w \in M1$ auch in M2 enthalten ist. Wenn $\chi'_{M2}$ wahr liefert ist das Element in der Schnittmenge und kann somit dem $n$ welches gerade zum Aufzählen von $M1$ verwendet wird, abgebildet werden. Wenn es nicht terminiert, dann ist es nicht in $M2$ und somit auch nicht im Schnitt. Damit ist der Schnitt semi-entscheidbar und damit auch aufzählbar.