CCT-UFCA/Ciência da Computação/Teoria da Computação/O que é um algoritmo

O que é realmente é um algoritmo?

Durante muito tempo, o conceito de algoritmo era tratado de forma informal, sendo entendido como uma sequência finita de instruções simples capaz de realizar uma determinada tarefa. Esse conceito teve grande importância na matemática, pois permitia que vários problemas fossem resolvidos a partir de algoritmos, como por exemplo encontrar o máximo divisor comum ou identificar números primos. Apesar disso, essa definição informal permaneceu até a primeira metade do século XX, quando se percebeu que ela era insuficiente para um entendimento mais profundo, principalmente quando se queria provar que certos problemas não podiam ser resolvidos por nenhum algoritmo.

Em 1900, no Congresso Internacional de Matemáticos, David Hilbert apresentou 23 problemas desafiadores para o século que se iniciava. Um desses problemas, o 10º, pedia um método que determinasse se um polinômio multivariável possuía ou não uma raiz inteira. Hilbert não utilizou o termo "algoritmo", mas sim a ideia de um processo composto por um número finito de operações. Naquela época, a crença era que, eventualmente, seria possível encontrar um algoritmo para esse problema. Contudo, a resposta definitiva para o 10º problema só seria possível décadas depois, com a formalização da noção de algoritmo.

Para provar que não existe um algoritmo capaz de resolver um problema, foi necessário primeiro definir formalmente o que é um algoritmo. Esse avanço só foi alcançado na década de 1930, graças aos trabalhos de Alan Turing e Alonzo Church. Ambos propuseram formalizações do conceito de algoritmo, mas de formas diferentes: Turing utilizou um modelo conhecido como Máquina de Turing, enquanto Church utilizou o λ-cálculo. Posteriormente, ficou demonstrado que as duas definições eram equivalentes, originando o que conhecemos hoje como Tese de Church-Turing. Essa tese estabelece que tudo o que é possível computar por um algoritmo pode ser computado por uma Máquina de Turing.

A formalização dos algoritmos não só permitiu estudar os próprios algoritmos de forma científica, como também tornou possível demonstrar que alguns problemas, como o 10º problema de Hilbert, não possuem solução algorítmica. De fato, foi Yuri Matiyasevich quem, utilizando a teoria das Máquinas de Turing, provou que não existe algoritmo capaz de resolver o 10º problema de Hilbert, tornando esse problema Turing-reconhecível, porém não decidível.

A Máquina de Turing proposta por Alan Turing em 1936 é um modelo computacional extremamente poderoso. Ela é composta por uma fita infinita que funciona como memória e por uma cabeça de leitura e escrita que pode se mover para a esquerda ou para a direita. O modelo de Máquina de Turing consegue realizar qualquer tarefa que um computador real pode fazer. No entanto, mesmo esse modelo teórico encontra limites, pois existem linguagens e problemas que não podem ser resolvidos por nenhuma Máquina de Turing.

Formalmente, uma Máquina de Turing é definida por uma 7-upla composta por um conjunto finito de estados, um alfabeto de entrada, um alfabeto da fita (que inclui o símbolo em branco), um estado inicial, um estado de aceitação, um estado de rejeição e uma função de transição que determina o comportamento da máquina. Durante a computação, a Máquina de Turing lê um símbolo da fita, escreve um novo símbolo, move sua cabeça e transita para um novo estado, continuando esse processo até atingir um estado de aceitação, rejeição ou entrar em um loop infinito.