Parando o problema sem auto-referência

No problema de parada, estamos interessados se existe uma máquina de Turing que pode dizer se uma determinada máquina de Turing pára ou não em uma determinada entrada . Geralmente, a prova começa assumindo que existe umEm seguida, consideramos um caso em que restringimos ao próprio e derivamos uma contradição usando uma instância de um argumento diagonal. Estou interessado em como seria a prova se nos for dada a promessa de que ? E a promessa , onde é funcionalmente equivalente a ? $T$ $M$ $i$ $T$ $i$ $M$ $i \not = M$ $i \not = M^\prime$ $M^\prime$ $M$

computability undecidability halting-problem bellpeace
fonte

Dica: mesmo que não precise responder corretamente a perguntas sobre si mesmo ou sobre o equivalente de a ele, ainda podemos alimentar um equivalente e ver o que ele faz. Como não é calculável se é equivalente a , não será capaz de dizer que obteve algo equivalente a si próprio.

M

$M$

M^{'}

$M'$

M^{'}

$M'$

M^{'}

$M'$

M

$M$

M

$M$

Andrej Bauer

@AndrejBauer Essa foi apenas uma dica que você me deu e eu devo resolver meu problema real usando essa dica? Estou um pouco confuso, já que você relaxa o problema dizendo "não é necessário", onde, em meu ambiente, tenho a promessa de que não será alimentado com um equivalente . Basicamente, eu gostaria de ver qualquer tipo de "auto-referência" que torne os problemas indecidíveis. Eu pensava que esse é o caso quando se fala de lógica e incompletude.

M

$M$

M^{'}

$M^\prime$

bellpeace

Você pode quebrar a promessa e alimentar como quiser. Não posso dizer que você quebrou a promessa, de qualquer maneira. Se você acha que isso é trapaça, alimentarei coisas que não são equivalentes a porque são como mas com todas as entradas alteradas em , ou algo assim.

M

$M$

M

$M$

M

$M$

M

$M$

1

$1$

Andrej Bauer

Na verdade, suas perguntas não estão bem formuladas. Você deve descrever a prova real que tem em mente e especificar o que exatamente deseja evitar. Eu não acho que você quer dizer , mas outra coisa.

i \neq M

$i \neq M$

Andrej Bauer

Respostas:

Suponha que HALTS é uma TM que lê sua entrada como um par e , onde é uma codificação TM e é qualquer entrada para essa TM. $M$ $x$ $M$ $x$

Sua pergunta é se o que aconteceria se nós assumimos pára resolvido o problema da parada para todas as entradas tal que não é uma codificação de uma TM que é funcionalmente equivalente a . $\langle M,x \rangle$ $x$ $M$

Eu afirmo que isso implica uma contradição. Eu vim com isso no local, então eu recebo toda e qualquer crítica à minha prova. A idéia da prova é que, em vez de diagonalizar algo em si mesmo, criamos duas MTs mutuamente recursivas que se comportam de maneira diferente em algumas entradas (portanto, não são funcionalmente equivalentes), mas causam contradições.

Sejam e duas TMs mutuamente recursivas (ou seja, podemos simular, imprimir, etc., a descrição de dentro do programa de e vice-versa). Observe que podemos fazer TMs recursivas mutuamente a partir do teorema da recursão. $D_1$ $D_2$ $D_2$ $D_1$

Defina e seguinte maneira: na entrada , se (10 escolhidos arbitrariamente), então aceita e loops. (Portanto, eles não são funcionalmente equivalentes). $D_1$ $D_2$ $x$ $|x| < 10$ $D_1$ $D_2$

Entrada dada com , defina para simular HALTS em e interrompa se parar ou faça um loop se loop. $x$ $|x| \ge 10$ $D_1$ $\langle D_2, x \rangle$ $D_2$ $D_2$

Entrada dada com , defina para simular HALTS em e faça um loop se parar ou parar se loop. $x$ $|x| \ge 10$ $D_2$ $\langle D_1, x \rangle$ $D_1$ $D_1$

Observe que, para qualquer com , (x) pára ou faz um loop. Se na entrada x, sabemos que HALTS ( , x) determinou que pára na entrada x. No entanto, na entrada x implica que HALTS ( , x) faça um loop. $x$ $|x| \ge 10$ $D_1$ $D_1$ $D_2$ $D_2$ $D_2$ $D_1$

Se loops de entrada , a contradição da mesma forma. $D_1$ $x$

Isso é uma contradição, a menos que seja uma codificação para uma máquina de turing funcionalmente equivalente a ou , caso em que o HALTS tem um comportamento indefinido. No entanto, foi escolhido arbitrariamente entre todas as cadeias de tamanho maior que . Portanto, resta mostrar que existe uma máquina de turing com uma codificação de tamanho maior que 10 que se comporta de maneira diferente de e . Podemos construir essa máquina trivialmente. QED. $x$ $D_1$ $D_2$ $x$ $10$ $D_1$ $D_2$

Pensamentos?

Kurt Mueller
fonte

Por que você precisa garantir que e não sejam funcionalmente equivalentes?

D_{1}

$D_1$

D_{2}

$D_2$

bellpeace

Acho que você está certo de que isso não é necessário. Minha intenção original era diagonalizar em paradas ( )

⟨ D_{1}, D_{2} ⟩

$\langle D_1, D_2 \rangle$

Kurt Mueller

Sem isso, a prova é mais elegante, mas de qualquer maneira parece boa para mim e é exatamente o que eu precisava.

bellpeace

Você ainda não está fora de perigo. Você se depara com o mesmo problema, só que agora fornece a ele um TM, como entrada, onde você escolheu para ser funcionalmente equivalente a (diga que você adiciona uma nova regra a para que abertura de se mova estão um passo à direita, um passo à esquerda e, caso contrário, você não faz alterações). Você ainda vai se deparar com uma contradição. Você pode tentar eliminar todas as TMs equivalentes a , mas esse é um conjunto indecidível. $M'$ $M'$ $M$ $M$ $M'$ $M$

Update . Corrija um esquema de codificação em que denota a descrição desse esquema de uma TM e suponha que você tenha uma TM, em que $\langle\,M\,\rangle$ $M$ $H$

$H(\langle\,M\,\rangle, x)$ é indefinido quando é a codificação de uma TM que calcula a mesma função parcial que (ou seja, e são funcionalmente equivalentes). $x$ $H$ $x$ $H$
Para todas as outras entradas, retorna true se e somente se parar. $H(\langle\,M\,\rangle, x)$ $M(x)$

Agora, a construção usual de diagonalização ainda resulta em uma contradição. Defina um TM por $Q$

Q(x)=
  if H(<Q>, x) = false
    return true
  else
    loop forever

Claramente e são funcionalmente diferentes, então podemos deixar e descobrir que pára se, e somente se, não parar. não pode haver nenhuma TM tais . $Q$ $H$ $x=\langle\,Q\,\rangle$ $Q(\langle\,Q\,\rangle)$ $H$

Rick Decker
fonte

E suponha que eu tenho uma promessa de que não sou uma MT funcionalmente equivalente a ? Talvez eu possa estender minha pergunta no OP?

i

$i$

M

$M$

bellpeace

Suponha que você receba tal promessa; Eu sei que não é computável. Eu atualizei o OP.

bellpeace

@bellpeace: Como você define isso?

$\:$

$\;\;\;\;$

Entrada: um par de números inteiros de tal modo que não representam uma TM funcionalmente equivalente a TM representado por . Saída: se parar em , caso contrário. Esse problema é decidível?

(M, i)

$(M, i)$

i

$i$

M

$M$

1

$1$

M

$M$

i

$i$

0

$0$

bellpeace

@RickyDemer Sim, duas TMs são consideradas funcionalmente equivalentes se calcularem a mesma função parcial. Observe que, como Andrey apontou, que, embora determinar se e sejam equivalentes seja indecidível, ainda podemos considerar o problema em que recebemos a promessa de que dois TMS de entrada não são equivalentes, como exemplifiquei acima.

M

$M$

M^{'}

$M^\prime$

bellpeace