Computabilidade e Modelos de Computação

Computabilidade é uma propriedade elementar das máquinas ditas computáveis. Os computadores possuem a capacidade de receber como entrada de dados uma sentença (um programa) escrito em uma linguagem artificial computável (uma linguagem que o computador entende) e execultar tarefas bem definidas, baseada na interpretação da sentença recebida. O ato de interpretação da sentença é a execução do programa. Durante sua execução, o programa recebe entrada de dados informadas pelo usuário e produz saída de dados, que são captadas pelo usuário.
A entrada de dados efetuada pelo usuário do programa é formada por sentenças em uma linguagem abstrata (linguagem L1, mas adequada para pessoas). Assim a entrada de dados do programa pertence à linguagem artificial definida pelo programador.
A capacidade computacional plena (computabilidade) surge no momento em que a linguagem de máquina(linguagem L0), na qual o programa (a linguagem do programador) é construído, permite a construção de sentenças suficientemente poderosas (programas P0, escritos em L0), cuja a execução permite entrada de dados na linguagem abstrata (linguagem L1) , onde L1 irá tornar-se tão poderosa quanto L0. Os primeiro modelos de computabilidade, foram com:

• Kurt Göedel - funções recursivas.
• Alonso Church - lambda-calculus.
• Alan Turing - Máquina de Turing.

Essas invenções levaram a construção dos primeiros computadores.
Modelos de computação são modelos que buscam representar, e estudar a forma como calculamos, assim a CC, segundo as definições de Modelo Matemático , é verdadeiramente uma componente da matemática com a ciência.
Tomando por base o funcionamento de um computador, modelos de computação devem associar sinais de entrada e saídas, representar a memória (estado interno), basear-se na especificação de regras e de uma sequência para sua execução, e depender de um intérprete ou executor(computador).

links:
Teoria da Computação_Lucilia Figueiredo_UFOP2008
Computabilidade_Jorge Fernandes_maio2002