Verificando o histórico de configuração da máquina de Turing usando o PDA

Question

Eu estou tentando entender a técnica de usar o histórico de configuração em provas.

Para provar que: $ \ { | m \, \, \, é \, \, \, \, \, \, tm \, \, \, e \, \,\, L (m)=sum ^ * \} \ notin re $

dado $ $ Nós construímos uma máquina de Turing que aceita todas as palavras, exceto M Aceitar a configuração em w.(e depois redução simples)

Para provar que: $ \ {

| p é \, \, \, \, \, \, pda \, \, \ e \, \, \, l (p)=sum ^ * \} \ notin re $

Mostramos a mesma prova, apenas que construímos um PDA que aceitam todas as palavras, exceto a configuração de aceitação de m em w.

A capacidade do PDA de determinar se a entrada é uma configuração de aceitação de M sobre W, significa que eu posso simular a execução de M com um PDA?Ou testando se a configuração é uma configuração de aceitação é diferente de uma simulação

Answer 1

PDAs são estritamente mais fracos que TMS.Por exemplo, os PDAs sempre param após precisão $ | w | $ etapas, mas há algoritmos (aka TM) para perguntas que tomam mais etapas do que isso.

classificar uma matriz, por exemplo, teria definitivamente mais do que $ \ ômega (| w | log (| w |)) $ que é maior que $ | w | $ em algum momento.

Não é possível simular a execução de uma máquina em uma palavra como ela simplesmente leva mais tempo!Verificar o histórico de configuração leva menos tempo porque é comprimento é proporcional ao tempo de execução da $ m $ em $ W $ .