Articles

Objekttheorie

by admin

Wohlgeformte Objektebearbeiten

Wenn eine Sammlung von Objekten (Symbolen und Symbolsequenzen) als „wohlgeformt“ betrachtet werden soll, muss ein Algorithmus vorhanden sein, um durch Anhalten mit einer „Ja“ – oder „Nein“ -Antwort festzustellen, ob das Objekt wohlgeformt ist oder nicht (in der Mathematik a wff abkürzt wohlgeformte Formel). Dieser Algorithmus könnte im Extremfall eine Turing-Maschine oder eine Turing-äquivalente Maschine erfordern (oder sein), die die Symbolzeichenfolge „analysiert“, sobald sie als „Daten“ auf ihrem Band dargestellt wird; bevor eine universelle Turingmaschine eine Anweisung auf ihrem Band ausführen kann, muss sie die Symbole analysieren, um die genaue Art der Anweisung und / oder des dort codierten Datums zu bestimmen. In einfacheren Fällen kann eine Finite-State-Maschine oder ein Pushdown-Automat die Arbeit erledigen. Enderton beschreibt die Verwendung von „Bäumen“, um zu bestimmen, ob eine logische Formel (insbesondere eine Zeichenfolge mit Klammern) gut geformt ist oder nicht. Alonzo Kirche 1934 beschreibt die Konstruktion von „Formeln“ (wieder: Symbolsequenzen), wie in seinem λ-Kalkül unter Verwendung einer rekursiven Beschreibung des Startens einer Formel und des anschließenden Aufbaus des Startsymbols unter Verwendung von Verkettung und Substitution geschrieben.

Beispiel: Church spezifizierte seinen λ-Kalkül wie folgt (das Folgende ist eine vereinfachte Version, wobei Begriffe von freien und gebundenen Variablen weggelassen werden). Dieses Beispiel zeigt, wie eine Objekttheorie mit einer Spezifikation eines Objektsystems von Symbolen und Beziehungen beginnt (insbesondere durch Verkettung von Symbolen):

(1) Deklarieren Sie die Symbole: {, }, (, ), λ plus eine unendliche Anzahl von Variablen a, b, c, …, x, … (2) Formel definieren: eine Folge von Symbolen (3) Definieren Sie den Begriff der „wohlgeformten Formel“ (wff) rekursiv beginnend mit der „Basis“ (3.i):

  • (3.1) (Basis) Eine Variable x ist ein wff
  • (3.2) Wenn F und X wffs sind, dann ist {F}(X) ein wff; Wenn x in F oder X vorkommt, dann wird gesagt, dass es eine Variable in {F}(X) ist.
  • (3.3) Wenn M wohlgeformt ist und x in M vorkommt, dann ist λx ein wff.

(4) Definieren Sie verschiedene Abkürzungen:

  • {F} steht für F(X), wenn F ein einzelnes Symbol ist
  • F {\displaystyle {{F}}}
    {{F}}

    steht für {F}(X,Y) oder F(X,Y), wenn F ein einzelnes Symbol ist

  • λx1λx2…] steht für λx1x2…xn•M
  • λab•a(b) steht für 1
  • λab•a(a(b)) steht für 2 usw.

(5) Definieren Sie den Begriff der „Substitution“ der Formel N für die Variable x in M (Church 1936)

Undefinierte (primitive) Objektebearbeiten

Bestimmte Objekte können „undefiniert“ oder „primitiv“ sein und erhalten durch die Einführung der Axiome eine Definition (in Bezug auf ihr Verhalten).

Im nächsten Beispiel sind die undefinierten Symbole { ※, ↀ, ∫ } . Die Axiome beschreiben ihr Verhalten.

AxiomsEdit

Kleene beobachtet, dass die Axiome aus zwei Sätzen von Symbolen bestehen: (i) den undefinierten oder primitiven Objekten und denen, die zuvor bekannt waren. Im folgenden Beispiel ist im folgenden System (O, ※, ↀ, ∫) zuvor bekannt, dass O eine Menge von Objekten (die „Domäne“) darstellt, ※ ein Objekt in der Domäne ist, ↀ und ∫ Symbole für Beziehungen zwischen den Objekten sind, => gibt den logischen Operator „WENN DANN“ an, ε ist das Symbol, das angibt, „ist ein Element der Menge O“, und „n“ wird verwendet, um ein beliebiges Element der Objektmenge O anzuzeigen.

Nach (i) eine definition von „string-S“—ein Objekt, ein symbol ※ oder verketteten Symbole ※, ↀ oder ∫, und (ii) eine definition von „well-formed“ strings — (basis) ※ und ↀS, ∫S, wobei S ist eine beliebige Zeichenfolge, kommen die Axiome:

  • ↀ※ => ※, in Worten: „WENN ↀ angewendet Objekt ※ DANN Objekt ※ Ergebnisse.“
  • ∫n ε O, in Worten „WENN ∫ auf ein beliebiges Objekt „n“ in O angewendet wird, DANN ist dieses Objekt ∫n ein Element von O“.
  • ↀn ε O, „WENN ↀ auf ein beliebiges Objekt „n“ in O angewendet wird, DANN ist dieses Objekt ↀn ein Element von O“.
  • ↀ∫n => n, „WENN ↀ auf Objekt ∫n angewendet wird, ergibt sich Objekt n.“
  • ∫ↀn => n, „WENN ∫ auf Objekt ↀn angewendet wird, ergibt sich Objekt n.“

Was könnte also die (beabsichtigte) Interpretation dieser Symbole, Definitionen und Axiome sein?

Wenn wir ※ als „0“, ∫ als „Nachfolger“ und ↀ als „Vorgänger“ definieren, dann bedeutet ↀ※ => ※ „richtige Subtraktion“ (manchmal mit dem Symbol ∸ bezeichnet, wobei „Vorgänger“ eine Einheit von einer Zahl subtrahiert, also 0 ∸1 = 0). Die Zeichenfolge “ ↀ∫n => n “ zeigt an, dass, wenn zuerst der Nachfolger auf ein beliebiges Objekt n und dann der Vorgänger ↀ auf ∫n angewendet wird, das ursprüngliche n resultiert.“

Ist dieser Satz von Axiomen „angemessen“? Die richtige Antwort wäre eine Frage: „Angemessen zu beschreiben, was insbesondere?“Die Axiome bestimmen, auf welche von außerhalb der Theorie definierten Systeme die Theorie zutrifft.“ (Kleene 1952:27). Mit anderen Worten, die Axiome können für ein System ausreichend sein, aber nicht für ein anderes.

Tatsächlich ist es leicht zu erkennen, dass diese Axiommenge nicht sehr gut ist — tatsächlich ist sie inkonsistent (dh sie liefert inkonsistente Ergebnisse, unabhängig von ihrer Interpretation):

Beispiel: Definieren Sie ※ als 0, ∫※ als 1 und ↀ1 = 0. Aus dem ersten Axiom ↀ※ = 0, also ∫ↀ※ = ∫0 = 1. Aber das letzte Axiom gibt an, dass für jedes beliebige n einschließlich ※ = 0, ∫ↀn => n , so dass dieses Axiom festlegt, dass ∫ↀ0 => 0, nicht 1.

Beachten Sie auch, dass die Axiommenge nicht angibt, dass ∫n ≠ n. Oder, mit Ausnahme des Falles n = ※, ↀn ≠ n. Wenn wir diese beiden Axiome einschließen würden, müssten wir die intuitiven Begriffe „gleich“, symbolisiert durch = und nicht-gleich, symbolisiert durch ≠, beschreiben.