Encontrei o seguinte problema neste pdf :
Dado um TM M, se M alguma vez escreve um símbolo não em branco quando iniciado na fita vazia.
A solução dada é a seguinte:
Deixe a máquina escrever apenas em branco símbolo. Então, seu número de configurações no cálculo de com em w é q × 2, onde q é o número de estados de M; o fator 2 é para as escolhas re. a direção do movimento das cabeças; não há nenhum fator para o símbolo escrito porque ele está sempre em branco. Portanto, o problema é decidível, decidido pela seguinte máquina: entrada (M, w), execute M em w para q × 2 passos; se M alguma vez escrever um símbolo não em branco, pare com a resposta sim; se M nunca escrever um símbolo que não seja em branco, pare sem resposta
Dúvidas:
Q1. Como ter certeza de que todas as configurações de qx 2 acontecerão ao executar qx 2 etapas em w? Algumas configurações podem ser repetidas em qx 2 etapas.
Q2. A pergunta diz “quando iniciada no fita vazia “, mas a resposta tentou simular TM na string não vazia w. Como isso faz sentido?
Resposta
Q1: Um estado pode se repetir. A questão é que, se um estado se repetir e nenhum símbolo de não vazio tiver sido escrito, você saberá que a máquina de Turing nunca irá parar, pois está necessariamente presa no ciclo de alguns dos estados encontrados até agora. Como nenhum dos estados do ciclo fez com que a TM escrevesse um símbolo não vazio, a TM nunca escreverá um símbolo não vazio.
Após $ 2q $ etapas, ou um símbolo não em branco foi escrito e você pode responder “sim”, ou todos os símbolos escritos estavam em branco e (pelo menos) um estado deve ter sido encontrado duas ou mais vezes, o que significa que você pode responder “não”.
Q2: Meu palpite é que $ w $ é definido em algum lugar para ser a string vazia. Se a TM pode ser iniciada com alguma string arbitrária $ w $ , então uma variação da solução acima ainda funciona. Suponha que o cabeçalho da TM comece no início de $ w $ . O número de estados aumenta por um fator de no máximo $ 1+ | w | $ a fim de levar em consideração todos os estados possíveis da fita (se apenas símbolos em branco forem escritos , a fita sempre conterá um dos $ 1+ | w | $ sufixos de $ w $ ). Se o cabeçalho puder começar em qualquer lugar, esse fator será no máximo $ 1+ | w | ^ 2 $ .
Comentários
- No primeiro trimestre. Você quer dizer " ou um símbolo não em branco foi escrito e você pode responder sim … e você pode responder não "? Porque a pergunta pergunta " se M alguma vez escreve um símbolo que não seja em branco ". No 2º trimestre. Não obteve " no número de estados correspondente ao número de subconjuntos de posições de w que foram substituídos por um símbolo em branco "
- Você está certo. Eu fixei minha resposta. Eu também esclareci a última parte.