Máquina de Turing
A Máquina de Turing é um dispositivo teórico conhecido como máquina universal, que foi concebido pelo matemático britânico Alan Turing (1912-1954), muitos anos antes de existirem os modernos computadores digitais. Num sentido preciso, é um modelo abstrato de um computador, que se restringe apenas aos aspectos lógicos do seu funcionamento, e não a sua implementação física. Numa máquina de Turing pode-se modelar qualquer computador digital.
Descrição informal
Note que cada parte da máquina é finita e sua quantidade de fita potencialmente ilimitada dá uma quantidade ilimitada de espaço de memória.
Definição formal
Mais formalmente, uma máquina de Turing (com uma fita) é perfeitamente definida como uma 7-upla M = ( Q , Σ , Γ , s , b , F , δ ) {\textstyle M=(Q,\Sigma ,\Gamma ,s,b,F,\delta )} , onde Definições na literatura às vezes diferem um pouco, para tornar argumentos ou provas mais fáceis ou mais claras, mas isto é sempre feito de maneira que a máquina resultante tem o mesmo poder computacional. Por exemplo, mudar o conjunto { ← , → } {\displaystyle \{\leftarrow ,\rightarrow \}} para { ← , → , P } {\displaystyle \{\leftarrow ,\rightarrow ,P\}} , onde P permite ao cabeçote permanecer na mesma célula da fita em vez de mover-se para a esquerda ou direita, não aumenta o poder computacional da máquina, pois é possível simular o movimento P com o movimento sequenciado de ← {\displaystyle \leftarrow } e → {\displaystyle \rightarrow } o que mantém o cabeçote no mesmo lugar.
Imagem: La Cultura a Escena (youtube) · BY · Openverse
Nas palavras de Van Emde Boas (1990) p. 6: "O objeto do conjunto teórico [sua descrição formal sete-tupla similar ao acima] fornece apenas informação parcial sobre como a máquina agirá e com o que suas computações se parecerão."
Definições alternativas
Para tornar as provas e argumentos mais fáceis ou mais claras, encontramos na literatura definições levemente diferentes, mas isso sempre é feito de tal maneira que a máquina resultante tenha o mesmo poder computacional. Por exemplo, modificando o conjunto { L , R } {\displaystyle \{L,R\}} para { L , R , N } {\displaystyle \{L,R,N\}} , onde N ("Nada" ou "Sem operação") permitiria a máquina ficar sobre a mesma célula da fita em vez de mover para a esquerda ou para direita, não aumenta o poder computacional das máquinas. A convenção mais comum representa cada "instrução de Turing" na "tabela de Turing" por uma de nove 5-uplas, pela convenção de Turing/Davis (Turing (1936) em Undecidable, p. 126-127 e Davis (2000) p. 152):
O "estado"
A palavra "estado" utilizada em contexto de máquinas de Turing pode ser uma fonte de confusão, como isso pode significar duas coisas. A maioria dos comentaristas depois de Turing utilizaram "estado" para denotar o nome/designador da instrução atual para ser realizada — i.e. , os conteúdos do registro de estado. Mas Turing (1936) fez uma distinção forte entre um registro do que ele chamou de m-configuração da máquina, (seu estado interno) e o "estado de progresso" da máquina (ou pessoa) através da computação - o estado atual do sistema total. O que Turing chamou "a fórmula do estado" inclui ambos a instrução atual e todos os símbolos sobre a fita:
Imagem: Victoriano Izquierdo Personal Photos · BY-NC-SA · Openverse
A máquina de Turing a seguir tem um alfabeto {¬, 1}, onde ¬ representa o símbolo branco. Ela espera uma série de 1's na fita, com o cabeçote inicialmente no 1 mais à esquerda, e duplica os 1's com um ¬ no meio. Por exemplo, "111" torna-se "111¬111". O conjunto dos estados é {s1, s2, s3, s4, s5} e o estado inicial é s1. A tabela de ação é dada a seguir. A primeira linha desta tabela pode ser lida como: "Se a máquina estiver no estado s1 e o símbolo lido pelo cabeçote for 1, então escreva o símbolo ¬, mova uma posição para a direita e mude o estado para s2". Uma computação nesta máquina de Turing pode ser, por exemplo: (a posição do cabeçote é indicada mostrando-se a célula em negrito) O comportamento desta máquina pode ser descrito como um laço (loop): Ele inicia em s1, substitui o primeiro 1 com um ¬, então usa o s2 para mover para a direita, passando pelos 1's e pelo primeiro ¬ encontrado. S3 então passa pela próxima sequência de 1's (inicialmente há nenhuma) e substitui o primeiro ¬ que encontra por um 1. S4 move de volta para a esquerda, passando pelos 1's até encontrar um ¬ e vai para o estado s5. S5 então move para a esquerda, passando pelos 1's até achar o ¬ que foi originalmente escrito por s1. Ele substitui o ¬ por 1, move uma posição para a direita e entra no estado s1 novamente para outra execução do laço. Isso continua até s1 achar um ¬ (este é o ¬ que fica entre as duas cadeias de 1's), situação na qual a máquina pára.
Imagem: La Cultura a Escena (youtube) · BY · Openverse
Se a tabela de ação tem no máximo uma entrada para cada combinação de símbolo e estado então a máquina é uma máquina de Turing determinística (MTD). Se a tabela de ação contém múltiplas entradas para uma combinação de símbolo e estado então a máquina é uma máquina de Turing não-determinística (MTND ou MTN).
Imagem: arkhangellohim · BY-NC-SA · Openverse
Toda máquina de Turing computa uma certa função computável parcial a partir da cadeia dada formada pelos símbolos do alfabeto. Neste sentido ela comporta-se como um computador com um programa fixo. No entanto, como Alan Turing descreveu, podemos codificar a tabela de ação de qualquer máquina de Turing em uma cadeia de símbolos. Portanto podemos tentar construir uma máquina de Turing que espera em sua fita uma cadeia descrevendo a tabela de ação seguida por uma cadeia descrevendo a fita de entrada, e então computa a fita que a máquina de Turing codificada teria computado.
Imagem: Aldo.martinez.n · BY-SA · Openverse
Frequentemente diz-se que as máquinas de Turing, ao contrário de autômatos mais simples, são tão poderosas quanto máquinas reais, e são capazes de executar qualquer operação que um programa real executa. O que está faltando neste enunciado é que praticamente qualquer programa particular executando em uma máquina particular e dada uma entrada finita é, na verdade, nada além de um autômato finito determinístico, já que a máquina em que executa pode estar apenas em uma quantidade finita de configurações. Máquinas de Turing poderiam de fato ser equivalentes a uma máquina que tenha uma quantidade ilimitada de espaço de armazenamento. Podemos questionar então por que as máquinas de Turing são modelos úteis de computadores reais. Há várias maneiras de responder a isto: Uma maneira em que máquinas de Turing são pobres modelos para programas é que muitos programas reais, tais como sistemas operacionais e processadores de texto, são escritos para receber entradas irrestritas através da execução, e portanto não param. Máquinas de Turing não modelam bem tal "computação contínua" (mas ainda podem modelar porções dela, tais como procedimentos individuais).
Imagem: Aldo.martinez.n · BY-SA · Openverse
Não é difícil simular uma máquina de Turing num computador moderno (exceptuando pela quantidade de memória limitada existente nos computadores actuais). O site de busca Google, em comemoração aos 100 anos de Alan Turing, publicou um doodle dia 23 de junho de 2012, em forma de uma máquina de Turing. É possível construir uma máquina de Turing com base puramente mecânica. O matemático Karl Scherer construiu essa máquina em 1986, usando conjuntos de construção de metal, plástico e alguma madeira. A máquina, com 1,5 m de altura, usa puxões de fios para ler, movimentar e escrever informação, a qual é, por sua vez, representada por rolamentos. A máquina encontra-se atualmente em exibição na entrada do Departamento de Ciência de Computadores da Universidade de Heidelberg, na Alemanha. O conceito de máquina de Turing foi usado como ferramenta educativa na obra de ficção científica The Diamond Age (1995), escrita por Neal Stephenson. A personagem principal, Nell, possui um livro interactivo que a ensina a pensar criativa e logicamente apresentando-lhe puzzles numa história, os quais, sendo máquinas de Turing, se tornam cada vez mais complexos à medida que a narrativa se desenvolve. Estes puzzles começam por ser simples aparelhos mecânicos e evoluem para processos econômicos abstractos, atingindo um ponto em que se assiste à interação entre completos reinos ficcionais.
Imagem: Aldo.martinez.n · BY-SA · Openverse
Contexto histórico: máquinas computacionais
Robin Gandy (1919-1995), um estudante de Alan Turing (1912-1954) e seu amigo ao longo da vida, traça a linhagem da noção de "máquina de calcular" até a Babbage (em cerca de 1834) e, na verdade, propõe a "Tese de Babbage": Que o desenvolvimento e análise de operações são agora capazes de serem executados por máquinas. A análise de Gandy da Máquina Analítica de Babbage descreve as seguintes cinco operações (cf. p. 52-53): Gandy afirma que "as funções que podem ser calculadas por (1), (2), e (4) são precisamente as que são Turing computáveis." (p. 53). Ele cita outras propostas de "máquinas de calcular universais" incluídas as de Percy Ludgate (1909), Leonardo Torres y Quevedo (1914), Maurice d'Ocagne (1922), Louis Couffignal (1933), Vannevar Bush (1936), Howard Aiken ( 1937). No entanto:
O Entscheidungsproblem (o "problema de decisão"): O décimo problema de Hilbert de 1900
Com relação aos problemas de Hilbert propostos pelo famoso matemático David Hilbert em 1900, um aspecto do problema #10 tinha ficado flutuando por quase 30 anos antes de ser enquadrado com precisão. A expressão original de Hilbert para o 10º problema é a seguinte: 10. Determinação da solubilidade de uma equação Diofantina. Dada uma equação Diofantina com qualquer número de incógnitas e com coeficientes inteiros racionais: Elaborar um processo que com ele pode ser determinado em um número finito de operações se a equação é solúvel por números inteiros racionais. O Entscheidungsproblem [problema de decisão para a lógica de primeira ordem ] é resolvido quando sabemos que um procedimento que permite a qualquer expressão lógica dada decidir por um número finito de operações a sua validade ou satisfazibilidade ... O Entscheidungsproblem deve ser considerado o principal problema da lógica matemática.
Alan Turing uma-máquina(-automática)
Na primavera de 1935, Turing como aluno de mestrado em Kings College Cambridge, Reino Unido, aceitou o desafio; ele tinha sido estimulado pelas palestras do lógico M. H. A. Newman "e aprendeu com elas do trabalho de Gödel e o Entscheidungsproblem ... Newman usou a palavra "mecânico" ... Em seu obituário de Turing em 1955 Newman escreveu: Para a pergunta "o que é um processo "mecânico" ?" Turing retornou a resposta característica "Algo que pode ser feito por uma máquina" e ele embarcou na tarefa altamente congênita de analisar a noção geral de uma máquina de computação. Eu acho, mas não sei, que Turing, desde o início de seu trabalho, tinha como objetivo uma prova da indecidibilidade do Entscheidungsproblem. Ele me disse que a "ideia principal" do artigo veio a ele quando ele estava deitado nos prados de Grantchester no verão de 1935. A "ideia principal" poderia ter sido sua análise da computação ou a realização de que havia uma máquina universal, e assim um argumento de diagonalização para provar insolubilidade.
1937-1970: O "computador digital", o nascimento da "ciência da computação"
Em 1937, enquanto em Princeton trabalhando em sua tese de doutorado, Turing construiu um multiplicador (lógico-booleano) digital do nada, fazendo seus próprios relés eletromecânicos (Hodges p. 138). "A tarefa de Alan foi para encarnar o projeto lógico de uma máquina de Turing em uma rede de relé-operacinados interruptores ..." (Hodges p. 138). Embora Turing pudesse estar inicialmente curioso e experimentando, trabalhos muito sérios, no mesmo sentido, estavam sendo desenvolvidos na Alemanha ( Konrad Zuse (1938)), e nos Estados Unidos ( Howard Aiken ) e George Stibitz (1937); os frutos do seus trabalhos foram usados pelos militares do Eixo e dos Aliados na Segunda Guerra Mundial (cf Hodges p. 298-299).No início e meados da década de 1950, Hao Wang e Marvin Minsky reduziram a máquina de Turing a uma forma mais simples (um precursor da máquina de Post-Turing de Martin Davis); simultaneamente pesquisadores europeus estavam reduzindo o novíssimo computador eletrônico a um computador como objeto teórico equivalente ao que estava sendo chamado de "máquina de Turing". No final dos anos 1950 e início dos anos 1960, os desenvolvimentos, coincidentemente paralelamente, Melzak e Lambek (1961), Minsky (1961), e Shepherdson e Sturgis (1961) continuaram o trabalho europeu e reduziram a máquina de Turing para uma máquina mais amigável, como um computador de modelo abstrato chamado de counter machine ; Elgot e Robinson (1964), Hartmanis (1971), Cook e Reckhow (1973) levaram este trabalho ainda mais com a máquina de registo e de acesso aleatório máquina modelos, mas basicamente todos são apenas máquinas multi-fita de Turing com um conjunto de instruções aritméticas.
1970-presente: a máquina de Turing como um modelo de computação
Hoje, o contador, registrador e máquinas de acesso aleatório e seu pai a máquina de Turing continuam a ser os modelos de escolha para os teóricos que investigam questões da teoria da computação. Em particular, a teoria da complexidade computacional faz uso da máquina de Turing; Dependendo dos objetos um gosta de manipular os cálculos (números como inteiros não negativos ou cordas alfanuméricos), dois modelos têm obtido uma posição dominante na teoria da complexidade baseada em máquina: a máquina off-line multi-fita de Turing ..., que representa o modelo padrão para a computação orientada a cadeia, e a máquina de acesso aleatório (RAM), como introduzida por Cook e Reckhow ..., que modela o estilo de computador idealizado por Von Neumann.
