Dada uma TM

Quero determinar se esse problema de decisão é decidível. Eu tentei estabelecer reduções de Halt e "Aceita string vazia", mas ainda não encontrei uma solução.

Alguém pode me ajudar?

computability turing-machines undecidability Shuzheng
fonte

Isso significa que a máquina deve permanecer no mesmo local, sem movimentos. Não há muitas possibilidades para esse cálculo?

Hendrik Jan

Pode se mover, na verdade. Mas então suponha que

δ (q_{0},_) = (q, a, D)

$\delta(q_0,\_) = (q,a,D)$ para algum estado

q

$q$ , rótulo

a

$a$ e

D \in {L, R}

$D\in\{L,R\}$ . O que você pode dizer sobre o caso

q \neq q_{0}

$q\neq q_0$ ? O que acontece a seguir se

q = q_{0}

$q = q_0$ ?

Klaus Draeger

Esse problema pode ser decidível. Encontrei este artigo hal.inria.fr/inria-00074105 (não li, não tenho certeza) que poderia lhe interessar. Alega que o problema de parada para uma máquina de Turing de um estado é decidível. (que é um problema bastante próximo do seu problema).

wece

Altere o título da pergunta "... quando a fita de inicialização estiver em branco" se a sua recompensa for sobre "qualquer entrada de fita": o caso em que a fita está bloqueada é trivialmente decidível (eu postei uma resposta, mas de repente a apaguei quando Eu vi o comentário sobre a recompensa)

Vor

Respostas:

Eu diria que é decidível.

Se entendi corretamente, aqui está o que penso.

Antes de tudo, uma TM começa a partir de algum estado inicial $s_0$ . Como isso pode mudar o estado? Na sua função de transição, você tem algo como $(s_0, x) \to (s_i, y, m)$ Onde $s_i$ é um estado e $x$ , $y$ são símbolos e $m$ é o movimento da cabeça (esquerda direita ou permanecer). Portanto, se sair do estado inicial, deve haver uma transição de $(s_0, \_)$ para algum estado não $s_0$ . É fácil ver que é se e somente se. Assim, você pode construir outra máquina de Turing que tenha a entrada como TM em alguma codificação, passe pela função de transição e verifique a condição acima, e o problema é decidível.

Eugene
fonte

Eu não entendo essa resposta / algoritmo. Considere uma TM que possui uma regra de transição que pode deixar o estado

s_{0}

$s_0$ se o símbolo embaixo da cabeça for X. Agora precisamos saber se X pode estar presente em qualquer célula da fita. Suponha que a TM também tenha regras de transição no estado

s_{0}

$s_0$ que se movem para a esquerda e / ou para a direita e escrevem símbolos na fita, incluindo potencialmente o X. Agora, o que você fará? Como você vai dizer se a TM pode potencialmente gravar X em alguma célula e depois revisitá-la? Não vejo nenhum algoritmo aqui que lide com essa situação.

@DW Estamos falando de MT deteminística ou não determinística aqui?

187 Eugene

Essa é uma pergunta que você deve fazer ao pôster original se achar que não está claro, mas com as informações fornecidas, acho que devemos assumir uma TM determinística. Dito isto, suspeito que fui influenciado pelo texto de recompensa, que se refere a "nunca sai do estado inicial, não importa para nenhum estado inicial da fita", que é um pouco diferente de "nunca sai do estado de entrada quando o inicial o estado da fita está em branco ", então talvez minha objeção seja irrelevante para a pergunta apresentada.

De qualquer forma, talvez ajude a justificar a parte "fácil de ver ..." com mais cuidado. Por exemplo, você parece não usar explicitamente o fato de que a fita inicial está toda em branco, embora pareça que isso faça uma grande diferença.

Trivialmente decidível. Dado que a fita está realmente em branco, então T no estado $s_0$ deve alterar a célula de fita digitalizada no momento e executar uma destas três ações: (1) faça a transição para um estado diferente e mova para a esquerda ou direita (ou pare); (2) Transição de volta para $s_0$ e mova uma célula para a esquerda; (3) Transição de volta para $s_0$ e mova uma célula para a direita. Para ambos (2) e (3), o cabeçote da TM se afastou da célula de fita original e agora está digitalizando uma célula em branco; portanto, está agora na mesma situação em que começou e agirá da mesma maneira. Portanto, para (2) ou (3) o comportamento da MT em uma fita em branco é mover-se para sempre em uma direção, deixando um rastro de (provavelmente) células alteradas. Portanto, essa propriedade pode ser verificada inspecionando o conteúdo de uma única linha do 'programa' da TM (ou seja, a regra de transição para $s_0$ digitalização em branco) - se o novo estado NÃO for $s_0$ (incluindo 'paradas') a resposta é SIM, caso contrário, a resposta é NÃO.

Também estou razoavelmente certo de que o problema ainda é decidível, dada uma entrada arbitrária - você só precisa prestar mais atenção em qual direção a cabeça da fita se move, dependendo do conteúdo atual da célula.

PMar
fonte