Qual é a menor máquina de Turing em que não se sabe se pára ou não?

31

Eu sei que o problema da parada é indecidível em geral, mas existem algumas máquinas de Turing que obviamente param e outras que obviamente não. De todas as máquinas de torção possíveis, qual é a menor em que ninguém tem uma prova, quer pare ou não?

halting-problem Aaron
fonte

10

A resposta depende das especificidades do modelo da máquina (número de símbolos, etc.). De acordo com o artigo da Wikipedia sobre Busy Beaver, existe uma máquina de 2 símbolos e 5 símbolos que não se sabe se ela pára ou não.

Kaveh

1

Observe que a pergunta de Aaron não é sobre a decidibilidade de um determinado idioma, mas realmente a existência de uma prova de que uma máquina de Turing específica é interrompida. Para qualquer máquina de Turing, "o seu" problema de parada (se essa mesma máquina pára na entrada vazia) é "decidível": é Sim ou Não, e os dois idiomas {Sim} e {Não} são decidíveis. Isso é muito diferente de se ter uma prova de que a máquina para ou não. Aaron, se você quer dizer "qual é o menor

modo que o idioma

para com

seja indecidível", você pode editar sua pergunta?

M

$M$

{w ∣ M

$\{w \mid M$

w}

$w\}$

Michaël Cadilhac

1

@ MichaëlCadilhac O problema da parada é geralmente interpretado como "Dada uma máquina

e uma entrada

,

pára para a entrada

?" not "Dada uma máquina

,

para todas as entradas?"

M

$M$

w

$w$

M

$M$

w

$w$

M

$M$

M

$M$

David Richerby

@ DavidRicherby: Para mim, o problema da parada é o idioma da máquina (códigos) que para na entrada vazia. Se não é o significado pretendido aqui, acho que deve ser especificado para dissipar a possível confusão (ok, minha).

Michaël Cadilhac

várias maneiras de estudar o problema são válidas e inter-relacionadas e, de fato, há uma sutileza em distingui-las que o questionador não fez.

vzn

38

As maiores máquinas de Turing para as quais o problema de parada é decidível são:

$TM(2,3), TM(2,2), TM(3,2)$ $TM(k,l)$ $k$ $l$

$TM(2,4)$ $TM(3,3)$

$TM(4,2)$

O comentário de Kaveh e a resposta de Mohammad estão corretos; portanto, para uma definição formal das máquinas de Turing padrão / não padrão usadas nesse tipo de resultado, consulte Turlough Neary e Damien Woods trabalham em pequenas máquinas de Turing universais, por exemplo, A complexidade das pequenas máquinas de Turing universais: uma pesquisa (Regra 110 TMs são fracamente universais).

Marzio De Biasi
fonte

2

T M (4, 2)

$TM(4, 2)$

2

{⟨ M, x ⟩ ∣ M halts on x}

$\{\langle M,x \rangle \mid M \text{ halts on } x\}$

H A L T_{M} = {x ∣ M halts on x}

$HALT_M = \{ x \mid M \text{ halts on } x\}$

32

Gostaria de acrescentar que existem algumas máquinas de Turing para as quais o problema da parada é independente do ZFC.

Por exemplo, pegue uma máquina de Turing que procure uma prova de contradição no ZFC. Então, se o ZFC for consistente, ele não será interrompido, mas você não poderá provar isso no ZFC (por causa do segundo teorema da incompletude de Gödel).

Portanto, não se trata apenas de não ter encontrado uma prova ainda, às vezes nem existem provas.

Denis
fonte

ZFC? O que significa o ZFC? Eu simplesmente não consigo entender isso a partir do contexto.

Acapulco

7

@Acapulco lmgtfy.com/?q=zfc&l=1

Sasho Nikolov

Ri muito! Está bem. Eu fui ferido. Touchè. Não achava que seriam as iniciais que se relacionariam imediata e exclusivamente com esse tópico. De qualquer forma, não acho que dói adicionar um esclarecimento de "ZFC (teoria dos conjuntos de Zermelo-Fraenkel)" na primeira vez que é mencionado, também para evitar ambiguidade, caso exista? :)

Acapulco

16

@Acapulco, consulte o tour e o centro de ajuda . Qualquer cientista da computação teórico saberia o que significa o ZFC, então não há realmente a necessidade de um esclarecimento.

Kaveh

1

2

$2$

5

Ninguém tem uma prova se a máquina Universal Turing pára ou não. De fato, essa prova é impossível como resultado da indecidibilidade do problema da parada. A menor é uma máquina de Turing universal de dois estados e três símbolos, encontrada por Alex Smith pelo qual ganhou um prêmio de US $ 25.000.

Mohammad Al-Turkistany
fonte

4

Observe, no entanto, que, de acordo com a página da Wikipedia citada, a prova de universalidade é contestada. Além disso, este não é o modelo padrão das máquinas de Turing: a máquina supostamente universal não tem estado de parada, portanto não pode simular nenhuma máquina que pare, pelo menos no sentido padrão do que uma máquina de Turing universal faz.

David Richerby

2

@ DavidRicherby: Eu acho que a fraca universalidade da regra 110 é bem aceita: requer duas palavras diferentes repetidas à esquerda e à direita da entrada, e a condição de parada é a geração de um planador especial (gerado se e somente se a máquina simulada pára). Veja "Universalidade em autômatos celulares elementares", de Matthew Cook.

Marzio De Biasi

-4

uma pergunta geral inexatamente formulada, mas razoável, que pode ser estudada de várias maneiras técnicas específicas. existem muitas máquinas "pequenas" medidas por estados / símbolos em que a interrupção é desconhecida, mas nenhuma máquina "menor" é possível, a menos que seja apresentada alguma métrica justificável / quantificável da complexidade de uma TM que leve em conta estados e símbolos (aparentemente ninguém propôs um até agora).

$x \times y$ $x$ $y$

$x,y$

vzn
fonte

2

Não é necessário estabelecer uma métrica levando em consideração símbolos e estados. Uma vez que existem dois símbolos na fita, fica claro que o problema da parada é indecidível para quase todos os números de estados - pelo que me lembro, é possível escrever uma TM universal com apenas cinco estados. Se soubéssemos o limite exato da decidibilidade, tenho certeza de que seria fácil descrevê-lo em termos de (# estados, # símbolos) pares.

David Richerby

a pesquisa de castores ocupada envolve, de fato, encontrar provas para determinar se as MTs param nas configurações iniciais com pequeno número de estados, símbolos; existem casos resolvíveis. se alguém quer o "menor" qualquer coisa, deve criar uma métrica precisa que meça "pequeno". o ponto acima é que uma métrica que envolve apenas estados ou símbolos pode ser considerada enganosa na medida em que representa o limite conhecido que envolve ambos (e máquinas que não são universais). o limite indecidibilidade nesta pesquisa não é "fácil" para especificar em termos de alguma coisa, que é a sua natureza fundamental ....

vzn

1

2 \leq i \leq 4

$2\leq i\leq 4$

k_{i}

$k_i$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

k_{2}

$k_2$

k_{3}

$k_3$

k_{4}

$k_4$

David Richerby

ninguém propôs nenhuma métrica até agora. nenhuma fronteira importante nessa área é "trivial para descrever" e seria de esperar que o cenário fosse impossível via Rices thm. isso parece mostrar uma falta de familiaridade com a pesquisa e a referência citada, que está interessada na resolubilidade de insumos para máquinas menores do que aquelas conhecidas por serem universais (e conjecturadas por não serem universais). seus comentários parecem se concentrar nos limites universais versus não universais da máquina, que não são os mesmos que os limites de capacidade de decisão de castores ocupados que estão sendo explorados, por exemplo, nas referências citadas (ambas acima e nas de Marzio).

vzn

x

$x$

y

$y$

x

$x$

y

$y$

Qual é a menor máquina de Turing em que não se sabe se pára ou não?

Respostas: