Entradas "problemáticas" sem parar para máquinas de Turing

Question

Vamos começar esta pergunta, definindo para uma máquina de Turing, o conjunto de palavras que não é halt. Definir: $ p (m)={w \ in \ sigma ^ * | m $ não interrompe em $ w \} $

Sabemos que a $ halt $ problema é $ re \ setminus R $ - Assim todos os tm $ m $ que calcula $ halt $ tem uma palavra que não parou, ou seja, $ p (m) \ ne \ vazio $ .

A partir disso, surge a pergunta (simples):

$ q (1): $ "é um problema indecidível se e somente se cada TM que calcula, ele tem uma" classe problemática "não vazia. "Recipiente de matemática"> $ p (m) $ ? " $ ^ {\ espaço (1)} $

Além disso, observe que, para a $ halt $ problema que sabemos que dados $ m $ que calcula-o, há infinitamente muitas entradas que nunca param (eu encorajo a pensar porque isso é assim, antes de prosseguir no post)

Então, similarmente, podemos nos perguntar a versão (ligeiramente) mais difícil da primeira pergunta.

$ q (2): $ "é um problema indecidível IFF a cada tm $ m $ que calcula que tem $ | p (m) |=Aleph_0 $ ? " $ ^ {\ espaço (2)} $

Além disso - vamos fazer uma pergunta ainda mais forte:

$ q (3): $ "Se $ l $ é indecidível, ainda estaremos Capaz de encontrar um conjunto finito de máquinas de turing $ m_1, ..., m_n $ que compute $ L $ e tem $ \ bigcap_ {k \ space=space0} ^ np (m_k) $ finito? E quanto a um infinito conjunto de máquinas de Turing que satisfazem isso? " $ ^ {\ espaço (3)} $

e nossa pergunta final (e meio aberta) serão:

$ Q (4): $ "O que mais podemos entender sobre as máquinas de Turing e seus conjuntos problemáticos?"

Answer 1

Então, vamos começar a enfrentar esses problemas. Como uma nota lateral, eu arranjei as perguntas de tal forma que cada pergunta usa a resposta do que antes dela (e desta forma, eles parecem quase trivial demais para começar com $: $ P).

$ Um (1): $ é bastante trivial de definição. Se $ l $ é indecidível, então não há máquina de Turing que calcula e sempre pára, portanto, todas as máquinas de Turing que computa $ L $ Have $ P (M) \ ne \ emptyset $ . A outra direção também é tão simples quanto esta.

$ A (2): $ vamos assumir $ l $ é indecidível. Se houvesse uma máquina de Turing $ m $ que calcula $ l $ e tem uma classe finita $ P (M) $ , em seguida, vamos construir uma nova máquina $ \ hat M $ de tal forma que ele terá $ P (\ chapéu H)=emptyset $ como se segue (na entrada $ w $ ):

• rejeitar se $ w \ em p (m) $ (isso é possível desde a $ p (m) $ < / span> é finito)
• de outra forma, retorne $ m (w) $

Esta nova máquina, vai parar para cada $ w \ em p (m) $ , mas como para cada $ w \ notin P (M) $ ele será executado $ M $ , e é garantido que ele irá parar em que (uma vez que de outra forma teria sido em $ P (M) $ ), temos que a nova $ \ hat M $ sempre paradas, e aceita $ L $ - contrariando assim o pressuposto. A outra direção é simplesmente derivado de $ Um (1) $ .

$ a (3) $ : para finitos conjuntos de máquinas de Turing, $ m_1 ... m_n $ mostraremos que é impossível ter finito $ \ bigcap_ {k \ space=space0} ^ np (m_k) $ mas indecidível $ l $ . Vamos assumir a contradição que isso não segura. Apenas em $ A (2) $ , vamos construir $ \ hat M $ - mas agora é o suficiente construí-lo de tal forma que $ P (\ hat M)=bigcap_ {k \ espaço=space0} ^ nP (M_k): $

• Executar $ M_1 (w), m_2 (w), ..., M_n (w) $ em paralelo
• Aceite se alguém aceito.

Agora, é óbvio porque $ \ hat m $ aceita $ l $ . Vamos $ w \ notin P (\ chapéu M) $ , então há alguns $ 1 \ le k \ le n $ < / span> tal que $ m_k (w) $ parou, assim $ w \ notin \ bigcap_ {k \ space=space0} ^ np (m_k) $ . Deixe $ w em p (\ hat m) $ , então não parou em nenhuma $ m_k $ , assim $ w \ em p (m_k) $ para todos $ k $ . Concluindo que $ p (\ hat m)=bigcap_ {k \ space=space0} ^ np (m_k) $ é finito e, portanto, da $ a (2) $ não pode existir.

Com relação ao infinito conjuntos de máquinas de Turing, isso é definitivamente possível. Apenas definir para cada $ w \ in \ sigma ^ * $ a máquina $ m_w $ que aceita $ L $ , mas também pára em $ w $ (semelhante à construção em $ A (2) $ ). então $ w \ notin p (m_w) $ portanto $ w \ notin \ bigcap _ {\ hat w} p (m_ \ HAT W) $ e, portanto, não apenas que $ \ bigcap _ {\ hat w} p (m_ \ hat w) $ é finito, também é vazio.

$ a (4): $ Deixe $ l $ é indecidável e $ m_1, m_2 ... $ são máquinas de Turing que aceitam $ l $ e sua interseção do" conjunto problemático "é finito . Se olharmos para a função $ f: \ mathbb {n} \ rightarrow \ sigma ^ * $ definido por $ f ( k)=langle m_k \ rangle $ , então é não computável. Isso segue de $ a (2) $ desde que se essa função fosse computável, teríamos sido capazes de criar uma máquina de Turing $ \ hat M $ com

ontainter "> $ p (\ hat m)=bigcap_k p (m_k) $

Outra ideia que comecei a pensar é o que acontece quando falamos sobre dois idiomas ou mais, em vez de um de cada vez. Deixe $ m_1 $ ser uma máquina para $ l_1 $ e $ M_2 $ para $ l_2 $ . Em seguida, podemos definir uma máquina $ m $ para $ l_1 \ bigcap l_2 $ ou $ l_1 \ bigcock l_2 $ com:

$ p (m)= p (m_1) \ bigcock p (m_2) $ (Nota isto também pode provar propriedades de fechamento na matemática $ \ mathcal R $ )

ou se $ l_1 \ delta l_2 $ é finito, então nós os conjuntos problemáticos de máquinas para os idiomas são praticamente os mesmos (para cada máquina $ m $ Em qualquer um deles podemos encontrar máquinas $ m'_1, m'_2 $ para os outros dois idiomas com o mesmo conjunto problemático)

Embora ainda não tenha escrito uma prova formal do acima. (Honestamente, eu não tenho energia para escrever mais provas como aquele neste grande post) Eu ainda encorajo você a tentar provar que em casa!

Finalmente! Eu acho que (mas ainda sem certeza) podemos obter resultados semelhantes (mas com mais restrições) para análise de complexidade de tempo, se definirmos $ p (m, t) $ por tempo construtível $ t (n) \ ge log (n) $ como o grupo de palavras $ m $ não Halt em dentro de $ t (n) $ etapas. Nesta definição há o problema complicado de constantes, então é mais difícil mostrar aos teoremas definindo novas máquinas (como eles podem fazer apenas um pouco mais de trabalho constante que fará alguma palavra entrar no conjunto problemático, e a notação Big-O aqui é um pouco sem sentido para diferentes constantes)

Se você acha que algo está incorreto, ou só quer adicionar mais - ficarei feliz em fazer alterações.