Resumo do capítulo 2 do livro Computability, Complexity, and Languages. Fundamentals of Theoretical Computer Science.

Instruções da Linguagem L:

  • V ← V + 1
  • V ← V – 1
  • V ← V
  • IF V ≠ 0 GOTO L

Sintáxe do L:

  • X1, X2, X3 … são as variáveis de entrada.
  • Z1, Z2, Z3 … são as variáveis locais.
  • Y é a variável de saída.
  • Todas as variáveis são 0 inicialmente.
  • Um estado, σ, de um programa é uma lista com pelo menos todas as variáveis utilizadas pelo programa.
  • Um snapshot, S, de um programa é contador i, 1 ≤ i ≤ n+1, que representa a instrução atual do programa, e um estado, (i, σ). Quando i = n+1 dizemos que o programa parou e o snapshot é terminal.
  • Uma computação de um programa é uma lista de snapshot, com o último snapshot sendo terminal.

Funções Computáveis:

  • ψP(m)(r1, r2,r3,…,rm) é o valor da variável Y após uma computação do programa P fazendo X1=r1, X2=r2, X3=r3… Xm=rm. Se não existe tal computação então dizemos que ψP(m)(r1, r2,r3,…,rm) é indefinida para esses valores (↑).
  • Dizemos que uma função parcial, g, é parcialmente computável se para algum programa P temos: gP(m)(r1, r2,r3,…,rm) = ψP(m)(r1, r2,r3,…,rm). Se g é total e há esse programa P então dizemos que g é computável.

Macros:

  • P(Y, X1, X2,… Xn, Z1, Z2,… Zk; E, A1, A2,… Al) programa P possui n variáveis X, k variáveis Z e l labels A. Podemos mudar suas variáveis como em seguida:
  • Qm = P(Zm, Zm+1, Zm+2,… Zm+n, Zm+n+1, … Zm+n+k; Em, Am,… Am+l)
  • Seja W ← f(V1,…, V3), podemos expandir a macro f da seguinte maneira:

Zm← 0
Zm+i← Vi
Zm+n+i← 0
Qm
[Em] W ← Zm

O autor original desse resumo é o Ronan Pardo, eu só dei uma ajeitada.