Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Polynomordnungen für TES finden
Hallo,
wir haben verstanden, dass man zum Beweis der Terminierung eines TES eine Polynomordnung benutzen kann. Uns ist nicht genau klar, wie man auf die Polynome kommt.
Seite 17 im Inoffiziellen Skript im Beispiel 2.39 steht zB. P_+ := 2x+y+1 und P_* := xy.
Frage: Wie kommt man auf diese Polynome? Gibt es einen bestimmten Ansatz?
Viele Grüße
Im Prinzip ist es gezieltes Ausprobieren:
Aus (6) wissen wir über P_+ und P_*:
P_* ( x, P_+(y,z) ) > P_+ ( P_(x,y), P_(x,z) ) für alle x,y,z \in A (was auch immer dieses A \subseteq \N sein könnte).
aus (7) wissen wir:
P+( P+(x,y), z) > P+( x, P+(y,z))
Lass wegen (7) doch mal versuchen: P+(a,b) := 2a + b
dann haben wir mit (7): 2*(2x+y) + z > 2x + (2y+z). das gilt tatsächlich für x,y,z > 1, also lass uns damit weiterarbeiten.
wenn wir das jetzt in (6) einsetzen und rumprobieren, werden wir feststellen, dass P*(a,b) := a*b ganz gut aussieht, das liefert naemlich:
x * (2y+z) > 2xy + xz
das gilt leider aber nicht, aber man könnte es reparieren, indem man P+(a,b) zu 2a+b+1 umändert
dann wäre (7) naemlich:
x * (2y + z + 1) > 2xy + xz + 1
→ yay, (7) passt. kurz nachrechnen, dass wir (6) nicht kaputtgemacht haben (haben wir nicht), fertig.
Hallo, habe nochmals eine Frage zu den Polynomordnungen:
Gegegeben sei:
[b]- Polynomordnung Pβ (x, y) := x+y+1
- TES: x € y →x β ( x β y )[/b]
Gesucht sei: P€(x, y), sodass TES terminiert
Lösungsansatz:
- Wir wissen, dass die linke Seite von “→” größer sein muss, als die rechte Seite.
- Wir wissen, dass x β ( x β y ) = x β (x+y+1)+1 = x+(x+y+1)+1 = 2x + y + 2.
FRAGE: Können wir nun direkt durch Ablesen eine Polynomordnung für P€ angeben, der zB. um 1 größer ist als “die Rechte Seite” ?
Also: P€(x,y) := 2x + y + 2 +1= 2x + y + 3
D.h.: 2x + y + 3 > 2x+y+2
Vielen Dank 
PS: Sry für die Unübersichtlichkeit
edited: PSS: Thx an Windfisch 
Genau. Wenn dein TES wirklich nur aus dieser einen Regel besteht, ist das hier kein Problem.
Du hast aber glaube ich einen kleinen Fehler drin (der sich aber lustigerweise in deinem nächsten Schritt gleich wieder raushebt):
Du schreibst z.B.:
Du meinst aber vermutlich:
x β ( x β y ) = x β (x+y+1)
Worauf du allerdings (auch beispielsweise in der Klausur) achten solltest, ist, nicht einfach die Polynome und die Terme des TES zu vermischen.
Also statt:
Wäre besser:
P_x β (x β y) (x, y) = P_β (x, (x+y+1)) = x+(x+y+1)+1 = 2x+y+2
(Das Unterstrichene steht im Index.)
Oder einfach keine =s dazwischen.
Ich weiß nämlich nicht, ob das Punktabzug gibt.