Função calculável
Uma função computável (ou função recursiva ) é uma função semi-computável (ou função recursiva parcial ) que também é total , ou seja, definida em todo o seu domínio. Essas são as funções calculadas por uma máquina de Turing “ terminal” .
Uma função calculável não é necessariamente “calculável fisicamente”, por exemplo, se seu tempo de execução exceder vários bilhões de anos.
Os exemplos mais simples de funções computáveis são funções constantes . Uma consequência do princípio do terceiro excluído é então que a função constante que associa a um inteiro 1 se a conjectura de Goldbach for verdadeira e 0 se for falsa é computável, embora não saibamos hoje se a conjectura é verdadeira. Isso mostra como a aplicação deste princípio destrói qualquer noção intuitiva de computabilidade.
Exemplos
- Os programas de computador que param (durante a execução de qualquer entrada) são funções calculáveis.
- A função que toma como entrada uma máquina de Turing (representada por um inteiro) e uma entrada para esta máquina, e os associa a 1 se esta máquina parar nesta entrada, nada de outro modo, é uma função semicalculável. Somente uma aplicação do princípio do terceiro excluído torna possível estender esta função em uma função total que dá 0 se a máquina considerada não para na entrada considerada, mas esta função não é então calculável (para mais do que informações, consulte o artigo problema de desligamento ).
- O cálculo de um GCD é uma função calculável.
Referências
-
Alain Prochiantz , Machine-Mind , Odile Jacob,5 de janeiro de 2001( leia online ).
Veja também