Em lógica e matemática - especialmente metalógica e teoria da computabilidade - método efetivo Hunter, Geoffrey , Metalogic : uma Introdução ao Metateoria de lógica de primeira ordem padrão , University of California Press, 1971 ( também chamado de procedimento efetivo) é o procedimento para uma classe de problemas é um método para o qual cada passo pode ser descrito como uma operação mecânica, e que, se seguidas rigorosamente resulta em: sempre dar alguma resposta , em vez de nunca dar nenhuma resposta ; sempre dar a resposta certa e nunca dar uma resposta errada ; sempre efetuada num número finito de passos, em vez de um número infinito ; trabalhar para todas as instâncias de problemas da classe .

Um método efetivo para o cálculo dos valores de uma função é um algoritmo ; funções com um método efetivo , por vezes são chamadas efetivamente calculáveis .

Vários esforços independentes para dar uma caracterização formal de previsibilidade eficazes levou a uma variedade de definições propostas (recursão geral, Máquina de Turing, Cálculo lambda), que mais tarde mostraram-se equivalentes, a noção capturada por essas definições é conhecida como função computável .

O tese de Church-Turing afirma que as duas noções coincidem: qualquer função aritmética que é efetivamente calculável é recursivamente computável. Esta não é uma expressão matemática e não pode ser comprovada por uma prova matemática.

Pode-se requerer que um método efetivo quando aplicado a um problema de fora da classe para a qual é eficaz, possa ser interrompido sem resultado ou continuar indefinidamente sem parar, mas não deve retornar um resultado como se fosse a resposta ao problema (cf divergência) .

Uma característica essencial de um método efetivo é que ele não requer qualquer engenhosidade de qualquer pessoa ou máquina para executá-lo. Dicionário de Filosofia de Cambridge , procedimento eficaz

Ver também Decidibilidade Problema de decisão Problema Função Resultados efetivos em teoria dos números Conjunto recursivo Problema indecidível

Referências

S. C. Kleene (1967), Mathematical logic. Reprinted, Dover, 2002, ISBN 0-486-42533-9, pp. 233 ff., esp. p. 231.

Categoria:Lógica matemática Categoria:Teoria da computabilidade Categoria:Teoria da computação