dobrze uformowane obiektyedit

Jeśli zbiór obiektów (symboli i sekwencji symboli) ma być uważany za „dobrze uformowany”, musi istnieć algorytm, aby określić, zatrzymując odpowiedź „Tak” lub „nie”, czy obiekt jest dobrze uformowany (w matematyce wff skraca dobrze uformowaną formułę). Algorytm ten, w skrajności, może wymagać (lub być) maszyny Turinga lub równoważnej maszyny Turinga, która „parsuje” ciąg symboli przedstawiony jako” dane ” na jego taśmie; zanim uniwersalna maszyna Turinga może wykonać instrukcję na swojej taśmie, musi przeanalizować symbole, aby określić dokładną naturę instrukcji i / lub danych tam zakodowanych. W prostszych przypadkach skończona maszyna stanu lub automat pushdown może wykonać zadanie. Enderton opisuje użycie „drzew” do określenia, czy formuła logiczna (w szczególności ciąg symboli z nawiasami) jest dobrze uformowana. Kościół Alonzo 1934 opisuje budowę ” formuł „(ponownie: ciągi symboli), jak zapisał w swoim rachunku λ za pomocą rekurencyjnego opisu, jak rozpocząć formułę, a następnie zbudować na symbolu startowym za pomocą konkatenacji i podstawienia.

przykład: Church określił swój λ-rachunek w następujący sposób (poniżej jest uproszczona wersja pomijająca pojęcia zmiennej swobodnej i związanej). Ten przykład pokazuje, jak teoria obiektu zaczyna się od specyfikacji obiektowego systemu symboli i relacji (w szczególności za pomocą konkatenacji symboli):

(1) deklaruj symbole: {,}, (,), λ, plus nieskończoną liczbę zmiennych a, b, c, …, x,.. (2) Zdefiniuj formułę: ciąg symboli (3) Zdefiniuj pojęcie „dobrze uformowanej formuły” (wff) rekurencyjnie zaczynając od „podstawy” (3.i):

• (3.1) (podstawa) zmienna x jest wff
• (3.2) Jeśli F I X są wffs, to {F} (X) jest WFF; jeśli X występuje w F lub X, to mówi się, że jest zmienną w {F} (X).
• (3.3) jeśli M jest dobrze uformowane, a x występuje w M, to λx jest wff.

(4) Definiowanie różnych skrótów:

• {f} skraca się do F(X), jeśli F jest pojedynczym symbolem
• f {\displaystyle {{f}}}
  

  skraca się do {F}(X,Y) lub F(X, Y), jeśli F jest pojedynczym symbolem

• λx1λx2…] skraca się do λx1x2…xn•m
• λab•A(B) skraca się do 1
• λab * A(A(b)) skraca się do 2, itd.

(5) Zdefiniuj pojęcie „substytucji” formula_1 dla zmiennej x w całym M (Church 1936)

Undefined (primitive) objectsEdit

niektóre obiekty mogą być „niezdefiniowane” lub „prymitywne” i otrzymać definicję (w kategoriach ich zachowań) poprzez wprowadzenie aksjomatów.

w następnym przykładzie niezdefiniowanymi symbolami będą { ※ ,ↀ,}}. Aksjomaty opisują ich zachowania.

Aksjomatyedit

Kleene zauważa, że aksjomaty składają się z dwóch zestawów symboli: (i) nieokreślonych lub prymitywnych obiektów oraz tych, które są wcześniej znane. W poniższym przykładzie w następującym systemie (o,※,ↀ,∫) wcześniej wiadomo, że O jest zbiorem obiektów („domena”), ※ jest obiektem w domenie, ↀ i ∫ są symbolami relacji między obiektami, => określa operator logiczny „jeśli wtedy”, ε jest symbolem wskazującym „jest elementem zbioru O”, A „n” zostanie użyty do oznaczenia dowolnego elementu zbioru obiektów O.

Po (i) określenie „ciąg”—obiekt, który jest symbolem ※ dodatkowych znaków ※,ↀ, lub ∫ i (II) określenia „dobrze to opis generowany” struny — (podstawa) ※ i ↀS, ∫s, gdzie S-dowolny ciąg znaków, przyjdź aksjomaty:

• ↀ※ => i ※ w słowa: „Jeśli ↀ stosuje się do obiektu ※ po obiektu wyniki※.”
• ∫n ε o, w słowach „jeśli ∫ jest zastosowane do dowolnego obiektu” N „W O to ten obiekt ∫N jest elementem O”.
• ↀn ε O, „jeśli ↀ jest zastosowane do dowolnego obiektu” n „W O to ten obiekt ↀn jest elementem O”.
• ↀ ∫ n = > n, „jeśli obiekt ∫ zostanie zastosowany do obiektu ∫ n, to wynik obiektu N.”
• ∫ ↀn => n, ” jeśli obiekt ↀ zostanie zastosowany do obiektu ↀn, to wynik obiektu N.”

jaka zatem może być (zamierzona) interpretacja tych symboli, definicji i aksjomatów?

jeśli zdefiniujemy ※ jako „0”, ∫ jako „następca”, a ↀ jako” poprzednik”, to ↀ ※ = ※ wskazuje” prawidłowe odejmowanie „(czasami oznaczone symbolem∸, gdzie” poprzednik ” odejmuje jednostkę od liczby, a zatem 0 ∸1 = 0). Ciąg znaków ” ↀ ∫ n => n ” wskazuje, że jeśli najpierw następnik zostanie zastosowany do dowolnego obiektu n, a następnie poprzednik ↀ zostanie zastosowany do ∫ n, oryginalne n wyniki.”

czy ten zbiór aksjomatów jest „odpowiedni”? Właściwą odpowiedzią byłoby pytanie: „adekwatne do opisania, co w szczególności?””Aksjomaty określają, do których układów, zdefiniowanych poza teorią, stosuje się teorię.”(Kleene 1952:27). Innymi słowy, aksjomaty mogą być wystarczające dla jednego systemu, ale nie dla innego.

w rzeczywistości łatwo zauważyć, że ten zbiór aksjomatów nie jest zbyt dobry—w rzeczywistości jest niespójny (to znaczy daje niespójne wyniki, bez względu na jego interpretację):

przykład: Zdefiniuj ※ jako 0, ∫ ※ jako 1 i ↀ1 = 0. Od pierwszego aksjomatu, ↀ ※ = 0, więc ∫ ↀ ※ = 0 0 = 1. Ale ostatni aksjomat określa, że dla dowolnego N, w tym ※ = 0, ∫ ↀn => n, więc ten aksjomat określa, że ∫ ↀ0 => 0, a nie 1.

zauważ również, że zbiór aksjomatów nie określa, że ∫n ≠ N. Lub, z wyjątkiem przypadku n=※, ↀn ≠ N. gdybyśmy mieli uwzględnić te dwa aksjomaty, musielibyśmy opisać intuicyjne pojęcia „równi” symbolizowani przez=, a nie-równi symbolizowani przez ≠.