Information: Software-Patente unter der Lupe

[ Zurück ]

Software-Patente unter der Lupe

Kommentare sind sehr erwünscht. Bitte an obige E-Mail-Adresse.

deutsch english

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

1 Teile und herrsche

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 heissen (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 schützt auch die Ableitung einer Idee bzw. die Ableitung der Realisierung einer Idee.
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 schützt auch die Ableitung einer Funktion bzw. die Ableitung des Programmes zu einer Funktion.

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.

2 Mathematische Grundlagen

In der Mathematik leitet man Relationen aus der Mengenlehre ab. Kommt es auf die Reihenfolge zweier Elemente x₁ , x₂ an, so wird der Begriff des geordneten Paares oder 2-Tupel ( x₁ , x₂ ) verwendet. Eine mengentheoretische Definition des geordneten Paares wäre folgende:

Definition (1)

( x₁ , x₂ ) { x₁ , x₂ } wegen { x₁ , x₂ } = { x₂ , x₁ }
aber:
( x₁ , x₂ ) := { { x₁ } , { x₁ , x₂ } }

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)

M₁ ... M_n := { ( x₁ , ... , x_n ) | x_i M_i } heißt karthesisches Produkt der Mengen M₁ , ... , M_n.
Die Menge M₁ M₂ := { ( x₁ , x₂ ) | x₁ M₁ x₂ M₂ } heißt auch Paarmenge.

Definition (3)

Jede Teilmenge R M₁ ... M_n 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.

3 Turing-Maschinen und -Kalkül

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.

4 Beweise über Software

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.

5 Analysen

5.1 Analyse von Aussage a)

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 = { a₁ , ... , a_n } dem eine alphabetische Ordnung a₁ < a₂ < ... < a_n zugrunde liegt, dann ist bekanntlich A^* die Menge aller Texte bzw. Wörter über A:

A^* = { , a₁ , ... , a_n , a₁a₁ , a₁a₂ , ... , a₄a₁a₆a₂a₁ , ... }

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 n^m verschiedene Wörter über A (also endlich viele); dann sortiert man noch innerhalb der Wörter gleicher Länge lexikographisch, also bei b₁b₂ ... b_m < c₁c₂ ... c_m gilt b₁ < c₁ (b₁ = c₁ b₂ < c₂) ... (b₁ = c₁ ... b_m-1 = c_m-1 b_m < c_m). 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 M_f derjenigen Zahlen m , für die f(m) = 1 ist. Umgekehrt gibt es für jede Teilmenge M eine solche Funktion f_M, 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.

5.2 Analyse von Aussage b)

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) = x² - 2x + 1

Betrachten wir nun drei spezielle Funktionen f₁, f₂ und f₃:

f₁(x) = { 0 für x=0 und 1 für x=1
f₂(x) = x
f₃(x) = x²

f₁ besteht aus zwei 2-Tupeln, d.h. der Definitionsbereich und der Wertebereich sind nur für 2 Werte definiert. Im Gegensatz dazu seien f₂ und f₃ über ganz definiert. Wenn wir nun festlegen, dass für unsere Rechnungen bei allen drei Funktionen nur der Definitionsbereich { 0 , 1 } verwendet werden soll (oder kann), 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 x² ebenfalls gleichwertige Algorithmen zur Berechnung von f₁ darstellen und man kann sagen, dass f₂ und f₃ Ableitungen von f₁ sind, da sie f₁ 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. f₃(x) = x² 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.

5.3 Analyse von Aussage c)

c) Ein Patent schützt auch die Ableitung einer Funktion bzw. die Ableitung des Programmes zu einer Funktion.

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: a₀ , a₁ , ... , a_N A und b₀ , b₁ , ... , b_M 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 b_i = f a_i und a_i = f^-1 b_i.

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 b_i = f a_i. 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 K_Q 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 K_Q (bzw. die quadratische Matrix K_Q) 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 K_Q erreicht wurden. Für N = Q = M gilt: f = K_Q.

Da K_Q immer existiert, können wir nun jede Funktion basierend auf ihrer charakteristischen Kernfunktion K_Q darstellen.

Satz (2)

Jede Funktion f kann als Kombination einer Mappingfunktion q_a und der Kernfunktion K_Q ausgedrückt werden.

Beweis (2)

Aus Satz (1) wissen wir, dass jede Funktion f: A B eine Kernfunktion K_Q mit Q = card(B) enthält. Wir bestimmen zwei neue Mengen A_q und B_q für die Abbildung K_Q: A_q B_q. Es gelte: B_q = B und A_q A. Wir schließen die Lücke zwischen A und A_q mit einer Mappingfunktion q_a: A A_q.

Die Funktion f lässt sich dann im -Kalkül schreiben als f = x . K_Q ( q_a x ).

Im Fall card(A) = Q müssen wir nur q_a = I (Identität) setzen.
Prüfung: f = x . K_Q ( q_a x ) = x . K_Q ( I x ) = x . K_Q x = K_Q.

Im Fall card(A) > Q müssen wir q_a so wählen, dass jene Q Elemente aus A, die K_Q bilden, direkt auf A_q gemappt werden. Die redundanten Eingangswerte bleiben übrig und werden so auf A_q gemappt, dass sich nach Durchlauf durch K_Q der gleiche Ergebniswert ergibt als hätte man direkt in B abgebildet. Man mappt quasi die redundanten Eingangswerte auf einen Repräsentanten in A_q. Dieses Mapping ist immer ohne Probleme möglich.

In Beweis (2) haben wir B_q = B festgelegt. Dies hätten wir auch anders machen können. Indem wir eine weitere Mappingfunktionen q_b: B_q B einführen und q_b = I setzen, erhalten wir dasselbe Ergebnis. Wir können dies wieder verallgemeinern und damit dann die Kernfunktion K_Q: A_q B_q durch die Identitätsfunktion I_Q: {1,2,...,Q} {1,2,...,Q} ersetzen. Die Aufgabe von I_Q 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 I₁ , I₂ , I₃ , ...

Satz (3)

Jede Funktion f kann als Kombination von zwei Mappingfunktionen q_a und q_b und einer für f charakteristischen Identitätsfunktion I_Q ausgedrückt werden.

Beweis (3)

Im Beweis (2) haben wir eine Funktion f als f = x . K_Q ( q_a x ) geschrieben. Nun wandeln wir diesen Ausdruck leicht ab in f = x . q'_b ( K_Q ( q'_a x ) ) und denken uns q'_b = I und q'_a = q_a. Wir sehen, dass sich dadurch die Aussage nicht ändert.
Da K_Q eine eineindeutige Abbildung vermittelt, ist K_Q: A_q B_q isomorph zu I_Q: {1,2,...,Q} {1,2,...,Q}. Es sei I_Q die Identitätsmatrix der Größe Q. Wir nutzen für die isomorphe Abbildung wiederum zwei Mappingfunktionen m_a: A_q {1,2,...,Q} und m_b: {1,2,...,Q} B_q. Damit schreiben wir den Ausdruck für f nun als f = x . q'_b ( m_b ( I_Q ( m_a ( q'_a x ) ) ) ). Es macht keinen großen Sinn zwei Mappingfunktionen hintereinanderzuschalten, wenn eine Mappingfunktion dieselbe Abbildung leisten kann. Wir definieren q_b = x .( q'_b ( m_b x ) ) und q_a = x .( m_a ( q'_a x ) ) und haben damit dann f = x . q_b ( I_Q ( q_a x ) ).

In Beweis (3) konnten wir nachweisen, dass in jede Funktion f eine Identitätsfunktion I_Q 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 . q_b ( I_Q ( q_a x ) ) ausdrückt auch grafisch darstellen.

Nun sind wir an einem Punkt wo wir unsere Überlegungen auf die Zusammenhänge zwischen zwei beliebigen Funktionen f₁ und f₂ ausdehnen können.
Es seien dabei folgende Abbildungen gemeint:
f₁: A₁ B₁ und f₂: A₂ B₂.
Die Kardinalitäten erfassen wir mit:
N₁ = card(A₁), N₂ = card(A₂), M₁ = card(B₁) und M₂ = card(B₂).
Es gelten die Bedingungen:
N₁ >= M₁ und N₂ >= M₂.
Die Identitätsfunktionen seien:
I_Q1 mit Q₁ = M₁ und I_Q2 mit Q₂ = M₂.

Wir bilden jetzt Äquivalenzklassen über die Differenzen N₁-N₂ und M₁-M₂. 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

N₁ M₁ N₂ M₂ N₁-N₂ M₁-M₂

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 N₁-N₂ und M₁-M₂ lassen sich in ein 2-dimensionales Koordinatensystem eintragen. Damit werden die Beziehungen wesentlich anschaulicher. Da wir immer die Mächtigkeiten von f₂ abziehen ist f₂ unser Bezugssystem. Der Koordinatenursprung drückt somit die Identität zu f₂ aus, d.h. alle Funktionen, die gleich große Matrizen zu f₂ haben kommen im Punkt (0;0) zu liegen.

Wenn f₂ eine patentierte Funktion ist, können wir sagen, dass jede Funktion f₁, wenn sie auf (0;0) abgebildet wird, eine Patentverletzung von f₂ darstellt.

Beweis (4)

N₁-N₂=0 und M₁-M₂=0 bedeutet gleich große Matrizen. Die Identitätsmatrizen haben die gleiche Größe wegen Q₁=M₁=M₂=Q₂. Es gibt auch gleich viele redundante Eingangswerte wegen N₁-M₁=N₂-M₂. Umgeformt: N₁-N₂=M₁-M₂, also 0=0. Damit existiert ein eineindeutiges Mapping zwischen den beiden Funktionen. f₁ x kann als q_b ( f₂ ( q_a x ) ) dargestellt werden. qed

Wir zeigen nun, dass alle Funktionen f₁ mit M₁-M₂=0 und N₁-N₂>0 eine Patentverletzung von f₂ darstellen.

Beweis (5)

M₁-M₂=0 bedeutet gleich große Identitätsmatrizen wegen Q₁=M₁=M₂=Q₂. Da N₁-N₂>0 sein soll, bedeutet dies, dass f₁ mehr redundante Eingangswerte als f₂ hat. Redundante Eingangswerte lassen sich aber immer durch eine Mappingfunktion auf einen Repräsentanten reduzieren, siehe Beweis (2). Sei f'₁ x' = q_b ( f₂ ( q'_a x' ) ) eine Funktion wie unter Beweis (4) welche in (0;0) zu liegen kommt. Mit einer Mappingfunktion m_a bilden wir die redundanten Werte x auf ihre Repräsentanten in x' ab. Also: x' = m_a x und somit f₁ x = q_b ( f₂ ( q'_a ( m_a x ) ) ). Da man zwei Mappingfunktionen zu einer vereinigen kann, können wir mit q_a x = q'_a ( m_a x ) auch wieder f₁ x = q_b ( f₂ ( q_a x ) ) schreiben. qed

Wenden wir den Beweis (5) umgekehrt an, können wir sagen, dass wir von f₂ aus durch Hinzufügen von redundanten Eingangswerten jede Funktion auf der Achse N₁-N₂>=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 f₁, die auf dieser Achse liegen eine Patentverletzung von f₂ darstellen.

Beweis (6)

Wir beweisen konstruktiv, indem wir von f₂ 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 f₂ ausgingen ist f₂ auch nach dem Hinzufügen weiterhin in der neuen Matrix als Untermatrix enthalten. Da f₂ nicht alle Werte von f₁ berechnen kann, können wir dies mit einer anderen Funktion f₃ und einer Fallunterscheidung tun. f₁ x kann z.B. einfach als q_b ( ( if ( zusatz x ) f₃ f₂ ) ( q_a 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 f₃ oder f₂ zur weiteren Berechnung aus. qed

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 N₁-N₂ subtrahieren, d.h. unsere waagerechte Achse sei nun (M₁-M₂)-(N₁-N₂). 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 f₁ 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 f₁ weniger Tupel als f₂ besitzt. Da man aber davon ausgehen darf, dass innerhalb von f₁ 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 f₁, die im zweiten Quadranten zu liegen kommt, hat weniger Tupel als die einzubettende Funktion f₂. Wir erzeugen nun eine Funktion f₃, die wir aus f₁ 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 N₁-N₂ treffen. Diese Position ist bestimmt durch (M₁-M₂)-(N₁-N₂)=0 bzw. (M₁-M₂)=(N₁-N₂). Aus Beweis (5) wissen wir, dass eine Funktion, die auf dieser Achse liegt eine Patentverletzung von f₂ darstellt. Diese Funktion hat auch genug Tupel, um f₂ total zu überdecken. Wir betten f₃ nun in f₁ 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 f₃ ist somit Ableitung sowohl von f₁ als auch von f₂. Es kann deshalb von beiden Seiten eine Patentverletzung angemahnt werden. qed

Damit haben wir eine Überdeckung der ersten beiden Quadranten nachgewiesen. Die Patentverletzung haben wir für f₁ in Bezug auf f₂ gezeigt.

Man kann aber auch den Bezugspunkt wechseln und die Patentverletzung für f₂ in Bezug auf f₁ betrachten. Tun wir dies, dann ändert sich die Beschriftung der Achsen, da nun N₂-N₁ und (M₂-M₁)-(N₂-N₁) berechnet werden. Formt man diese Terme um in -(N₁-N₂) und -(M₁-M₂)+(N₁-N₂), also -((M₁-M₂)-(N₁-N₂)), 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 die Schutzanspüche von Aussage c) vollkommen überzogen sind. Aussage c) muss in Bezug auf Software als ungültig erklärt werden.

5.4 Analyse von Aussage d)

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.

6 Schlussfolgerung

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

7 Literatur

[BAR81] Barendregt, H.P.: The Lambda-Calculus - Its Syntax and Semantics. Amsterdam: North-Holland, 1981.

[BAR90] Barendregt, H.P.: Functional Programming and Lambda-Calculus. Siehe dort in [LEE90], pp. 321-363.

[CHU36] Church, Alonzo: An Unsolvable Problem of Elementary Number theory. American Journal of Mathematics 58, 354-363, 1936.

[CHU41] Church, Alonzo: The Calculi of Lambda Conversion. Princeton, NJ: Princeton University Press, 1941.

[DTV74] dtv-Atlas zur Mathematik: Grundlagen Algebra und Geometrie, Tafeln und Texte, Band 1, Deutscher Taschenbuch Verlag GmbH & Co. KG, München, 1974.

[ERD22] Erdmann, Karl Otto: Die Bedeutung des Wortes, Aufsätze aus dem Grenzgebiet der Sprachpsychologie und Logik, Leipzig, 1922

[ERW99] Erwig, Martin: Grundlagen funktionaler Programmierung / von Martin Erwig. - München; Wien: Oldenbourg, 1999, ISBN 3-486-25100-7

[HOP79] John E. Hopcroft, Jeffrey D. Ullman: Introduction to automata theory, languages and computation, Addison-Wesley, 1979, §8.4

[LEE90] van Leeuwen, J. (Ed.): Handbook of Theoretical Computer Science, Vol. B: Formal Methods and Semantics. Amsterdam: Elsevier Science Publishers, 1990.

[RIC53] Rice, H.G.: Classes of recursively enumerable sets and their decision problems, Trans. AMS. 89 (1953), 25-59

[RIC56] Rice, H.G.: On completely recursively enumerable classes and their key arrays, J. Symb. Logic 21 (1956), 304-341

[SOEUR] M.H.B. Sørensen, P. Urcykcyn: Lectures on the Curry Howard Isomorphism.

[TUR37] Turing, Alan M.: Computability and -Definability, Journal of Symbolic Logic 2, 1937.

[TUR87] Turing, Alan M.: Intelligence Service: Schr./Alan M. Turing. (Hrsg. v. Bernhard Dotzler u. Friedrich Kittler). Berlin: Brinkmann & Bose, 1987, ISBN 3-922660-22-3

[WRG86] Whitehead, Alfred North; Russell, Bertrand; Gödel, Kurt (1986): Principia Mathematica: Vorwort und Einleitungen / Alfred North Whitehead; Betrand Russell. Übers. von Hans Mokre. Mit einem Beitrag von Kurt Gödel. - 3. Aufl. - Frankfurt am Main : Suhrkamp, 1994 (Suhrkamp-Taschenbuch Wissenschaft ; 593) Einheitsacht.: Principia Mathematica <dt.> ISBN 3-518-28193-3

Kommentare sind sehr erwünscht. Bitte an obige E-Mail-Adresse.

[ Zurück ]