Instruções detalhadas definindo um processo computacional (que é então dito ser algoritmico), que começa com um input arbitrário (a partir de um certo número de inputs possíveis para o algoritmo dado), e com instruções destinadas a obter um resultado (ou output) que é totalmente determinado pelo input. Por exemplo, as regras ensinadas nas escolas primárias para adição, subtração, multiplicação e divisão em colunas são algoritmos; nestes algoritmos os possíveis resultados são inteiros não negativos escritos no sistema decimal, enquanto os possíveis inputs são ordenados por pares de tais números. Não é, em geral, assumido que o resultado é necessariamente obtido: o processo de aplicação de um algoritmo a algum input possível (ou seja, um processo algorítmico que se inicia a partir desse input) também pode terminar sem que um resultado seja obtido (nesse caso, um sem stop de resultados) ou pode não terminar de todo. Se o processo terminar (não termina), então diz-se que o input é adequado (não é adequado) para o algoritmo em questão.
Um resultado importante nesta área é a indecidibilidade do chamado problema de parada. É possível construir um algoritmo $ \alpha $such que não há algoritmo para decidir se algum input arbitrário que é possível para $ \alpha $ é também adequado para $ \alpha $. Em particular, pode-se encontrar tal algoritmo $ \alpha $ para o qual o conjunto de seus possíveis inputs é o conjunto de números naturais.
A noção de um algoritmo é um dos conceitos centrais na matemática moderna, especialmente na área de cálculos. Um exemplo é dado abaixo. Encontrar a solução numérica de equações de um determinado tipo equivale a construir um algoritmo que converte uma equação arbitrária deste tipo e um número racional positivo arbitrário $ \epsilon $ em um número (ou um conjunto de números) que difere da(s) raiz(s) desta equação por menos de $ \epsilon $. No entanto, o termo “processo computacional”, como utilizado no contexto de um algoritmo, não deve ser entendido como significando cálculos meramente numéricos: mesmo em cálculos de álgebra elementar com letras são utilizados. Os cálculos aritméticos padrão envolvem alguns símbolos que não são números (parênteses, sinais de igualdade, símbolos para operadores aritméticos). Por isso, é conveniente considerar algoritmos que envolvam símbolos arbitrários e objetos compostos a partir de símbolos. O exemplo mais simples de tal objecto é uma sequência linear de símbolos que formam uma palavra. Também é possível considerar objetos “não lineares” – matrizes algébricas, árvores de derivação de alguma linguagem formal e gráficos gerais. Intuitivamente, o mínimo requisito nos inputs e resultados dos algoritmos é que eles devem ser objetos construtivos (cf. Objeto construtivo). Assim, o conceito de um algoritmo é muito geral. Pode-se falar de um algoritmo para a tradução de uma língua para outra, de um algoritmo de um controlador de tráfego aéreo (processamento de informações sobre os movimentos das aeronaves de acordo com regras fixas), e outros exemplos de processos de controle descritos algorítmicamente. Consequentemente, o conceito de um algoritmo é uma das ideias centrais na cibernética e informática.
Exemplo de um algoritmo.
Deixe as possíveis entradas e os possíveis resultados serem todas as palavras possíveis sobre o alfabeto $ \{ a, b \} $. A transição de uma palavra $ X $ para uma palavra $ Y $ é “permissível” nos dois casos seguintes (onde $ P $denota uma palavra arbitrária): 1) $ X $is do formulário $ aP $, e $ Y $is do formulário $ Pb $; ou 2) $ X $is do formulário $ baP $, enquanto $ Y $is do formulário $ Paba $. As instruções são formuladas como se segue: “designando alguma palavra como o input, execute as transições permitidas até que uma palavra do formulário aaP seja obtida; depois pare e deixe a palavra P ser o resultado” . Estas instruções constituem um algoritmo, que será denotado por $ \mathfrak A $. Pegue a palavra $ babaa $ como o input. Após uma transição obtém-se $ baaaba $; após a segunda, obtém-se $ aabaaba $. Aqui o algoritmo pára com $ baaba $ como resultado. Considere outro input $ baaba $. Obtém-se, em sucessão, $ abaaba, baababab, abababa, bababab, babababa , . $. Pode-se mostrar que este processo nunca terminará (ou seja, nenhuma das palavras geradas começarão com $ aa $). Agora pegue $ abaab $ como entrada. Obtém-se $ baabb, abbaba, bbabab $; não são possíveis mais transições permitidas e, ao mesmo tempo, a condição de terminação não é satisfeita. A pessoa tem uma parada sem resultados. Assim, input $ babaa $ é adequado para $ \mathfrak A $, e inputs $ baaba $ e $ abaab $ não são.
O significado dos algoritmos.
Na ciência, os algoritmos são encontrados em toda parte: uma solução “geral” para um problema requer um algoritmo. A capacidade do homem de adicionar números é um exemplo disso. Não o facto de ele poder encontrar, mais cedo ou mais tarde, a soma de quaisquer dois números, mas sim no sentido de que ele possui um método para a adição única de quaisquer dois números dados na forma escrita, ou seja, um algoritmo de adição como o conhecido método de adição por coluna. “Geralmente” a solução de um problema é formalizada como a solução de um problema algorítmico. Um problema algorítmico consiste em instâncias de problema separadas, e um único algoritmo precisa ser encontrado para a solução de todos eles. Se não existe tal algoritmo, diz-se que o problema algorítmico é insolúvel. Assim, o problema de resolver numericamente equações de um determinado tipo e o problema de tradução automática são problemas algorítmicos. Seus problemas são, respectivamente, encontrar a solução numérica de equações individuais de um determinado tipo e a tradução de frases individuais. Outros exemplos são a verificação de equações algébricas em álgebra; o problema algorítmico do reconhecimento da dedutibilidade de proposições de determinados axiomas em lógica matemática. (Na lógica matemática, o conceito de algoritmo também é importante, pois serve como base do conceito chave de um cálculo, que é uma generalização e uma forma mais precisa dos conceitos intuitivos de “prova” e “demonstração”). O estabelecimento da insolvabilidade de um determinado problema algorítmico (por exemplo, o problema de estabelecer a verdade ou demonstrabilidade de frases em alguma linguagem lógico-matemática) é importante, pois mostra que, em princípio, instâncias específicas desse problema só podem ser resolvidas por métodos específicos para cada instância de problema individual.
A importância científica do conceito de um algoritmo é reconhecida há muito tempo. Desde os primeiros tempos, as pessoas têm procurado por métodos construtivos para resolver problemas matemáticos. Tais esforços geralmente se beneficiaram da nova disponibilidade de notações simbólicas adequadas. Este processo tem dado uma contribuição significativa ao conhecimento científico, especialmente depois de ter ficado claro que alguns problemas são intrinsecamente insolúveis (quadratura do círculo, etc.). Depois de ter sido reconhecido que certos problemas não podem ser resolvidos por cálculos diretos, o conceito teórico de um conjunto nasceu no século XIX. Só após um período de rápido desenvolvimento deste conceito (que não envolvia problemas de métodos construtivos no seu sentido moderno), foi possível em meados do século XX voltar aos problemas construtivos, mas isto foi feito a um nível diferente, enriquecido pelo conceito de um algoritmo que entretanto se tinha cristalizado. Este conceito forma a base da tendência construtiva em matemática.
A palavra “algoritmo” vem da palavra “algoritmi” , sendo esta última a transliteração latina do nome do matemático árabe do século IX Al-Khwarizmi. Um “algoritmo” na Europa da Idade Média era “o sistema decimal-posicional e a arte de calcular com ele” , pois é através da tradução latina (século XII) do tratado de Al-Khwarizmi que o sistema posicional foi introduzido na Europa.
A estrutura de um processo algorítmico.
Um processo algorítmico é um processo de conversão consecutiva de objectos construtivos por “passos” discretos , cada passo consistindo na substituição de um objecto construtivo por outro. Assim, ao aplicar o algoritmo $ \mathfrak A $ à palavra $ baaba $, seguem-se, sucessivamente, as palavras $ baaba, abaaba, baababab $, etc. Se se aplicar, digamos, o algoritmo de subtracção em coluna ao par de números <307, 49 >, então obtém-se, sucessivamente, os seguintes objectos construtivos:
$$ \begin{array}{rrrr}307 &3 \7 &3 \dot{0} 7 &\dot{3} \7 abaixo da linha 49. &\i}underline{- 49 } &\i}underline{- 49 } &\i}underline{- 49 } \\{} & 8 &58 &258 {arranjo}$$
Note-se que, numa série de objectos construtivos sucessivos, cada objecto construtivo sucessivo é totalmente determinado (no quadro do algoritmo dado) pelo objecto construtivo imediatamente anterior a ele. Na abordagem mais rigorosa, assume-se também que a transição de qualquer objecto construtivo para o imediatamente seguinte é suficientemente “elementar” – no sentido em que a transformação de um passo do objecto precedente no objecto imediatamente seguinte é local (não é todo o objecto construtivo que se transforma, mas apenas a sua parte limitada ao algoritmo; além disso, esta transformação em si não é determinada pelo objecto precedente completo, mas apenas por uma parte limitada do mesmo).
De acordo, não só se tem um conjunto de entradas possíveis e um conjunto de resultados possíveis, mas também um conjunto de resultados intermediários possíveis, representando o meio de trabalho no qual o processo algorítmico está evoluindo. Em relação a $ \mathfrak A $, todos esses três conjuntos coincidem, mas isso não é verdade para o algoritmo de subtração em coluna – os inputs possíveis são pares de números, os resultados possíveis são números (todos no sistema decimal), enquanto os resultados intermediários possíveis são registros de “três andares” do tipo
$$ \begin{r}{r} p \begin{- q } \\ r $$$
onde $ q $ é o registo escrito do número no sistema decimal, $ r $ é um registo semelhante ou a palavra vazia, enquanto $ p $ é o registo escrito de um número no sistema decimal, com pontos sobre alguns dos dígitos. Como regra, vários parâmetros (não independentes) que são característicos de um algoritmo podem ser distinguidos: 1) o conjunto de entradas possíveis; 2) o conjunto de resultados possíveis; 3) o conjunto de resultados intermediários possíveis; 4) a regra inicial; 5) a regra de transição direta; 6) a regra de término; e 7) a regra para a recuperação do resultado.
Formalizar o conceito de um algoritmo.
O conceito de um algoritmo na sua forma geral é um conceito matemático fundamental que não pode ser definido em termos de conceitos mais simples. Estritamente falando, as formalizações do conceito de um algoritmo na realidade restringem-no um pouco. Em cada uma dessas formalizações é dada uma definição exata de alguma classe dentro da qual cada um dos parâmetros pode variar. As várias formalizações diferem umas das outras pela seleção de tais classes. Uma vez que os parâmetros definem sem ambiguidade algum algoritmo, uma escolha de domínios de parâmetros determina alguma classe de algoritmos. No entanto, tal escolha pode alegar ser uma formalização do conceito intuitivo de algoritmo, apenas se for possível ter a certeza que para qualquer algoritmo “intuitivo” existe um algoritmo equivalente na classe de algoritmos definida pela escolha em consideração. Este requisito é formulado para cada formalização como uma hipótese fundamental, que, no presente estado de conhecimento, não pode ser matematicamente demonstrada.
As primeiras formalizações deste tipo são devidas a E.L. Post
e a A.M. Turing , cujas construções anteciparam em muitos aspectos as ideias em que se baseiam os computadores modernos. Há também versões formuladas por A.A. Markov ,
(cf. Algoritmo normal) e por A.N. Kolmogorov , , que baseou a abordagem em complexos topológicos construtivos de um certo tipo, o que permite expressar mais precisamente a propriedade de “ser local” de uma transformação. Em cada uma destas formalizações a hipótese fundamental está em satisfatória concordância com a prática. Outro argumento a favor desta hipótese é o fato de que, como pode ser demonstrado, todas as versões formais (de computabilidade efetiva) que foram propostas são equivalentes.
Como exemplo, considere a formalização proposta por Turing. Na sua forma original, esta foi uma descrição de algum computador teórico constituído por 1) uma fita infinita, dividida em células consecutivas, cada célula capaz de conter algum símbolo fora do “alfabeto da fita” da máquina; e 2) um “controle finito”, que a cada momento está em algum “estado” (fora de uma dada lista finita de estados). O controle finito pode se mover ao longo da fita, uma célula de cada vez, e mudar o conteúdo das células que ela passa. Um programa que monitora o movimento do controle finito constitui o algoritmo para os cálculos realizados em tal máquina (um “algoritmo de turing”). Para uma descrição mais exacta e detalhada ver “Turing machine”. Aqui é dada uma exposição modernizada da construção da Turing. Para definir um algoritmo Turing, especifica-se a) os alfabetos disjuntos em pares $ B, D, C $, com uma letra distinta $ \lambda $ em $ D $ e letras distintas $ \alpha $ e $ \omega $ em $ C $; e b) um conjunto de pares da forma $langle p {\i}, p {\i1}pxi , pq {\i}eta Tq {\i}onde $ p, q {\i}em C $, $ {\i}, pq {\i}eta D $, enquanto $ T $ é um dos três símbolos $ -, 0, + $; neste conjunto (que é chamado de programa) não há dois pares com a mesma primeira coordenada. As entradas possíveis e as saídas possíveis são palavras acima de $ B $, enquanto que os possíveis resultados intermediários são palavras acima de $ B \cup D \cup C $ que não contém mais de uma letra de $ C $. A regra inicial é que a palavra inicial $ P $ é convertida para a palavra $ \lambda P \lambda $. A regra final é que um resultado intermediário que contém $ \mega $ é final. A regra para a recuperação da saída é que a saída é a seqüência de letras no resultado intermediário final que segue $ \mega $ e precede a primeira letra que não pertence a $ B $. A regra de transformação que converte $ A $ em $ A ^prime $ é a seguinte. A letra $lambda $ é escrita à esquerda e à direita de $ A $; na palavra assim formada, a parte da forma $epsilon p ^xi $, onde $ p^ em C $, $epsilon $^xi em B $cup D $, é substituída por uma palavra $ Q $ em conformidade com a regra: um par com o primeiro termo $ p \xi $ é procurado no programa; que o segundo termo deste par seja $ tq $; se $ t $is $ – $, $ Q = q \epsilon \eta $; se $ t = 0 $, $ Q = \epsilon q \eta $; se $ T $ é $ + $, $ Q = {\i1}epsilon {\i1}eta q=. A palavra produzida por esta troca é $ A {\i}prime $. Para referências, veja , , , , , , ,
de Algoritmos, teoria de.
A hipótese fundamental mencionada acima é normalmente chamada de tese de Igreja-Turing ou hipótese de Turing. Esta tese afirma que o que pode ser efetivamente computado de acordo com a intuição sobre o que constitui um processo efetivo, também pode ser computado por uma máquina Turing, ou seja, uma noção formalmente definida de algoritmo. Por sua própria natureza de identificar uma noção informal intuitiva com uma definição formal precisa, a tese Igreja-Turing não pode ser formalmente provada.
Muitas formalizações revelaram-se equivalentes, e nenhuma formalização revelou-se estritamente mais poderosa. Além das formalizações mencionadas acima, as seguintes referências são as mais padronizadas no Ocidente: Formalização da Igreja de números e funções computáveis por termos lambda, esquemas recursivos gerais de Kleene e o modelo de máquina de registro proposto por J.C. Shepherdson e H.E. Sturgis, que foi estendido para um modelo computacional mais realista por S.A. Cook e R.A. Reckhow. As versões do Markov e do Kolmogorov são menos conhecidas. Para completar as referências originais a Turing e Post também são dadas.
| A.M. Turing, “On computable numbers, with an application to the Entscheidungsproblem” Proc. London Math.Soc. Ser. 2 , 42 (1936) pp. 230-265 | |
| A.M. Turing, “Correcções a “Em números computáveis, com aplicação ao Entscheidungsproblem” ” Proc. London Math.Soc. Ser. 2 , 43 (1937) pp. 544-546 | |
| A. Church, “An unsolvable problem of elementary number theory” Amer. J. Matemática. 58 (1936) pp. 345-363 | |
| S.C. Kleene, “General recursive functions of natural numbers” Matemática. Ann. , 112 (1936) pp. 727-742 | |
| E.L. Post, “Formal reductions of the general combinatorial decision problem” Amer. J. Matemática. 65 (1943) pp. 197-268 | |
| J. C. Shepherdson, H. E. Sturgis, “Computabilidade de funções recursivas” J. Assoc. Comp. Mach. , 10 (1963) pp. 217-255 | |
| S.A. Cook, R.A. Reckhow, “Time-bounded random access machines” J. Computer and System Sciences , 7 (1973) pp. 354-375 |