Qual é a máquina de Turing universal de 2 estados mais simples e incontroversa?

Estou querendo codificar uma simples máquina de Turing nas regras de um jogo de cartas. Eu gostaria de torná-la uma máquina universal de Turing para provar sua integridade.

Até agora, criei um estado de jogo que codifica a máquina de Turing de 2 estados e 3 símbolos de Alex Smith . No entanto, parece (admitidamente baseado na Wikipedia) que há alguma controvérsia sobre se a máquina (2, 3) é realmente universal.

Por uma questão de rigidez, gostaria que minha prova apresentasse um UTM "não controverso". Então, minhas perguntas são:

1. A máquina (2,3) é geralmente considerada universal, não universal ou controversa? Eu não sei onde seria um local respeitável para procurar a resposta para isso.

2. Se a máquina (2,3) não é amplamente aceita como universal, qual é o menor N, de modo que uma máquina (2, N) é aceita de maneira não controversa como universal?

Editado para adicionar: Também seria útil conhecer todos os requisitos da fita infinita para as máquinas mencionadas, se você as conhecer. Parece que a máquina (2,3) requer um estado inicial de fita não periódico, o que será um pouco difícil de simular dentro das regras de um jogo de cartas.

Houve novos resultados desde o trabalho citado nas respostas anteriores. Esta pesquisa descreve o estado da arte (veja a Figura 1). O tamanho da menor máquina universal de Turing conhecida depende dos detalhes do modelo e aqui estão dois resultados relevantes para esta discussão:

• Existe uma máquina universal padrão de 2 estados e 18 símbolos (Rogozhin 1996. TCS, 168 (2): 215–240). Aqui temos a noção usual de símbolo em branco em uma ou ambas as direções de uma única fita.
• Existe uma máquina fracamente universal de 2 estados e 4 símbolos (Neary, Woods 2009. FCT. Springer LNCS 5699: 262-273). Aqui temos uma única fita contendo a entrada finita e uma palavra constante (independente da entrada) repetida infinitamente para a direita, com outra palavra constante repetida infinitamente para a esquerda. Isso melhora a máquina fracamente universal mencionada por David Eppstein.$r$$l$

Parece que o (2,18) é mais útil para você.

Observe que agora é sabido que todas as menores máquinas universais de Turing funcionam em tempo polinomial. Isso implica que seu problema de previsão (dado que uma máquina , entrada tempo limite unário, aceita dentro do tempo ?) Está P-completo. Se você está tentando fazer um jogo (para um jogador), isso pode ser útil, por exemplo, para mostrar que é difícil para o NP encontrar uma configuração inicial (mão de cartas) que leva a uma vitória em t movimentos. Para esses problemas de complexidade, nos preocupamos apenas com uma parte finita da fita, o que torna as máquinas (extremamente pequenas) fracamente universais muito úteis.w t M w $M$$w$$t$$M$$w$$t$

A figura mostra as menores máquinas universais conhecidas para uma variedade de modelos de máquinas de Turing (extraídas de Neary, Woods SOFSEM 2012). As referências podem ser encontradas aqui .

Esta não é uma resposta real à sua pergunta (não sei muito sobre o (2,3) debate sobre máquinas); mas sugiro o artigo " Máquinas pequenas de Turing e competição generalizada de castores ". Eu li rapidamente há algum tempo, e ele tem um bom gráfico com as fronteiras entre os 4 tipos de pequenas TMs:

• decidível
• problema semelhante ao Collatz aberto
• $3x + 1$Simulação
• universal

(talvez alguns resultados tenham sido aprimorados).

A noção de MT usada no artigo é a definição padrão de MT usada em papéis em pequenas máquinas universais de Turing:

... Eles têm uma fita unidimensional única, infinita nas duas direções, e um cabeçote de leitura / gravação de duas vias exclusivo. Há um símbolo em branco denotado por 0. Inicialmente, uma palavra finita, a entrada, é gravada na fita, outras células contêm o símbolo em branco, a cabeça lê o símbolo mais à esquerda da entrada e o estado é o estado inicial. Em cada etapa, de acordo com o estado atual da máquina e o símbolo lido pela cabeça, o símbolo é modificado, a cabeça se move para a esquerda ou direita (e não pode ficar lendo a mesma célula), e o estado é modificado. A computação para quando um estado de parada especial é atingido. ...

Também é possível alcançar a universalidade com 7 estados e 2 símbolos, embora muitas das mesmas objeções se apliquem (condições iniciais não uniformes na fita infinita e condições incomuns de terminação). Consulte http://11011110.livejournal.com/104656.html e http://www.complex-systems.com/abstracts/v15_i01_a01.html

Eles se baseiam na simulação do autômato celular da Regra 110, provado universal por Matthew Cook, e Cook também encontrou uma simulação de 2 estados e 5 símbolos da Regra 110, se você estiver comprometido com a restrição de que haja apenas dois estados.

$S$$0\leq s < S$$C$$0\leq c< C$$2$$\text{L}$$\text{R}$$C+4SC$

Em todos os momentos, apenas a célula atual, ou as duas células envolvidas em uma transição, podem ter cores aprimoradas: todas as outras células têm sua cor verdadeira. Queremos que nossa máquina se comporte da seguinte maneira: verifique qual transição real deve ser executada, mova as informações de "estado verdadeiro" da célula que queremos deixar para a célula de destino (isso envolve muitas idas e vindas), limpe o célula que deixamos (dando uma cor verdadeira), repita.

$(c,s)$$\text{L}$$\text{R}$$(c_{\text{new}}, s_{\text{new}}, \text{emit})$$\text{L}$

$c$$\text{L}$$c$$(c,0, \text{L},\text{receive})$$\text{R}$

Aqui estão as transições para implementar isso. Em quase todos os casos, mova-se na direção especificada pelo estado atual e depois vire o estado

1. $c \to (c,0,\langle dir\rangle,\text{receive})$$\langle dir\rangle$

2. $(c,s) \to (c_{\text{new}},s_{\text{new}},\text{emit})$

3. $(c,s,\text{emit}) \to (c,s-1,\text{emit})$$s>0$

4. $(c,0,\text{emit}) \to c$

5. $(c,s, \langle dir\rangle, \text{receive}) \to (c, s+1, \langle dir\rangle, \text{receive})$$\langle dir\rangle$

6. $(c,s, \langle dir\rangle, \text{receive}) \to (c,s)$$\langle dir\rangle$

$C+3SC$

a menos que você defina cuidadosamente "não controverso" de alguma maneira técnica, não há uma resposta precisa. aqui está outra máquina pequena, baseada na regra 110, provada universal em certo sentido, mas meu entendimento é que ela requer infinitas formulações periódicas de fita de entrada (e da mesma forma extração no final quando a máquina pára). nunca vi a edição de fita "periódica versus não periódica" descrita na literatura, embora tenha sido discutida em, por exemplo, listas de discussão em matemática [lista de discussão Foundations of Mathematics]

A prova de universalidade de Turing, de Alex Smith, da máquina de Turing de 2 estados e 3 símbolos, conjecturada por Wolfram, definitivamente não é controversa. A prova de universalidade fornecida (não a máquina) requer um padrão infinito na fita de Turing, e a questão era se alguém deveria permitir tais configurações (você pode pensar na fita geralmente 'em branco' como um padrão repetitivo infinito de símbolos em branco). A conclusão foi que, desde que a configuração na fita da máquina seja fixa (ou seja, ela não muda após o início do cálculo e permanece a mesma para qualquer cálculo), o cálculo universal é realizado pela máquina de Turing. Observe que isso NÃO é controverso para a regra 110 do autômato celular elementar da Wolfram, que Wolfram e Cook provaram ser universais. A prova de universalidade da regra 110 também requer um padrão infinito na configuração inicial, diferente em ambos os lados, e portanto é da mesma natureza para a máquina de Turing de 2 estados e 3 símbolos. Outra preocupação era que talvez esse relaxamento do requisito de condição inicial (em branco) tornasse universal alguns autômatos universais não-Turing aceitos, como autômatos de estado finito, lineares limitados ou push down para mencionar alguns exemplos, mas não o faz e respeita a hierarquia de Chomsky. Portanto, definitivamente não é controverso se a máquina de Turing de dois estados e três símbolos é universal, mas sua prova de universalidade exigia uma variação do que geralmente é considerado o cotamento de uma fita de máquina de Turing comum. Isso não implica diretamente, a propósito, que os dois estados,