Bem-formado objectsEdit

Se uma coleção de objetos (símbolos e símbolo-sequências) é para ser considerada como “bem-formado”, um algoritmo deve existir para determinar, interrompendo com um “sim” ou “não” como resposta, independentemente de ser ou não o objeto é bem-formado (em matemática uma wff abrevia bem formado fórmula). Este algoritmo, no extremo, pode exigir (ou ser) uma máquina de Turing ou máquina Turing-equivalente que “analisa” a cadeia de símbolos como apresentada como “dados” em sua fita; antes que uma máquina de Turing universal possa executar uma instrução em sua fita, ela deve analisar os símbolos para determinar a natureza exata da instrução e/ou datum codificado lá. Em casos mais simples, uma máquina de estados finitos ou um autômato de pilha podem fazer o trabalho. Enderton descreve o uso de “árvores” para determinar se uma fórmula lógica (em particular uma cadeia de símbolos com parênteses) é bem formada. A Igreja de Alonzo 1934 descreve a construção de” fórmulas ” (novamente: sequências de símbolos) como escrito em seu cálculo λ pelo uso de uma descrição recursiva de como iniciar uma fórmula e, em seguida, construir sobre o símbolo inicial usando concatenação e substituição.

exemplo: Church especificou seu cálculo λ como segue (a seguinte é a versão simplificada deixando de fora noções de variável livre e limitada). Este exemplo mostra como uma teoria de objetos começa com uma especificação de um sistema de objetos de símbolos e relações (em particular pelo uso de concatenação de símbolos):

(1) declarar os símbolos: {, }, (, ), λ, Mais um número infinito de variáveis A, b, c, …, x, … (2) Define fórmula: uma sequência de símbolos (3) Define a noção de “fórmula bem formada” (wff) recursivamente começando com a “Base” (3.i):

• (3.1) (basis) a variable x is a wff
• (3.2) If F and X are wffs, then {F}(X) is a wff; if x occurs in F or X then it is said to be a variable in {F}(X).
• (3.3) se M é bem formado e x ocorre em M então λx é um wff.

(4) definir várias abreviaturas:

• {F} abrevia a F(X) se F é um símbolo único
• F {\displaystyle {{F}}}
  

  abrevia a {F}(X,Y) ou F(X,Y) se F é um símbolo único

• λx1λx2…] abreviatura de λx1x2…xn * M
• λab•A (b) abreviaturas de 1
• λab•a(A(b)) abreviaturas de 2, etc.

(5) Define a noção de “substituição” da fórmula N para a variável x toda M (Igreja de 1936)

Indefinido (primitiva) objectsEdit

Certos objetos podem ser “indefinido” ou “primitivos” e receber definição (nos termos de seus comportamentos) pela introdução dos axiomas.

no próximo exemplo, os símbolos indefinidos serão { ※ ,ↀ,}}. Os axiomas irão descrever os seus comportamentos.

AxiomsEdit

Kleene observa que os axiomas são compostos de dois conjuntos de símbolos: (i) os objetos indefinidos ou primitivos e aqueles que são anteriormente conhecidos. No exemplo a seguir, é previamente conhecido no seguinte sistema ( S ※, ↀ, ∫ ) que O constitui de um conjunto de objetos (“domínio”), ※ é um objeto no domínio, ↀ e ∫ são símbolos para as relações entre os objetos, => indica o “SE-ENTÃO” operador lógico, ε é o símbolo que indica “é um elemento do conjunto S”, e “n” é utilizado para indicar um elemento arbitrário de conjunto de objetos O.

Após (i) a definição de “string S”—um objeto que é um símbolo ※ ou concatenadas símbolos ※, ↀ ou ∫ e (ii) a definição de “bem-formado” seqüências — (base) ※ e ↀS, ∫S onde S é qualquer seqüência, vêm os axiomas:

• ↀ※ => ※, em palavras: “SE ↀ é aplicada ao objeto ※ em objeto ※ resultados.”
• ∫N ε o, in words “IF ∫ is applied to arbitrary object “n” in o THEN this object ∫n is an element of O”.
• ↀn ε o, “IF ↀ is applied to arbitrary object” n “in o THEN this object .n is an element of O”.
• ↀ ∫ n = > n, “if ↀ is applied to object ∫n then Object n results.”
• ∫ ↀn => n, ” if∫is applied to object ↀn then Object n results.”

então qual pode ser a interpretação (pretendida) destes símbolos, definições e axiomas?

Se a gente definir ※ como “0”, ∫ como “sucessor”, e ↀ como “antecessor”, em seguida, ↀ ※ => ※ indica “adequada subtração” (por vezes designado pelo símbolo ∸, onde “antecessor” subtrai uma unidade a partir de um número, assim, 0 ∸1 = 0). A string ” ↀ ∫ n = > n ” indica que se primeiro o sucessor é aplicado a um objeto arbitrário n e então o predecessor ↀ é aplicado a ∫n, Os resultados originais de N.”

Este conjunto de axiomas é “adequado”? A resposta adequada seria uma pergunta: “adequada para descrever o quê, em particular?””The axioms determine to which systems, defined from outside the theory, the theory applies.”(Kleene 1952: 27). Em outras palavras, os axiomas podem ser suficientes para um sistema, mas não para outro.

Na verdade, é fácil ver que este axioma não é muito bom—na verdade, ele é inconsistente (ou seja, ele produz resultados inconsistentes, não importa o que sua interpretação):

Exemplo: Definir ※ como 0, ∫※ 1, e ↀ1 = 0. Do primeiro axioma, ↀ ※ = 0, so ∫ ↀ ※ = ∫ 0 = 1. Mas o último axioma especifica que, para qualquer conjunto arbitrário de n, incluindo ※ = 0, ∫ↀn => n, então este axioma estabelece que ∫ↀ0 => 0, e não 1.

Observe também que o conjunto axiomático não especifica que ≠ n ≠ n. Ou, excetuando o caso n = ※, ↀn ≠ n. Se incluíssemos estes dois axiomas precisaríamos de descrever as noções intuitivas “iguais” simbolizadas por = e não-iguais simbolizadas por ≠.