Theoretische Informatik

3. Übungsblatt

Aufgabe 1:

20
Umrechnung zwischen Zahlensystemen
Vervollständigen Sie folgende Tabelle!
100%
Fett-Markiert sind die vorgegebenen Werte
dezimalbinaerdyadisch3-adisch
3510001111211322
49110001211211211
8310100111212112232
1271111111111111111131

Aufgabe 2:

30
Simulation einer RAM durch ein Python-Programm
Wenden Sie die Konstruktion aus Satz 2.20 auf folgendes RAM-Programm an, das hier eine Funktion N × N → N berechnet. Geben Sie das entstehende Python-Programm ab!
0 R3 <- RR2
1 R3 <- R3 + R2
2 R2 <- R2 + R1
3 RR2 <- R3
4 R0 <- R0 - R1
5 IF R0 > 0 GOTO 0
6 R0 <- RR2
7 STOP
100%
def read(u,v,a): # liefert den Inhalt von Ra
  i=0
  while (i < len(u) and u[i] != a): # Index a suchen
    i=i+1
  if (i == len(u)):
    u += [a]
    v += [0]
  return v[i]

def write(u,v,a,b):
  i=0
  # Listen erweitern
  # Inhalt von Ra zurueck
  # schreibt b in Ra
  while (i < len(u) and u[i] != a): # Index a suchen
    i=i+1
  if (i == len(u)):
    u += [a]
    v += [0]
  v[i] = b
  # Listen erweitern
  # schreibt b in Ra

def phi(x1,x2):
  u = [0,1]
  v = [x1,x2]
  br = 0
  while (br < 7):

    if (br == 0):
      # 0: R3 <- RR2
      i = read(u,v,2)
      j = read(u,v,i)
      write(u,v,3,j)
      br = br + 1

    if (br == 1):
      # 1: R3 <- R3 + R2
      i = read(u,v,3) + read(u,v,2)
      write(u,v,3,i)
      br = br + 1

    if (br == 2):
      # 2: R2 <- R2 + R1
      i = read(u,v,2) + read(u,v,1)
      write(u,v,2,i)
      br = br + 1

    if (br == 3):
      # 3: RR2 <- R3
      i = read(u,v,3)
      j = read(u,v,2)
      write(u,v,j,i)
      br = br + 1

    if (br == 4):
      # 4: R0 <- R0 - R1
      i = read(u,v,0) - read(u,v,1)
      if (i < 0):
        i=0
      write(u,v,0,i)
      br = br + 1

    if (br == 5):
      # 5: IF R0 > 0 GOTO 0
      if (read(u,v,0) > 0):
        br = 0
      else:
        br = br + 1

    if (br == 6):
      # 6: R0 <- RR2
      i = read(u,v,2)
      j = read(u,v,i)
      write(u,v,0,j)
      br = br + 1

    #if (br == 7):
      # 7: STOP
    #while ende
  return read(u,v,0)

Aufgabe 3:

20
TM-Programm
Sei l : N → N mit l(x) = 2x + 1. Geben Sie ein kommentiertes Programm einer 1-Band-TM an, die l in dyadischer Darstellung berechnet. (gefordert: Beschreibung der Arbeitsweise + kommentiertes Programm)
100%

Aufgabe 4:

30
Simulation einer TM durch ein Python-Programm
Simulieren Sie folgende 2-Band-Turingmaschine M entsprechend der im Beweis des Satzes 2.45 verwendeten Methode. Neben den in While-Programmen erlaubten Konstrukten dürfen Sie auch die im Skript auf Seite 69 beschriebenen Erweiterungen (z.B. Listen) benutzen. Sei M=(Σ,Z,f,z0,z1) mit Σ={􏰀,1,2,∗} und Z={z0,z1,z2,z3}. Die Überführungsfunktion f : {z0, z2, z3} × Σ2 → Z × Σ2 × {L, O, R}2 ist durch folgendes Programm gegeben, wobei 􏰀 durch _ dargestellt ist.
(z0,1,_)->(z0,1,1,R,L)
(z0,2,_)->(z0,2,2,R,L)
(z0,_,_)->(z2,_,_,O,R)
(z2,_,1)->(z2,1,_,R,R)
(z2,_,2)->(z3,2,_,R,R)
(z3,_,1)->(z3,1,_,R,R)
(z3,_,2)->(z3,_,_,R,R)
Sei g : N → N die Funktion, die von M in dyadischer Darstellung berechnet wird. Für Ihr Python-Programm P muss dann gelten:
• Falls x ∈ N − Dg, so liefert P bei Eingabe x kein definiertes Ergebnis.
• Falls x ∈ Dg, so liefert P bei Eingabe x den Wert g(x).
0%
Keine Loesung mitgeschrieben

Zusatzaufgabe 1:

20
Definition von Turing-Maschinen
Seien k ∈ N+, Z eine endliche Menge und Σ eine endliche Menge mit 􏰀,∗ ∈ Σ. Bestimmen Sie die Anzahl der k-Band-Turing-Maschinen mit dem Alphabet Σ und der Zustandsmenge Z.
0%
Keine Loesung mitgeschrieben

Zusatzaufgabe 2:

30
RAM-Simulator
Schreiben Sie ein Python-Programm, das allgemeine RAMs simulieren kann. Dabei sind RAM-Programme als Listen entsprechend der Punkte 1 und 2 auf Seite 164 codiert. Beispiel:
Programm:
0 R3 <-
1 IF R1=0 GOTO 5
2 R2<-R2+R0
3 R1<-R1-R3
4 GOTO1
5 R0<-R2
6 STOP
Code als Python-Liste:
[[3, 3, 1, 0], [7, 1, 5, 0], [4, 2, 2, 0], [5, 1, 1, 3], [6, 1, 0, 0], [0, 0, 2, 0], [9, 0, 0, 0]]
100%
def read(u,v,a): # liefert den Inhalt von Ra
  i=0
  while (i < len(u) and u[i] != a): # Index a suchen
    i=i+1
  if (i == len(u)):
    u += [a]
    v += [0]
  return v[i]

def write(u,v,a,b):
  i=0
  # Listen erweitern
  # Inhalt von Ra zurueck
  # schreibt b in Ra
  while (i < len(u) and u[i] != a): # Index a suchen
    i=i+1
  if (i == len(u)):
    u += [a]
    v += [0]
  v[i] = b
  # Listen erweitern
  # schreibt b in Ra

def phi(code, args):
  u = []
  v = args
  i = 0
  while (i < len(args)):
    u.append(i)
    i = (i+1)
  br = 0
  
  while (br < len(code)):
    step = code[br]
    befehl = step[0]
    a = step[1]
    b = step[2]
    c = step[3]

    if (befehl == 0):
      # Ri <- Rj
      i = read(u,v,b)
      write(u,v,a,i)
      br = br + 1

    if (befehl == 1):
      # Ri <- RRj
      i = read(u,v,b)
      j = read(u,v,i)
      write(u,v,a,j)
      br = br + 1

    if (befehl == 2):
      # RRi <- Rj
      i = read(u,v,b)
      j = read(u,v,a)
      write(u,v,j,i)
      br = br + 1

    if (befehl == 3):
      # Ri <- j
      write(u,v,a,b)
      br = br + 1

    if (befehl == 4):
      # Ri <- Rj + Rk
      i = read(u,v,b) + read(u,v,c)
      write(u,v,a,i)
      br = br + 1

    if (befehl == 5):
      # Ri <- Rj-Rk
      i = read(u,v,b) - read(u,v,c)
      if (i < 0):
        i=0
      write(u,v,a,i)
      br = br + 1

    if (befehl == 6):
      # GOTO i
      br = a

    if (befehl == 7):
      # IF Ri=0GOTO j
      if (read(u,v,a) == 0):
        br = b
      else:
        br = br + 1

    if (befehl == 8):
      # IF Ri>0GOTO j
      if (read(u,v,a) > 0):
        br = b
      else:
        br = br + 1

    if (befehl == 9):
      # STOP
      br = (len(code)+2) # Mehr als zwei nicht!!!!
  return read(u,v,0)
Für Testzwecke: 
#TROLLOLLOLOLOLLOLLOLOLOLOLO
print phi([[3, 3, 1, 0],[7, 1, 5, 0],[4, 2, 2, 0],[5, 1, 1, 3],[6, 1, 0, 0],[0, 0, 2, 0],[9, 0, 0, 0]], [7, 13, 42, 1, 77])