The most amazin fact: "All the attempts at formalizing the intuitive notion of computable function yield exactly the same class of functions." [1]
Paradigma 1: Máquina de Turing
- Possui uma fita dividida em quadrados (potencilamente infinita - pode ser estendida para a direita ou esquerda quando necessário).
- Possui uma cabeça de leitura que observa um quadrado, lê ou escreve algo no quadrado corrente ou se move para um dos quadrados vizinhos.
- Cada quadrado pode conter um símbolo (1) ou estar vazio (0).
- Operações básicas:
1. Escreve o símbolo 1 no quadrado corrente.
2. Apaga o símbolo que ocorre no quadrado corrente.
3. Move para o quadrado à direita.
4. Move para o quadrado à esquerda.
Paradigma 2: Função recursiva primitiva
- Todas as funções computáveis são resultado da aplicação de duas operações básicas em três funções básicas que são obviamente computáveis.
- Funções iniciais:
1. Z(n) = 0 --> zero
2. S(n) = sucessor de n na sequência de números naturais --> sucessor
3. P(i,k) (x1, x2, ..., xk) = xi --> projeção
- Operações básicas:
1. Composição de funções
2. Recursão primitiva:
* para funções de uma variável: f(0) = d
f(n+1) = h( f(n), n )
* para funções de mais de uma variável: f(0, x1, x2, ... xk) = g(x1, x2, ... xk)
f(n+1, x1, x2, ... xk) = h( f(n, x1, x2, ... xk), n, x1, x2, ... xk )
Dentre outros paradigmas...
Bacana pensar que essas duas definições super diferentes (uma bem operacional e outra bem matemática) vão resultar na mesma classe de funções. Isso pode ser um indicativo que eles estão na direção certa (se é que existe uma direção natural pré-definida pra seguir).
[1] Computability 3ed. Epstein, R. L. and Carnielli, W. A.