Em 1900, o grande e influente matemático David Hilbert, no congresso internacional de matemáticos, anunciou os 23 problemas que deveriam nortear a pesquisa no séc. 20. Entre eles, o décimo, sobre um algoritmo para busca de raízes de equações diofantinas (com coeficientes e variáveis reais), foi estudado por nada menos que Alan Turing, que na época, década de 1930, era aluno de doutorado de Alonzo Church (criador do lambda-cálculo). Um exemplo de equação diofantina é ax+by=c, sendo que, dados a, b e c números reais, queremos saber quais valores de x e y levam à igualdade. Turing, trabalhando no modelo de computação que hoje leva o seu nome, a máquina de Turing, descobriu que diversos problemas em matemática não tem algoritmos para sua solução. Em 1970, Yuri Matiyasevich, matemático e cientista da computação russo, resolveu o problema de forma definitiva, ou seja, não existe um algoritmo para determinar uma solução para equações diofantinas.
O trabalho pioneiro de Turing, desenvolvido depois do golpe fatal desferido por Gödel em 1931, com seus teoremas da incompletude, formaram a base dos computadores modernos, calcados na arquitetura de Von Neumann, o gênio Húngaro que contribuiu em diferentes campos do conhecimento, desde teoria dos jogos na economia, fundamentos da mecânica quântica, engenharia química e, obviamente, matemática.
As máquinas de Turing são modelos computacionais mais sofisticados para análises em teoria da complexidade, problemas de decidibilidade, intratabilidade, eficiência de tempo e espaço em algoritmos, etc. Dentro da Teoria da Computação, área que abarca o estudo teórico dos limites do que pode ser computado, há modelos mais básicos como:
Autômatos Finitos Determinísticos
Autômatos Finitos Não-Determinísticos
Autômatos Finitos Não-Determinísticos Generalizados
Autômatos Finitos com Pilha
Cada modelo lida com um tipo de problema, como linguagens regulares, linguagens livres de contexto, sensíveis ao contexto e irrestritas.
Dentro de teoria da Computação e Matemática, um problema famoso e extremamente importante, é o de P vs NP. Quando analisamos a complexidade de tempo de um algoritmo, ou seja, como o tempo t varia com o tamanho da entrada n, e, utilizando a notação assintótica (que descarta constantes, coeficientes e variáveis de menor ordem em polinômios), encontramos uma hierarquia de performance, como O(1), constante, O(n*log(n)), O(n) linear, O(n²) quadrático, O(n³) cúbico, etc. Quando é possível verificar e solucionar um problema com um algoritmo em tempo polinomial, dizemos que ele faz parte do conjunto P. NP é a classe de problemas que não têm algoritmo conhecido para solução em tempo polinomial, mas que podem ser verificados rapidamente (polinomial) se uma solução para um caso específico for conhecida. Um exemplo é uma posição de xadrez. Se você tiver uma sequência de jogadas que termina em xequemate, é fácil verificar que funciona, caso contrário, o número de possibilidades diferentes de jogadas é monstruoso.