Máquinas de Turing

Neste primeiro vídeo da série sobre máquinas de Turing apresentamos algumas motivações e apresentamos o modelo fita-cabeçote-estado-de-máquina. Discutimos como extrair, a partir desse modelo, a definição precisa de MT como coleção finita de quádruplas.

Apresentamos em detalhes as máquinas que, em uma fita em branco, escrevem (a) infinitos símbolos "1" intercalados por células em branco e (b) escreve três símbolos "1" em uma fita em branco e para com o cabeçote de leitura no "1" mais à esquerda. Explicamos também como representar MT via fluxogramas.

Apresentamos em detalhes máquinas que (a) computam a função constante zero, ou seja, para qualquer argumento inteiro não negativo o valor da função é zero e (b) computam a função soma, ou seja, dados argumentos inteiros não negativos "m" e "n", o valor da função é "m+n".

Apresentamos uma prova indireta de que há funções de argumentos inteiros que não são computadas por uma máquina de Turing. A estratégia do vídeo é, por um lado, apresentar uma enumeração das Máquinas de Turing e, por outro lado, mostrar que a coleção de funções unárias de argumentos inteiros não negativos é não enumerável.

Enunciamos a função parada para MT e provamos, detalhada e cuidadosamente, que essa função não é computável por máquinas de Turing. Como setup para a prova, discutimos o acoplamento de MT e deixamos uma provocação no final do vídeo.

Neste sexto e último vídeo da série motivamos, enunciamos e defendemos a tese de Church-Turing. Por fim, argumentamos o porquê de não ser possível demonstrar essa tese.