Máquina de Turing de 2 estados e 3 símbolos de Wolfram

Em seu livro A New Kind of Science, Stephen Wolfram descreveu uma máquina de Turing de cinco cores e dois estados; e conjecturou que uma máquina de Turing particular de dois estados e três cores (de agora em diante, máquina de Turing (2,3)) ^[1] poderia também ser universal.

Em 14 de maio de 2007, Wolfram anunciou um prêmio de $25,000^[2] para a primeira pessoa que aprovasse ou desaprovasse a universalidade de uma máquina de Turing (2,3). De acordo com Wolfram, a proposta do prêmio era encorajar a pesquisa para ajudar a responder questões fundamentais associadas com a estrutura do que ele chama de "universo computacional". Em 24 de outubro de 2007, foi anunciado que o prêmio teria sido vencido por Alex Smith, um estudante de computação e eletrônica na Universidade de Birmingham.

Descrição

Em cada estado, a máquina lê um bit sob a cabeça e executa a instrução na seguinte tabela (onde Pn imprime o bit n; E e D são esquerda e direita, respectivamente; e A e B significam "troca de estado").

	A	B
0	P1,D,B	P2,E,A
1	P2,E,A	P2,D,B
2	P1,E,A	P0,D,A

A máquina de Turing (2,3):

• Não tem estado de parada;
• É trivialmente relacionada a 23 outras máquinas pelas trocas de estados, cores e direções.

Minsky (1967) brevemente argumenta que as máquinas padrões (2,2) não podem ser universais; embora, parece que a máquina de Turing (2,3) seria a menor máquina de Turing universal possível (em termos de estados * (vezes) número de símbolos). Entretanto, os resultados não são diretamente comparáveis, por que Minsky apenas considera máquinas as quais explicitamente param, o que a (2,3) não faz. Geralmente, quase todas as definições formais da máquina de Turing diferem em detalhes irrelevantes ao seus poderes, mas talvez relevantes ao que pode ser expressado usando um dado número de estados e símbolos; não existe uma única definição formal padrão. A máquina de Turing (2,3) também requer uma entrada infinita sem repetições, novamente fazendo uma comparação direta à problemática das máquinas de Turing pequenas. Portanto, achou-se que poderia ser verdade que a máquina (2,3) é de alguma forma a "menor máquina de Turing universal possível”, isso não tem sido estritamente provado; e a alegação disso está aberta a debates.

O estado da cabeça (com a gota para cima ou para baixo) e o padrão da cor (laranja ,amarelo e branco) em uma dada linha depende unicamente no contexto da linha imediatamente acima dela.

Mesmo achando que a máquina tem uma cabeça com apenas dois estados e a fita que pode guardar apenas três cores (dependendo do conteúdo inicial dessa), a saída da máquina pode ainda ser notavelmente complexa^[3]

Prova da universalidade

Em 24 de outubro de 2007, foi anunciado pela companhia Wolfram Research (sem a aprovação da comissão julgadora^[4]) que Alex Smith, um estudante de eletrônica e computação na Universidade de Birmingham, provou que a máquina de Turing (2,3) é universal e ganhou o prêmio de Wolfram descrito acima.^{[5][6][7][8][9][10][11][12][13][14][15][16]} Martin Davis notou em uma publicação do FOM mailing list que:

"Pelo tanto que eu sei, nenhum membro da comissão tem passado na validação desta prova de 40 páginas. A determinação de que a prova de Smith está correta parece ter sido feita inteiramente pela organização Wolfram. Meu entendimento é de que as Entradas e saídas envolvem codificações complexas."^[17]

A prova mostrou que a máquina é equivalente a uma variante de um sistema de tag já conhecido por ser universal. Smith primeiro construiu uma sequência de regras, mostrando que a máquina de turing (2,3) é capaz de computações finitas arbitrárias. Ele em seguida empregou uma nova abordagem para estender esta construção a computações ilimitadas. A prova procede em dois estágios. A primeira parte simula a evolução finita de qualquer sistema de tag de duas cores cíclico. A simulação é composta de séries de emulações envolvendo os sistemas de regras indexada 'system 0' através do 'system 5'. Cada sistema de regras simula a próxima em uma sequência. Smith, em seguida, mostrou que apesar da condição inicial da máquina de Turing (2,3) não ser repetitiva, a construção desta condição inicial não é universal. Por isso, a máquina (2,3) é universal.

Vaughan Pratt disputou a corretude desta prova em uma lista de discussão pública,^[18] notando que técnicas similares poderiam permitir ao autômato linearmente limitado (ou ALL) ser universal, o qual entraria em contradição com o já conhecido resultado da não universalidade devido a Noam Chomsky.

Alex Smith entrou na lista de discussão após esta mensagem e respondeu no dia seguinte, explicando que um ALL requereria ser reiniciado manualmente para se tornar universal usando a mesma configuração inicial, enquanto sua construção reinicia a máquina de Turing automaticamente sem nenhuma intervenção.^[19] Discussões sobre a prova continuaram por um tempo entre Alex Smith, Vaughan Pratt e outros.^[20]

Wolfram reivindica que a prova de Smith é outro pedaço da evidência ao Princípio geral de Wolfram de "Equivalência Computacional" (PCE).^[21] Esse princípio afirma que se alguém vê um comportamento que não é obviamente simples, o comportamento corresponderá a computação que está em sentido "maximamente sofisticado".^[22] A prova de Smith desencadeou um debate sobre as condições precisas operacionais que uma máquina de Turing deve satisfazer, a fim de que ela seja candidata à máquina universal.

A máquina de Turing universal (2,3) tem aplicações concebíveis.^[23] Por exemplo, uma máquina que é pequena e simples pode ser incorporada ou construída usando um pequeno número de partículas ou moléculas. Mas o algoritmo "compilador" de Smith implica não produzir código compacto ou eficiente, pelo menos para qualquer coisa exceto casos simples. Portanto, o código resultante tende a ser astronomicamente grande e muito ineficiente. Determinar se existem mais códigos eficientes que permitam que a máquina (2,3) compute mais rapidamente é uma questão em aberto.

Ver também

• Máquina de Turing
• Máquina de Turing universal
• Teoria dos Autômatos
• Máquina de estados finitos

Referências

1. Wolfram, Stephen (2002). A New Kind of Science. [S.l.: s.n.] p. 709. Consultado em 10 de fevereiro de 2009 
2. «The Wolfram 2,3 Turing Machine Research Prize». Consultado em 10 de fevereiro de 2009 
3. «Student snags maths prize». Consultado em 10 de fevereiro de 2009 
4. http://cs.nyu.edu/pipermail/fom/2007-October/012163.html
5. Keim, Brandon (24 de outubro de 2007). «College Kid Proves That Wolfram's Turing Machine is the Simplest Universal Computer». Wired. Consultado em 10 de fevereiro de 2009 
6. Geoff Brumfiel. «Nature.com». Nature.com. Consultado em 9 de março de 2010 
7. «New Scientist». New Scientist. Consultado em 9 de março de 2010 
8. «Thaindian.com». Thaindian.com. Consultado em 9 de março de 2010 
9. «U of Birmingham». Newscentre.bham.ac.uk. Consultado em 9 de março de 2010 
10. «Math in the news from Math Society». Ams.org. Consultado em 9 de março de 2010 
11. Crighton, Ben (26 de novembro de 2007). «Proving Turing's simple computer». BBC News. Consultado em 9 de março de 2010 
12. «Bitwise Mag article». Bitwise Mag article. 24 de outubro de 2007. Consultado em 9 de março de 2010 
13. «Mathematical Association of America». Maa.org. Consultado em 9 de março de 2010 
14. «Scientific American». Scientific American. 25 de outubro de 2007. Consultado em 9 de março de 2010 
15. «plus magazine». Plus.maths.org. Consultado em 9 de março de 2010 
16. Tom Stuart (29 de novembro de 2007). «U.K». London: Guardian. Consultado em 9 de março de 2010 
17. http://cs.nyu.edu/pipermail/fom/2007-October/012132.html
18. «Vaughan Pratt's message to the FOM list» 
19. «Alex Smith's first reply to Vaughan Pratt in the FOM list» 
20. «FOM list archive for November 2007». Cs.nyu.edu. Consultado em 9 de março de 2010 
21. «Stephen Wolfram reply in the FOM list» 
22. «The Wolfram Prize and Universal Computation: It's Your Problem Now» 
23. «Simplest 'universal computer' wins student $25,000». New Scientist 

• Wolfram, S (2002) A New Kind of Science. Wolfram Media.
• Wolfram Research, Inc., "Prize Announced for Determining the Boundaries of Turing Machine Computation". Formal announcement that Alex Smith has won the prize.
• ------, Wolfram 2,3 Turing Machine Research Prize. Invitation to contestants.

Bibliografia

• Marvin Minsky (1967) Computation: Finite and Infinite Machines. Prentice Hall.
• Turing, A (1937) "On Computable Numbers with an Application to the Entscheidungsproblem," Proceedings of the London Mathematical Society Series 2, 42: 230-265.
• ------ (1938) "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction," Proceedings of the London Mathematical Society Series 2, 43: 544-546.

Ligações externas

• "Student snags maths prize" Nature. Published online 24 October 2007.
• "College Kid Proves That Wolfram's Turing Machine is the Simplest Universal Computer," Wired Science. Published online 24 October 2007.
• "Simplest 'universal computer' wins student $25,000," New Scientist. Published online 24 October 2007.
• "The Wolfram Prize and Universal Computation: It's Your Problem Now," Dr. Dobbs Journal. Published online 22 October 2007.
• Minkel, J.R., "A New Kind of Science Author Pays Brainy Undergrad $25,000 for Identifying Simplest Computer," Scientific American, October 25, 2007.
• From Foundations of Mathematics discussion threads:
  • Simple Turing machines, Universality, Encodings, etc.
  • Simplest universal Turing Machine.
  • Smallest universal machine.
  • Vaughan Pratt's claim that Smith's proof is invalid.
  • Wolfram's reply to Pratt in the same forum.
  • Reply to Pratt by Todd Rowland, one of the judges for the prize.