Prova construtiva de decidibilidade do conjunto finito no estilo de problema de parada que não usa a pesquisa de tabela

Tentei provar que o seguinte idioma é recursivo: para , um número inteiro positivo: onde $\Sigma=\{0,1\}$ $k$

L_{k} = H_{T M, ε} \cap Σ^{k}

$L_k= H_{\mathrm{TM},\varepsilon}\cap \Sigma^k$

H_{T M, ε} = {⟨ M ⟩ ∣ M is a TM that halts on an empty input}

$H_{\mathrm{TM},\varepsilon}=\{\langle M\rangle\mid M \text{ is a TM that halts on an empty input}\}$

É fácil provar porque é finito, mas eu não percebi isso e tentei provar isso encontrando uma TM decisiva para ele. Eu pensei que, como a codificação da TM é de comprimento , ela não pode ter mais de estados e, executando-a no épsilon por etapas, se parar por essa altura, aceitar outras rejeições. Foi-me dito que está incorreto - é uma solução errada. Como posso provar isso usando esse método (e não da maneira que mencionei sobre ser finito)? $L_k$ $k$ $2^k$ $2^k$ $L_k$

computability turing-machines proof-techniques scifie
fonte

Tomei a liberdade de editar sua postagem no formato LaTex. Se interpretou mal sua intenção, sinta-se à vontade para revertê-la para sua forma original. Também sugeri que fosse reaberto. Vamos ver como isso vai. By the way, bem-vindo ao site.

23915 Rick Decker

Como é indecidível, ele não pode ser representado por uma união recursivamente enumerável de conjuntos decidíveis. Portanto, existem subconjuntos infinitos indecidíveis (e co-infinitos) de . Portanto, você precisa usar a finitude de alguma maneira. Você está perguntando: "como mostro a decidibilidade usando a finitude de uma maneira menos óbvia?". Não sei em que sentido essa é uma pergunta útil para você.

H_{T M, ε}

$H_{\mathrm{TM},\varepsilon}$

H_{T M, ε}

$H_{\mathrm{TM},\varepsilon}$

Raphael

@Raphael: é a união dos conjuntos para números inteiros positivos . Portanto, é "uma união recursivamente enumerável de conjuntos decidíveis".

H_{T M, ϵ}

$H_{\mathrm{TM},\epsilon}$

{⟨ M ⟩ ∣ M is aTM that halts within t steps on ϵ input}

$\{\langle M\rangle \mid M \text{ is aTM that halts within } t \text{ steps on $\epsilon$ input}\}$

t

$t$

H_{T M, ϵ}

$H_{\mathrm{TM},\epsilon}$

@RickyDemer True, obrigado. Meu argumento funciona apenas para a não semi-decisão (não é?).

Raphael

Respostas:

Não existe uma maneira geral de encontrar uma TM decisiva para $L_k$

Você está certo de que é recursivo porque, sendo um subconjunto do conjunto finito , também é finito. $L_k$ $\Sigma^k$

Você prefere encontrar uma TM decisiva para e sugere algumas técnicas. Mesmo sem entrar em detalhes dessas técnicas e por que elas não funcionam, você não tem nenhuma chance de ter sucesso. $L_k$

A primeira coisa que você deve notar é que o argumento de finitude indica que existe um TM decisivo para o idioma , mas não informa o que é esse TM. É um exemplo de prova não construtiva: você prova que existe uma decisão, mas não pode dizer qual é. $M_k$ $L_k$

Agora, suponha que, dado , você tenha um procedimento para encontrar esse decisivo para o idioma (em vez de apenas provar que ele existe). Então, dada qualquer máquina de Turing , existe um número inteiro tal que , de modo que . Em seguida, você pode usar o procedimento para encontrar uma decisão TM que possa determinar se . Então você tem uma maneira de decidir se o TM pára na entrada vazia. E isso funciona para qualquer TM $k$ $\mathcal P(k)$ $M_k$ $L_k$ $M$ $k'$ $|\langle M\rangle|=k'$ $\langle M\rangle\in \Sigma^{k'}$ $\mathcal P$ $M_{k'}$ $\langle M\rangle\in L_{k'}$ $M$ $M$ . No entanto, isso não é possível, porque é indecidível se um determinado TM pára na entrada vazia. $M$

Portanto, o procedimento não pode existir. $\mathcal P$

Desde que você está procurando uma maneira geral para encontrar o decisivo TM , você não pode ter sucesso porque esse método seria precisamente um procedimento como . $M_{k'}$ $\mathcal P$

Observe que essa prova ainda pode deixar a possibilidade (muito remota) de encontrar um fator para alguns valores específicos de , mas você precisaria identificar com precisão os valores em questão e o método não funcionaria para todos os valores de . Não estou aconselhando você a tentar. $k$ $k$

babou
fonte

Então, basicamente, a única maneira de extrair é recursiva é usar o argumento de finitness?

jon Primeiro-

Tentei prová-lo dessa maneira devido ao fato de que provavelmente não entendi muito bem quando usar esses argumentos sobre o número de configurações e estados possíveis: por exemplo, a questão de provar que L100 = {<M> | M no epsilon não usa mais de 100 lugares na fita} é recursivo, é comprovado executando o TM para as etapas | Q | · 100 · | Gama | ^ 100 +1. Então, alguém pode explicar quando esses argumentos são apropriados - em que tipos de perguntas, talvez alguns exemplos de quando esses argumentos podem ser usados e quando não podem?

jon Primeiro-

Acho que nunca se pode dizer que há apenas uma maneira de provar um resultado. Tudo o que posso dizer é que qualquer prova que funcione para todos os valores de será necessariamente uma prova não construtiva, que não lhe dirá qual é a decisão da TM.

k

$k$

babou 16/07/2015

Em relação à sua tentativa, é um pouco confuso. O tamanho de ⟨M⟩ é igual ao tamanho de um texto de programa. Não está relacionado à quantidade de memória que o programa realmente usará. Para a MT, na verdade é a descrição da MT em um sentido muito abstrato, para que uma descrição muito curta possa corresponder a uma MT extremamente complexa. O tamanho não informa a quantidade de memória usada. Argumentos baseados no tamanho da memória são mais complexos (número exponencial de configurações) e exigem que a memória seja delimitada em tamanho, o que não é o caso aqui.

k

$k$

babou 16/07/2015

Uma prova construtiva geral não precisa induzir um procedimento computável (!) . Por exemplo, a prova canônica é construtiva, de certa forma: pesquisa de tabela, ou seja, codifica o resultado para todas as entradas em . Obviamente, não pode haver algoritmo para construir esta tabela (para infinitamente todo ) pelos motivos mencionados.

P

$\mathcal{P}$

L_{k}

$L_k$

k

$k$

Raphael

Você pode "consertar" sua prova usando a função de castor ocupado. Seja o número máximo de etapas que uma máquina de Turing com tamanho de descrição no máximo executa antes de parar, quando recebe a entrada vazia. Se você conhece (ou mesmo apenas um limite superior em , ou seja, alguns ), poderá resolver os problemas de parada para máquinas de Turing com o tamanho de descrição (e a entrada vazia) executando a máquina fornecida por até para as (ou ). Se não parar nesse ponto, então você sabe que nunca pára. $B_k$ $k$ $B_k$ $B_k$ $T_k \geq B_k$ $k$ $B_k$ $T_k$

Como o problema de parada não é decidível, sabemos que a função não pode ser computável. De fato, nenhuma função computável satisfaz para todos os . Em outras palavras, para qualquer função computável , é o caso de para infinitamente muitos . Grosso modo, cresce mais rápido que todas as funções computáveis. $B_k$ $T_k$ $T_k \geq B_k$ $k$ $f(k)$ $B_k > f(k)$ $k$ $B_k$

Na verdade, usando um diagonalization pode mostrar que faz crescer mais rápido do que toda função computável: para cada computável existe tal que para todo . Isso foi provado pela primeira vez pelo Rado . $B_k$ $f(k)$ $K$ $B_k > f(k)$ $k \geq K$

Yuval Filmus
fonte

Encontrar o número máximo de etapas que a TM pode ser executada antes de entrar em loop definitivamente é exatamente o que eu estava cansando de provar - eu queria argumentar que, uma vez que a TM é do tamanho K, o número máximo de estados que ela pode ter codificado é 2 ^ k e minha lógica era (e me diga se estou errado) - se em uma determinada entrada uma TM com m estados fizer pelo menos m + 1 movimentos (isto é, repete um estado), ela definitivamente fará um loop.

scifie 24/07

E com relação à sua sugestão de encontrar o número máximo de etapas que uma máquina de Turing com tamanho de descrição no máximo k executa antes de parar, o número não deve ser 2 ^ k, como sugeri?

scifie 24/07

Infelizmente você está errado. O que você escreve é verdadeiro para autômatos finitos, mas não para máquinas de Turing, cujo estado inclui uma fita. Tome como exercício a construção de uma máquina de Turing com estados que são interrompidos após etapas (aproximadamente).

n

$n$

2^{2^{n}}

$2^{2^n}$

Yuval Filmus

@ Yuval Filmus, isso está incorreto - os estados da TM não estão relacionados à fita. Os estados de TMs são indicados por Q e é um conjunto finito. Como ele está conectado à sua fita? A fita é para manipulação de entrada e não faz parte dos Estados de uma TM.

Scifie

@scifie O estado inclui tudo o que você precisa para descrever a situação atual em que a máquina está. Isso inclui o estado adequado (ao que você se refere), a localização da cabeça e o conteúdo da fita.

Yuval Filmus

A principal falácia é que você assume que o número de estados de uma TM limita seu tempo de execução (antes da finalização) de alguma forma. Isto é falso.

Caso em questão, existem máquinas de Turing universais , que são TMs finitamente descritas que podem exibir qualquer comportamento, desde o término rápido da execução arbitrariamente longa até a repetição de loop, com a entrada correta.

Em uma nota técnica, as TMs universais são geralmente descritas como tendo dois parâmetros, uma codificação de TM e a entrada para simulá-lo. É fácil mesclá-los em um parâmetro, para que haja, de fato, MTs universais unárias.

Mais especificamente, você ignora a entrada da TM codificada, que pode ser arbitrariamente grande (e complicada). O estado real de uma TM é o produto do estado de controle e do conteúdo da fita, portanto, um argumento combinatório simples baseado no número de estados de controle sozinho não é suficiente. Em particular, uma TM não está em um loop inevitável quando visita algum estado pela segunda vez.

Rafael
fonte

Heh, minha resposta não se aplica aqui, pois consideramos apenas uma entrada fixa (vazia). O tempo de execução é limitado neste caso, cf. A resposta de Yuval.

Raphael

Prova construtiva de decidibilidade do conjunto finito no estilo de problema de parada que não usa a pesquisa de tabela

Respostas:

Não existe uma maneira geral de encontrar uma TM decisiva paraLkLkL_k

Não existe uma maneira geral de encontrar uma TM decisiva para $L_k$