Máquina de Turing

Acho que atingi uma compreensão de como uma máquina de computação contemporânea cumpre os requisitos restritos da máquina universal de computação.

A máquina universal de computação é uma máquina que opera sobre símbolos ocorrendo um espaço unidimensional infinito. A máquina transforma seu estado de acordo com o símbolo atual; ela pode, por exemplo, avançar ou retroceder no espaço de símbolos, reescrever o símbolo em uma determinada posição, ou qualquer outra coisa.

A máquina se torna útil com a especificação do conjunto de símbolos representáveis e do significado de todos esses símbolos. Assim, um símbolo pode significar "avance três posições" e outro símbolo pode significa "substitua o próximo símbolo com o símbolo seguinte a esse, e vice-versa.

É claro que nenhuma máquina concreta terá acesso a um espaço infinito para símbolos; portanto, podemos falar sobre uma máquina universal restrita com espaço finito para símbolos.

Uma máquina universal binária é uma máquina cujos símbolos são 0 e 1. Uma tal máquina não pode significar muita coisa com apenas um símbolo, mas nada impede que significados especiais sejam atribuídos a sequências específicas de símbolos.

Assim, podemos falar sobre símbolos complexos, compostos por uma sequência de símbolos, que na máquina binária será uma sequência de 0s e 1s. A máquina binária possui portanto uma regra implícita: enquanto um símbolo complexo não for compreendido, ela avança para o próximo símbolo.

Quando um símbolo completo é compreendido, a máquina realiza a transformação especificada para aquele símbolo complexo.

É claro que, em uma máquina concreta, o número de símbolos complexos especificáveis é finito, já que os próprios símbolos complexos devem ser sequências finitas de símbolos fundamentais, e portanto existe uma combinação finita de tais símbolos complexos.

Mas um conjunto suficientemente grande pode representar todas as operações possíveis sobre uma memória sequencial de símbolos fundamentais, como: se o valor lógico do próximo símbolo complexo for verdade avance para a posição determinada pelo símbolo complexo seguinte a este, senão pelo símbolo complexo duas posições depois.

Isso é verdade porque, se podemos computar matemática fundamental, podemos computar qualquer coisa.