Computabilidade

Uma função f: Nᵏ → N é computável quando um procedimento mecânico, para cada k-upla, termina e devolve o valor. Em um sistema formal o procedimento produz teoremas: S ⊢ T quando T se alcança em finitos passos a partir dos axiomas.

Gödel, os esquemas PR e μ, e o máximo S(k) deste tópico — e as classes P e NP no tópico seguinte — partem dessa função computável e da relação ⊢.

As páginas se agrupam em três blocos. O primeiro pergunta o que o sistema S demonstra: se a cadeia de regras alcança T, e se toda sentença verdadeira dos naturais tem prova.

O segundo pergunta quais funções Nᵏ → N cabem no laço com teto conhecido e quais exigem uma busca sem teto.

O terceiro pergunta, entre as máquinas de k estados na fita vazia, se os tempos de parada têm máximo.

Sistemas Formais confere a cadeia S₀ ⊢ ⋯ ⊢ T e aplica Gödel: S consistente, recursivamente enumerável e aritmético deixa alguma φ verdadeira sem derivação.

Funções Recursivas escreve add(x,0)=x e add(x,y+1)=S(add(x,y)), calcula A(1,2)=4 e A(2,2)=7, classifica Ackermann como total e não primitiva recursiva, e enuncia que as μ-recursivas coincidem com as funções que uma máquina de Turing computa. Castor ocupado prova que S(k) existe pela finitude das tabelas: S(1)=1 e, para k=2, 12⁴ máquinas; nenhuma de k estados para depois de S(k)+1 passos.