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