Information: Software-Patente unter der Lupe [4.2]
Inhaltsverzeichnis
- 1 Teile und herrsche
- 2 Mathematische Grundlagen
- 3 Turing-Maschinen und -Kalkül
- 4 Beweise über Software
- 5 Analysen
- 5.1 Analyse von Aussage a)
- 5.2 Analyse von Aussage b)
- 5.3 Analyse von Aussage c)
- 5.4 Analyse von Aussage d)
- 6 Schlussfolgerung
- 7 Literatur
Die Entstehung des Patentwesens fußte im 19. Jahrhundert (dt. Patentgesetz von 1877)
zwangsläufig auf den damaligen wissenschaftlichen Möglichkeiten und Kenntnissen.
Ein epistemologisches Paradigma war, dass man das Wissen über die Welt in voneinander
unabhängige Kategorien einteilen kann, z.B. Mathematik, Physik, Chemie, Biologie,
Soziologie, Astronomie etc. und in diesen Wissensgebieten sollte es immer weitere
feinere unabhängige Unterteilungen geben.
Diesen Ansatz nennt man Divide and Conquer ("Teile und herrsche").
Viel später musste man feststellen, dass dieser Ansatz nicht so funktionierte
wie man es sich zuerst gedacht hatte.
Mathematischer ausgedrückt war die Annahme von Kategorien, eine Gruppierung von
Elementen in zueinander disjunkte Mengen (Baumstruktur) falsch.
Die moderne Sichtweise geht heute von sich überlappenden Mengen (Netzwerkstruktur) aus.
Das wissenschaftliche Weltbild hatte besonders durch die Quantentheorie (1925-1928) eine
grundlegende Änderung erfahren, die in ihrem Kern eine nichtlokale Theorie darstellt,
was besagt, dass alles mit allem verbunden ist.
Dies führte auch zu interdisziplinären Ansätzen: Biochemie, Bioinformatik,
Wirtschaftsinformatik, physikalische Chemie, angewandte Mathematik etc.
Trotz aller wissenschaftlichen Erkenntnisse der letzten 125 Jahre, basiert das
Patentwesen heute immer noch implizit auf dem überholten kategorischen Ansatz:
a) Alle Ideen sind gegeneinander abgrenzbar und es gibt unendlich viele davon.
In der Abbildung rechts soll dies durch farbige Kreise symbolisiert sein.
Freie Ideen sind "blau" dargestellt und patentierte "rot".
Ideen, die auf anderen Ideen basieren bzw. andere Ideen enthalten, sollen abgeleitete
Ideen heißen (siehe Punkt c).
|
|
b) Zu einer Idee gibt es eine Unzahl von Realisierungen dieser Idee.
Realisierungen unterschiedlicher Ideen sind voneinander verschieden.
In der Abbildung rechts sollen die weissen Kreise unterhalb der Ideen für deren
konkrete Realisierungen stehen.
Die roten Kästen stehen jeweils für ein Patent.
Es ist wie ein Zaun um ein Grundstück.
Gemeinsam genutzter Boden gibt es nicht.
Jedes Patent hat somit seinen eigenen Geltungsbereich.
|
|
c) Ein Patent deckt auch die Ableitung einer Idee bzw. die Ableitung der
Realisierung einer Idee ab.
Eine Ebene unter den konkreten Realisierungen sind, mit Pfeilen erreichbar, davon
abgeleitete Realisierungen gezeichnet.
Wenn z.B. Idee 1 das "Rad" wäre, dann könnte x für einen
Schubkarren stehen.
Wenn z.B. Idee 2 eine "Bremse" wäre, dann könnte z für einen
Seilzug mit Bremse stehen.
Der Fall einer Patentverletzung stellt y dar, wenn z.B. y ein Fahrrad mit Bremse wäre.
Der Patentinhaber argumentiert, dass derjenige, der y baut sich seiner Idee bedient habe.
Man sieht, dass sich der Anspruchsbereich des Patents beliebig ausdehnt, wenn die
patentierte Idee in der Ableitung mit enthalten ist.
|
|
d) Es gibt noch genug freie Ideen und Realisierungen von Ideen, sodass die Menge
der patentierten Ideen nicht stark störend wirkt.
|
Formulieren wir nun die obigen Aussagen aus dem Patentwesen um, so dass sie auf den
Bereich der Software passen.
Hierzu setzen wir Idee mit Funktion (bzw. Abbildung) und die Realisierung einer Idee
mit einem Programm (bzw. Algorithmus) gleich:
a) Alle Funktionen sind gegeneinander abgrenzbar und es gibt unendlich viele davon.
b) Zu einer Funktion gibt es eine Unzahl von Realisierungen (Programme).
Programme unterschiedlicher Funktionen sind voneinander verschieden.
c) Ein Patent deckt auch die Ableitung einer Funktion bzw. die Ableitung des
Programmes zu einer Funktion ab.
d) Es gibt noch genug freie Funktionen und Programme, sodass die Menge
der patentierten Funktionen nicht stark störend wirkt.
Aufgrund unserer Alltagserfahrungen halten wir alle diese Aussagen intuitiv
für richtig und es scheinen nähere Beweise, die die Richtigkeit eindeutig
nachweisen, überflüssig zu sein.
Wir möchten nun aber in diesem Text die entsprechenden Beweise nach und nach entwickeln.
Es wird sich herausstellen, dass die obigen Aussagen widersprüchlich und unangemessen sind.
In der Mathematik leitet man Relationen aus der Mengenlehre ab.
Kommt es auf die Reihenfolge zweier Elemente x1 , x2 an, so wird
der Begriff des geordneten Paares oder 2-Tupel ( x1 , x2 ) verwendet.
Eine mengentheoretische Definition des geordneten Paares wäre folgende:
Definition (1)
( x1 , x2 ) { x1 , x2 }
wegen { x1 , x2 } = { x2 , x1 }
aber:
( x1 , x2 ) := { { x1 } , { x1 , x2 } }
Eine andere Möglichkeit zur Bildung von 2-Tupeln besteht darin
Zahlen zur Strukturierung von Zahlen zu verwenden (Gödelisierung).
Mit geordneten Paaren kann man das karthesische Produkt definieren.
Es dient einerseits der Konstruktion neuer mathematischer Gebilde,
andererseits zur Definition des Relationsbegriffs.
Definition (2)
M1
... Mn :=
{ ( x1 , ... , xn ) | xi
Mi } heißt
karthesisches Produkt der Mengen M1 , ... , Mn.
Die Menge M1
M2 := { ( x1 , x2 ) | x1
M1
x2 M2 }
heißt auch Paarmenge.
Definition (3)
Jede Teilmenge R
M1
... Mn
heißt n-stellige Relation.
Relationen stellen meist keine eindeutigen Beziehungen zwischen Mengen her, d.h.
einem Element können durchaus mehrere Elemente zugeordnet sein.
Wenn es aber um Eindeutigkeit geht, benutzt man den Begriff der Abbildung bzw. Funktion.
Definition (4)
Eine linkstotale, rechtseindeutige Relation f
M N heißt Abbildung (Funktion).
Anschaulich kann man sich eine Funktion als Menge von 2-Tupeln vorstellen,
wobei ein Tupel jeweils eine eindeutige Zuordnung vermittelt.
Mit den obigen Definitionen haben wir jetzt eine abstrakte Beschreibung der Objekte
um die es in diesem Text gehen soll: Funktionen.
In den Jahren 1936-1941 wurde von Alonzo Church [CHU36, CHU41]
der -Kalkül zur Formalisierung des
Funktionenbegriffs entwickelt.
Er ist ein abstraktes Modell von Berechenbarkeit, basierend ausschließlich auf
Funktionsdefinition und Funktionsanwendung.
Später erkannte man, dass der -Kalkül ein
effizientes Mittel zur Beschreibung von Programmiersprachen darstellt.
1960 diente er McCarthy als Basis zur Entwicklung der Programmiersprache LISP.
Schon 1937 bewies Alan Turing in [TUR37], dass der
-Kalkül und die Turing-Maschine alternative
Beschreibungen ein und derselben Sache sind: unseres Verständnisses davon was
berechenbar ist.
Turing-Maschinen sind heutzutage allgegenwärtig, denn jeder existierende Computer
bzw. PC ist eine Turing-Maschine.
Es folgt eine Definition, was unter einem Kalkül zu verstehen ist:
Definition (5)
- Ein Alphabet ist eine Menge von Symbolen.
- Die Menge aller möglichen Worte über dem Alphabet A soll durch A* beschrieben sein.
- Eine Sprache K über einem Alphabet A ist dann eine Teilmenge aller möglichen Worte
über dem Alphabet, somit: K A*.
- Ein Kalkül ist eine Sprache mit einer Menge von Transformationsregeln, die auf
der Menge der Worte der Sprache definiert sind.
Ausgehend von (5) wird die folgende Definition des
-Kalküls verständlich:
Definition (6)
Es sei V eine abzählbare Menge von Variablen.
Die Sprache L der -Terme ist über dem
Alphabet V
{ ( , ) , } induktiv wie folgt definiert:
x V x L
M , N L
( M N ) L
Applikation
x V
M L
( x M ) L
Abstraktion
Eine genauere Erläuterung ersparen wir uns hier, da dies der interessierte Leser
in der vielfältigen Literatur zum -Kalkül
nachlesen kann.
Die ausreichende Kenntnis des -Kalküls sei aber
für die weitere Lektüre dieses Textes vorausgesetzt.
Anmerkung
Es sei hier noch auf einen Widerspruch des Patentrechts hingewiesen, wenn Software
patentierbar wird.
Im Patentrecht hat man mathematische Formeln ausdrücklich von der Patentierung
ausgeschlossen.
Wie wir aber gesehen haben ist Programmieren nichts anderes als Mathematik, wenn man
den -Kalkül o.ä. verwendet und Programme sind
mathematische Formeln.
Dass dies auch in der Praxis funktioniert zeigen funktionale Programmiersprachen wie
LISP, ML, Miranda, Haskell, Scheme, Clean etc.
Beweise über Eigenschaften von Programmen zu führen ist ein schwieriges
Unterfangen, da es in der Informatik viele Problemstellungen gibt, von denen bewiesen
ist, dass sie unlösbar sind.
Das bekannteste Problem ist sicher das Halteproblem.
Beim Halteproblem geht es um die Frage, ob es ein Programm gibt, das für jedes
Programm entscheiden kann ob dieses anhält bzw. terminiert.
Diese Frage ist unlösbar.
Ein solches Programm existiert nicht.
Es kommt aber noch schlimmer: Rice [RIC53] hat 1953 bewiesen, dass
praktisch alle interessanten Aussagen über Programme im Allgemeinen nicht entscheidbar sind
(siehe auch [RIC56] oder alternativ [HOP79]).
Satz von Rice
"Jede nicht triviale semantische Eigenschaft von Algorithmen ist nicht entscheidbar."
Eine Eigenschaft nennt man in diesem Zusammenhang trivial, wenn entweder jede oder
keine berechnete Funktion sie besitzt.
Somit sind beispielsweise nicht entscheidbar,
- ob die berechnete Funktion total, überall undefiniert, injektiv, surjektiv
oder bijektiv usw. ist,
- ob zwei gegebene Algorithmen dieselbe Funktion berechnen,
- ob ein gegebener Algorithmus korrekt zu einer gegebenen Funktion ist, d.h. es
wird nie ein Programm zur allgemeinen Software-Verifikation geben.
Auf der einen Seite ist es schon entmutigend, wenn man den Satz von Rice liest, aber
auf der anderen Seite kann man der Tatsache auch etwas positives abgewinnen.
Wenn es nämlich gelingt einen Beweis zu führen, dann beweist man immer eine
triviale Eigenschaft von Algorithmen, die uneingeschränkt für alle gilt.
Natürlich schränkt der Satz von Rice die Möglichkeiten ein.
Er gibt aber auch Hinweise wie man Beweise zu konstruieren hat bzw. wo man suchen sollte.
a) Alle Funktionen sind gegeneinander abgrenzbar und es gibt unendlich viele davon.
Wir präzisieren die Aussage, indem wir nachweisen, dass es
überabzählbar viele Funktionen gibt und dass nur abzählbar unendlich
viele davon berechenbar sind.
Definition (7)
Eine Funktion heißt berechenbar, wenn eine abstrakte Maschine existiert, die die
Funktion berechnet (ausführt).
Wenn wir prüfen wollen, ob es Funktionen gibt, die sich nicht durch Algorithmen
berechnen lassen, dann hilft uns folgende allgemeine Eigenschaft von Algorithmen:
Jeder Algorithmus läßt sich durch einen endlichen Text über einem
festen, endlichen Alphabet beschreiben.
Sei A ein Alphabet A = { a1 , ... , an } dem
eine alphabetische Ordnung a1 < a2 < ...
< an zugrunde liegt, dann ist bekanntlich A* die
Menge aller Texte bzw. Wörter über A:
A* = { ,
a1 , ... , an , a1a1 ,
a1a2 , ... ,
a4a1a6a2a1 , ... }
Das Zeichen soll hierbei für das Wort
mit der Länge 0 stehen.
Nun kann die Menge A* zunächst der Länge nach aufgelistet
werden, d.h. zu jeder Länge m gibt es nm verschiedene Wörter
über A (also endlich viele); dann sortiert man noch innerhalb der
Wörter gleicher Länge lexikographisch, also bei
b1b2 ... bm <
c1c2 ... cm gilt b1 <
c1 (b1 = c1
b2 < c2)
... (b1 = c1
... bm-1 = cm-1
bm < cm).
Damit haben wir eine Ordnung auf A* eindeutig bestimmt und
es folgt daraus: A* ist abzählbar.
Da es nicht mehr berechenbare Funktionen als berechnende Algorithmen gibt
und nicht mehr Algorithmen als die sie beschreibenden Texte geben kann,
gilt offenbar: Die Menge der berechenbaren Funktionen ist abzählbar.
Funktionen gibt es aber weit mehr.
Betrachten wir hierzu die auf der Menge der natürlichen
Zahlen definierten Funktionen f, die als Ergebnisse nur die Werte 0 oder 1 liefern; jede
davon definiert eine Teilmenge Mf
derjenigen Zahlen m
, für die f(m) = 1 ist.
Umgekehrt gibt es für jede
Teilmenge M
eine solche Funktion fM, die charakteristische Funktion der Menge M.
Die Menge der Teilmengen M
ist aber überabzählbar, ebenso also die Menge
ihrer charakteristischen Funktionen; und damit die Menge aller Funktionen erst recht.
Die Folgerung daraus ist, daß es nicht berechenbare Funktionen geben muss.
Anhand dieser Ergebnisse kann man zwar sagen, dass es mehr Funktionen gibt, als man
berechnen kann, aber die Aussage unter a) ist dennoch wahr.
b) Zu einer Funktion gibt es eine Unzahl von Realisierungen (Programme).
Programme unterschiedlicher Funktionen sind voneinander verschieden.
Wir wissen, dass Funktionen durch Programme berechnet werden können.
Wenn es um eine konkrete Funktion f geht, dann kann man sie als Abbildung
f: A B schreiben, d.h. f bildet die
Menge der Eingabewerte A auf die Menge der Ausgabewerte B ab.
Funktionen können wie anfangs gezeigt als Menge von 2-Tupeln aufgefasst werden.
Die einfachsten Funktionen, die man sich vorstellen kann wären jene, die nur
ein 2-Tupel enthalten.
Kompliziertere Funktionen lassen sich aufbauen, indem einfach weitere 2-Tupel
hinzu genommen werden.
Um nicht alle Tupel explizit aufzählen zu müssen, gibt es auch zahllose
Möglichkeiten die Tupel-Belegung zu berechnen.
Beispiele
f(x) = { 1234 für x=1
g(x) = { 1234 für x=1 und 48 für x=2 und 543 für x=3
h(x) = { 1234 für x=1 und 0 sonst
k(x) = x2 - 2x + 1
Betrachten wir nun drei spezielle Funktionen f1, f2
und f3:
f1(x) = { 0 für x=0 und 1 für x=1
f2(x) = x
f3(x) = x2
f1 besteht aus zwei 2-Tupeln, d.h. der Definitionsbereich und
der Wertebereich sind nur für 2 Werte definiert.
Im Gegensatz dazu seien f2 und f3 über ganz
definiert.
Wenn wir nun festlegen, dass für unsere Rechnungen bei allen drei Funktionen
nur zwei Punkte (0 und 1) im Definitionsbereich verwendet werden sollen, sehen wir,
dass alle drei Berechnungen dieselben Werte liefern.
Hinweis: Beim Programmieren benutzt man Typendeklarationen zur Eingrenzung des
Definitions- und Wertebereichs.
Man kann daher sagen, dass x und x2 ebenfalls gleichwertige Algorithmen
zur Berechnung von f1 darstellen und man kann sagen, dass f2
und f3 Ableitungen von f1 sind, da sie f1 komplett
beinhalten.
Umgekehrt gilt dies nicht.
Diese Eigenschaft von Funktionen ist kein Zufall.
Es liegt daran, dass Relationen als Teilmenge definiert wurden.
Siehe Definition (3).
Bei der Programmierung eines Computers ist man noch stärker eingeschränkt.
So lässt sich z.B. f3(x) = x2 gar nicht wirklich berechnen.
Wegen begrenztem Speicher und Rechengeschwindigkeit können Programme meist nur
Näherungen von Funktionen ausrechnen, d.h. man berechnet nur eine Teilmenge der
eigentlichen Funktion.
Ein eingeschränkter Definitions- oder Wertebereich stellt aber strenggenommen
eine andere Funktion dar.
Damit haben wir gezeigt, dass ein Programm durchaus für mehrere Funktionen die
korrekte Abbildung berechnen kann, ja dies sogar zwingend tun muss, sonst könnten
Programme überhaupt keine Ergebnisse liefern.
Dies steht im Gegensatz zur Aussage b), dass Programme nur einer Funktion
zugerechnet werden können, was ja Voraussetzung im kategorischen Ansatz war.
Aussage b) ist somit falsch.
Anmerkung
Man vergleiche Mehrdeutigkeit und Resourcenbeschränkungen bei der
Funktionsberechnung durch Programme mit der Folgerung, aus dem Satz von Rice, nach der
es nicht entscheidbar ist, ob zwei gegebene Algorithmen dieselbe Funktion berechnen.
c) Ein Patent deckt auch die Ableitung einer Funktion bzw. die Ableitung des
Programmes zu einer Funktion ab.
Nach Aussage c) verletzen alle Funktionen eine patentierte Funktion, wenn sie eine
Ableitung davon darstellen.
Im vorigen Abschnitt hatten wir schon eine Art von Ableitung kennengelernt, die darauf
basiert, dass eine abgeleitete Funktion genau die 2-Tupel der patentierten Funktion
enthält.
Es gibt aber auch Funktionen, die nach außen keine oder nur sehr wenige gemeinsame
Tupel besitzen, aber dennoch ist die eine Funktion komplett in der anderen enthalten,
um eine Berechnung zu realisieren.
Somit liegt auch eine Ableitung vor.
Wir wollen nun das Enthaltensein einer Funktion in einer anderen Funktion
genauer untersuchen.
Zur Veranschaulichung betrachten wir Darstellungen von Relationen als Matrizen.
Es sei immer eine Funktion f: A B
gemeint und es gelte: a0 , a1 , ... , aN
A und b0 , b1 ,
... , bM B.
Weiterhin bezeichnen N und M die Mächtigkeit der Mengen, also N = card(A)
und M = card(B).
Wie man sieht, gibt es nur drei Fälle.
Da wir uns auf Funktionen beschränken wollen, also rechtseindeutige Relationen,
entfällt Fall 3) und sei hier nur der Vollständigkeit halber gezeigt.
Jedes Kreuz steht für ein Tupel.
Als Charakteristik können wir die Anzahl der Kreuze pro Zeile bzw. pro Spalte bestimmen.
|
Fall 1) |
|
Fall 2) |
|
Fall 3) |
Zeilensumme |
1 |
|
1 |
|
2,...,M |
Spaltensumme |
2,...,N |
|
1 |
|
1 |
Da die Matrizen nur wirklich vorhandene Tupel darstellen (in der Abbildung bitte über
die Ungenauigkeit im variablen "..." Bereich hinwegsehen) muss jede Zeile oder Spalte
immer mit mindestens einem Kreuz belegt sein.
Im Fall 2), d.h. N = M, sind alle Summen gleich 1.
Es wird also jeder Eingangswert auf einen anderen Ausgangswert abgebildet.
Wir können sagen, dass die Abbildung in diesem Fall eineindeutig ist, also
bi = f ai und
ai = f-1 bi.
Im Fall 1), d.h. N > M, gibt es Spaltensummen, die größer als 1 sind.
Es werden so mehrere Eingangswerte auf denselben Ausgangswert abgebildet.
Es gilt nur noch bi = f ai.
Die Umkehrfunktion gilt nicht, da sie mehrere Werte liefern müsste, was wir ja
ausgeschlossen haben.
Dennoch können wir auch hier die eineindeutige Abbildung finden.
Satz (1)
Jede Funktion f: A B
besitzt eine innere eineindeutige Kernfunktion KQ mit Q = card(B).
Beweis (1)
Wegen des Aufbaus der 2-Tupel erzwingt eine Anzahl von M = card(B) Ausgabewerten
auch M Eingabewerte.
Da Funktionen rechtseindeutig sind, müssen die Eingabewerte alle verschieden sein.
Diese 2-Tupel bilden die Funktion KQ (bzw. die quadratische Matrix
KQ) mit Q = M = card(B).
Q ist die Anzahl der Zeilen bzw. Spalten dieser Matrix.
Falls die Anzahl N = card(A) der Eingabewerte größer
als Q ist, müssen N-Q Eingabewerte redundant sein und auf Werte abbilden, die schon von
KQ erreicht wurden.
Für N = Q = M gilt: f = KQ.
Da KQ immer existiert, können wir nun jede Funktion basierend auf
ihrer charakteristischen Kernfunktion KQ darstellen.
Satz (2)
Jede Funktion f kann als Kombination einer Mappingfunktion qa und
der Kernfunktion KQ ausgedrückt werden.
Beweis (2)
Aus Satz (1) wissen wir, dass jede Funktion f: A
B eine Kernfunktion KQ mit Q = card(B) enthält.
Wir bestimmen zwei neue Mengen Aq und Bq für die
Abbildung KQ: Aq
Bq.
Es gelte: Bq = B und Aq
A.
Wir schließen die Lücke zwischen A und Aq mit einer
Mappingfunktion qa: A
Aq.
Die Funktion f lässt sich dann im -Kalkül
schreiben als f = x . KQ ( qa x ).
Im Fall card(A) = Q müssen wir nur qa = I (Identität) setzen.
Prüfung:
f = x . KQ ( qa x )
= x . KQ ( I x )
= x . KQ x = KQ.
Im Fall card(A) > Q müssen wir qa so wählen, dass jene
Q Elemente aus A, die KQ bilden, direkt auf Aq
gemappt werden.
Die redundanten Eingangswerte bleiben übrig und werden so auf Aq
gemappt, dass sich nach Durchlauf durch KQ der gleiche Ergebniswert ergibt
als hätte man direkt in B abgebildet.
Man mappt quasi die redundanten Eingangswerte auf einen Repräsentanten in
Aq.
Dieses Mapping ist immer ohne Probleme möglich.
In Beweis (2) haben wir Bq = B festgelegt.
Dies hätten wir auch anders machen können.
Indem wir eine weitere Mappingfunktionen qb:
Bq B
einführen und qb = I setzen, erhalten wir dasselbe Ergebnis.
Wir können dies wieder verallgemeinern und damit dann die Kernfunktion
KQ: Aq
Bq durch die Identitätsfunktion
IQ: {1,2,...,Q} {1,2,...,Q} ersetzen.
Die Aufgabe von IQ ist es einfach gesagt, das Intervall 1,2,...,Q der
natürlichen Zahlen auf sich selbst abzubilden.
Je nach Wert von Q ergibt sich eine andere Identitätsfunktion
I1 , I2 , I3 , ...
Satz (3)
Jede Funktion f kann als Kombination von zwei Mappingfunktionen qa und
qb und einer für f charakteristischen Identitätsfunktion IQ
ausgedrückt werden.
Beweis (3)
Im Beweis (2) haben wir eine Funktion f als
f = x . KQ ( qa x )
geschrieben.
Nun wandeln wir diesen Ausdruck leicht ab in
f = x . q'b ( KQ ( q'a x ) )
und denken uns q'b = I und q'a = qa.
Wir sehen, dass sich dadurch die Aussage nicht ändert.
Da KQ eine eineindeutige Abbildung vermittelt, ist KQ: Aq
Bq isomorph zu
IQ: {1,2,...,Q} {1,2,...,Q}.
Es sei IQ die Identitätsmatrix der Größe Q.
Wir nutzen für die isomorphe Abbildung wiederum zwei Mappingfunktionen
ma: Aq
{1,2,...,Q} und mb: {1,2,...,Q}
Bq.
Damit schreiben wir den Ausdruck für f nun als
f = x . q'b ( mb ( IQ ( ma ( q'a x ) ) ) ).
Es macht keinen großen Sinn zwei Mappingfunktionen hintereinanderzuschalten, wenn eine
Mappingfunktion dieselbe Abbildung leisten kann.
Wir definieren qb =
x .( q'b ( mb x ) ) und
qa = x .( ma
( q'a x ) ) und haben damit dann
f = x . qb ( IQ ( qa x ) ).
In Beweis (3) konnten wir nachweisen, dass in jede Funktion f eine Identitätsfunktion
IQ mit Q = card(B) einbettbar ist.
Die Identitätsfunktion bzw. die Zahl Q ist dabei ein wichtiges Klassifikationsmerkmal.
Man kann die Beziehungen, die
f = x . qb ( IQ ( qa x ) )
ausdrückt auch grafisch darstellen.
Man erkennt sehr schön in der Grafik, dass es zwei Wege gibt, wie man A auf
B abbilden kann.
Nun sind wir an einem Punkt wo wir unsere Überlegungen auf die Zusammenhänge zwischen
zwei beliebigen Funktionen f1 und f2 ausdehnen können.
Es seien dabei folgende Abbildungen gemeint:
f1: A1 B1 und
f2: A2 B2.
Die Kardinalitäten erfassen wir mit:
N1 = card(A1),
N2 = card(A2),
M1 = card(B1) und
M2 = card(B2).
Es gelten die Bedingungen:
N1 >= M1 und N2 >= M2.
Die Identitätsfunktionen seien:
IQ1 mit Q1 = M1 und
IQ2 mit Q2 = M2.
Wir bilden jetzt Äquivalenzklassen über die Differenzen N1-N2
und M1-M2.
Damit können wir Funktionen miteinander vergleichen.
Die Idee, die dahinter steckt ist folgende: Es ist unwichtig wie groß die
Matrizen sind.
Wichtig ist nur um wieviele Zeilen oder Spalten sie sich voneinander unterscheiden.
Beispiele
N1 |
M1 |
N2 |
M2 |
N1-N2 |
M1-M2 |
5 |
4 |
5 |
4 |
0 |
0 |
12 |
12 |
12 |
12 |
0 |
0 |
6 |
4 |
3 |
3 |
3 |
1 |
8 |
6 |
5 |
5 |
3 |
1 |
12 |
12 |
10 |
8 |
2 |
4 |
Die Differenzen N1-N2 und M1-M2
lassen sich in ein 2-dimensionales Koordinatensystem eintragen.
Damit werden die Beziehungen wesentlich anschaulicher.
Da wir immer die Mächtigkeiten von f2 abziehen ist f2
unser Bezugssystem.
Der Koordinatenursprung drückt somit die Identität zu f2 aus,
d.h. alle Funktionen, die gleich große Matrizen zu f2 haben kommen
im Punkt (0;0) zu liegen.
Wenn f2 eine patentierte Funktion ist, können wir sagen, dass jede
Funktion f1, wenn sie auf (0;0) abgebildet wird, eine Patentverletzung
von f2 darstellt.
Beweis (4)
N1-N2=0 und M1-M2=0 bedeutet
gleich große Matrizen.
Die Identitätsmatrizen haben die gleiche Größe wegen
Q1=M1=M2=Q2.
Es gibt auch gleich viele redundante Eingangswerte wegen
N1-M1=N2-M2.
Umgeformt:
N1-N2=M1-M2, also 0=0.
Damit existiert ein eineindeutiges Mapping zwischen den beiden Funktionen.
f1 x kann als qb ( f2 ( qa x ) )
dargestellt werden.
Wir zeigen nun, dass alle Funktionen f1 mit M1-M2=0
und N1-N2>0 eine Patentverletzung von f2 darstellen.
Beweis (5)
M1-M2=0 bedeutet gleich große Identitätsmatrizen
wegen Q1=M1=M2=Q2.
Da N1-N2>0 sein soll, bedeutet dies, dass f1
mehr redundante Eingangswerte als f2 hat.
Redundante Eingangswerte lassen sich aber immer durch eine Mappingfunktion
auf einen Repräsentanten reduzieren, siehe Beweis (2).
Sei f'1 x' =
qb ( f2 ( q'a x' ) ) eine Funktion wie unter
Beweis (4) welche in (0;0) zu liegen kommt.
Mit einer Mappingfunktion ma bilden wir die redundanten Werte x auf
ihre Repräsentanten in x' ab.
Also: x' = ma x und somit f1 x =
qb ( f2 ( q'a ( ma x ) ) ).
Da man zwei Mappingfunktionen zu einer vereinigen kann, können wir mit
qa x = q'a ( ma x ) auch wieder
f1 x = qb ( f2 ( qa x ) )
schreiben.
Wenden wir den Beweis (5) umgekehrt an, können wir sagen, dass wir von
f2 aus durch Hinzufügen von redundanten Eingangswerten jede
Funktion auf der Achse N1-N2>=0 erreichen können.
Aus der Sicht der Matrizen bedeutet dies ein Hinzufügen von Zeilen.
Wir können aber auch Spalten hinzufügen und es ergibt sich eine neue Achse.
Auch hier zeigen wir, dass alle Funktionen f1, die auf
dieser Achse liegen eine Patentverletzung von f2 darstellen.
Beweis (6)
Wir beweisen konstruktiv, indem wir von f2 ausgehen.
Beim Hinzufügen von Spalten müssen wir beachten, dass wir das nicht unabhängig
von den Zeilen tun können.
Da wir nur Funktionen zugelassen haben, erzwingt jede neue Spalte auch eine neue Zeile.
Wäre dies nicht so, gäbe es mehrere Ausgangswerte und das ist dann keine
Funktion mehr.
Wir wandern somit auf einer 45°-Achse.
Damit ist eigentlich schon alles bewiesen.
Da wir von f2 ausgingen ist f2 auch nach dem Hinzufügen
weiterhin in der neuen Matrix als Untermatrix enthalten.
Da f2 nicht alle Werte von
f1 berechnen kann, können wir dies mit einer anderen Funktion
f3 und einer Fallunterscheidung tun.
f1 x kann z.B. einfach als
qb ( ( if ( zusatz x ) f3 f2 ) ( qa x ) )
dargestellt werden, mit if = p x y . p x y
und zusatz als Funktion, die
true = x y . x
dann liefert, wenn x ein neuer hinzugefügter Wert ist und sonst
false = x y . y.
Dies wählt dann entweder die Funktion f3 oder f2
zur weiteren Berechnung aus.
Da eine 45°-Achse für die weitere Fallunterscheidung nicht sehr anschaulich
ist, ändern wir unser Koordinatensystem ein wenig ab.
Wir können eine Koordinatentransformation machen, indem wir einfach
N1-N2 subtrahieren, d.h. unsere waagerechte Achse sei nun
(M1-M2)-(N1-N2).
Damit sind Änderungen an den Matrizen bzgl. Spalten- oder Zeilenzahl ein
Wandern parallel zu den Achsen.
Die Ergebnisse von Beweis (5) und (6) lassen sich kombinieren.
Eine beliebige Funktion f1 ist erreichbar, wenn man von (0;0) ausgeht und
auf der waagerechten Achse solange nach rechts läuft bis man denselben
Koordinatenwert erreicht hat.
Dann läuft man auf der vertikalen Achse nach oben bis man auch hier denselben
Koordinatenwert erreicht hat.
Damit kann nun der ganze erste Quadrant erreicht werden.
Wir leiten nun die Patentverletzung für den zweiten Quadranten ab.
Dies ist etwas schwieriger, da f1 weniger Tupel als f2 besitzt.
Da man aber davon ausgehen darf, dass innerhalb von f1
eine Berechnung über mehr Tupel gemacht werden kann und nur nach aussen weniger
sichtbar sind bzw. genutzt werden, dann ist das folgende sofort einsichtig.
Beweis (7)
Eine Funktion f1, die im zweiten Quadranten zu liegen kommt, hat
weniger Tupel als die einzubettende Funktion f2.
Wir erzeugen nun eine Funktion f3, die wir aus f1 gewinnen,
in dem wir weitere Tupel hinzufügen.
Dies bedeutet eine waagerechte Verschiebung nach rechts, was wir solange tun, bis
wir auf die vertikale Achse N1-N2 treffen.
Diese Position ist bestimmt durch
(M1-M2)-(N1-N2)=0 bzw.
(M1-M2)=(N1-N2).
Aus Beweis (5) wissen wir, dass eine Funktion, die auf dieser Achse liegt eine
Patentverletzung von f2 darstellt.
Diese Funktion hat auch genug Tupel, um f2 total zu überdecken.
Wir betten f3 nun in f1 ein.
Dies ist kein Kunstgriff, wie wir in der Analyse von Aussage b) gesehen haben,
sondern aktuelle Praxis.
Dort hatten wir eine Funktion mit nur 2 Tupeln mit Funktionen beschrieben,
die über ganz definiert waren.
Aufgrund von Beweis (6) muss man alle Funktionen, die durch
Rechtsverschieben erzeugt wurden als Ableitung ansehen.
Die Funktion f3
ist somit Ableitung sowohl von f1 als auch von f2.
Es kann deshalb von beiden Seiten eine Patentverletzung angemahnt
werden.
Damit haben wir eine Überdeckung der ersten beiden Quadranten nachgewiesen.
Die Patentverletzung haben wir für f1 in Bezug auf f2 gezeigt.
Man kann aber auch den Bezugspunkt wechseln und die Patentverletzung
für f2 in Bezug auf f1 betrachten.
Tun wir dies, dann ändert sich die Beschriftung der Achsen, da nun
N2-N1 und (M2-M1)-(N2-N1)
berechnet werden.
Formt man diese Terme um in -(N1-N2) und
-(M1-M2)+(N1-N2), also
-((M1-M2)-(N1-N2)), sieht man,
dass nur ein Vorzeichenwechsel stattfindet.
Wenn man für einen beliebigen Punkt in diesem Koordinatensystem das
Vorzeichen beider Achsen wechselt, so ist das gleichbedeutend mit einer
Hintereinanderausführung von Spiegelungen an beiden Achsen bzw. einer
Punktspiegelung am Koordinatenursprung.
Die obere Halbebene klappt dadurch komplett auf die untere Halbebene um.
Es kann so die gesamte Fläche überdeckt werden.
Wir müssen folgern, dass der Anspruchsbereich von Aussage c) vollkommen
überzogen ist. Durch die Wandelbarkeit von Funktionen kann fast jede
beliebige Patentverletzung erzielt werden.
Aussage c) muss in Bezug auf Software als ungültig erklärt werden.
d) Es gibt noch genug freie Funktionen und Programme, sodass die Menge
der patentierten Funktionen nicht stark störend wirkt.
Nach dem Ergebnis von Aussage c) kann Aussage d) nicht mehr aufrechterhalten werden.
Softwarepatente stellen eine starke Störung dar und es gibt keine
Ausweichmöglichkeiten.
Aussage d) ist somit falsch.
Wir konnten zeigen, dass zwischen zwei Funktionen immer eine
Patentverletzungs-Situation herrscht.
Wenn man dies auf mehr als zwei Funktionen ausdehnt, kann man sagen, dass hierbei immer
die trivialste Funktion gewinnt, da sie stets als in den komplexeren Funktionen enthalten
angegeben werden kann, während dies umgekehrt nicht immer gilt.
Dies zeigt nun aber ganz konkret wie gefährlich Trivialpatente sind.
Da wir nachgewiesen haben, dass eine Patentverletzung immer vorliegt, ist
die Bedrohung durch Softwarepatente nicht mehr hypothetisch.
Jeder, der sich Programmierer oder Informatiker nennt, kann hiernach
nicht mehr ruhigen Gewissens dem Spiel der Patentlobby zusehen.
Auch, wer glaubt, dass ihm eigene Patente einen Vorteil verschaffen, muss
nun einsehen, dass dies im Bereich der Software nicht möglich ist.
Praktisch jedes Softwareprojekt ist ständig der Gefahr einer Patentverletzung
ausgesetzt. Es ist nur eine Frage von Zeit und Geld, die man investieren möchte,
um eine Patentverletzung zu konstruieren.
|