As máquinas de Turing de fita única com entrada protegida contra gravação reconhecem apenas idiomas regulares

Aqui está o problema:

Prove que as Máquinas de Turing de fita única que não podem gravar na parte da fita que contém a sequência de entrada reconhecem apenas idiomas regulares.

Minha idéia é provar que essa TM específica é equivalente a um DFA.

O uso desta TM para simular o DFA é muito simples.

No entanto, quando quero usar esse DFA para simular a MT, encontro o problema. Para a transição de TM $\delta(q,a)=(q',a,R)$ , o DFA pode simular definitivamente lendo a fita à direita e fazendo a mesma transição de estado.

Para $\delta(q,a)=(q',a,L)$ , não consigo descobrir como usar esse DFA ou NFA para simular o movimento para a esquerda porque o DFA lê apenas para a esquerda e não possui pilha ou algo para armazenar.

Devo considerar outra maneira? Alguém poderia me dar algumas dicas? Obrigado.

Introdução

Eu pensei que poderia haver um erro na declaração original da pergunta, e o OP não estava mais por perto para perguntar. Portanto, presumi que a fita fosse somente leitura em todos os lugares e escrevi uma primeira prova com base nessa suposição, motivada pelo fato de a TM ter poder total de Turing fora da parte de entrada da fita, se puder gravá-la, o que induz a falsa crença de que ele pode reconhecer qualquer linguagem ER.

No entanto, esse não é o caso: a restrição de gravação na parte de entrada da fita implica que apenas informações finitas podem ser extraídas da entrada, limitadas pelo número de estados de entrada e saída dessa parte da fita (combinada com lado de entrada e saída). O InstructorA deve ser creditado por comentar em um comentário que há um problema no reconhecimento de qualquer idioma RE, pois não é possível fazer uma cópia da entrada sem NUNCA gravar na área de entrada original,

Por isso, escrevi uma segunda prova que assume que apenas a seção de entrada da fita é somente leitura, sendo o restante permitido para leitura e gravação.

Estou mantendo as duas provas aqui, pois a primeira me ajudou a encontrar a solução, mesmo que não seja necessário entender a segunda prova, é mais complexa e é subsumida pela segunda prova. Pode ser pulado. No entanto, a prova mais fraca tem a vantagem de ser construtiva (para obter um FSA equivalente à Máquina de Turing), enquanto o resultado mais geral não é construtivo.

No entanto, estou dando primeiro o último e mais poderoso resultado. Estou um pouco surpreso por não ter conseguido encontrar esse resultado, mesmo sem provas, em outros lugares da rede ou perguntando a alguns usuários competentes, e qualquer referência ao trabalho publicado seria bem-vinda.

Conteúdo:

• Máquinas de Turing que não substituem a entrada aceitam apenas idiomas regulares. Esta prova não é construtiva.

• Máquinas de Turing com fitas somente leitura aceitam apenas idiomas comuns. Pode ser ignorado como incluído na prova anterior, mas usa uma abordagem diferente, que tem a vantagem de ser construtiva.

Máquinas de Turing que não substituem a entrada aceitam apenas idiomas regulares

Lembramos que, embora a TM não substitua sua entrada e, portanto, seja apenas lida em sua entrada, a TM pode ler e escrever no restante da fita . A prova se baseia no fato de que o comportamento observacional da MT em relação a uma entrada desconhecida pode produzir apenas um número finito de casos diferentes. Portanto, embora a TM possua o poder total de Turing apenas contando com o restante de sua fita, suas informações na entrada, que podem ser qualquer string em , são finitas, portanto, podem ser computadas apenas em um número finito de casos diferentes. Isso fornece uma visão diferente do caráter finito das linguagens regulares, comportamentais e não estruturais.$\Sigma^*$

Assumimos que a TM aceita quando entra em um estado de aceitação.

Prova.

Definimos uma computação restrita de entrada (IRC) como uma computação ( somente leitura) da TM, de modo que o cabeçote da TM permaneça na parte de entrada da fita, exceto possivelmente para a última transição que pode movê-la para uma célula imediatamente no esquerda ou direita da área de entrada.

Os cálculos restritos da entrada esquerda são um IRC que começa no símbolo mais à esquerda da entrada. Um cálculo de entrada restrita à direita é um IRC que inicia no símbolo mais à direita da entrada.

Primeiro, provamos que, para cálculos restritos de entrada esquerda que começam no estado , os seguintes idiomas são regulares:$p$

• o idioma das seqüências de entrada, de modo que exista um cálculo restrito à entrada esquerda, iniciando no estado p , que termina na primeira célula à esquerda do símbolo de entrada mais à esquerda no estado q ;$K_{Lp\to Lq}$$p$$q$

• o idioma das seqüências de entrada, de modo que exista uma computação restrita à entrada esquerda, iniciando no estado p , que termina na primeira célula à direita do símbolo de entrada mais à direita no estado q ;$K_{Lp\to Rq}$$p$$q$

• o idioma de cadeias de entrada de modo que exista uma computação restrita à entrada esquerda, iniciando no estado p , que atinge um estado de aceitação.$A_{Lp}$$p$

E da mesma forma, para cálculos restritos de entrada correta começando no estado , os seguintes idiomas definidos da mesma forma são regulares: K R p → L q , K R p → R q e A R p .$p$$K_{Rp\to Lq}$$K_{Rp\to Rq}$$A_{Rp}$

As 6 provas baseiam-se no fato de que os autômatos de estado finito não-determinístico (2NFA) de duas vias reconhecem conjuntos regulares (ver Hopcroft + Ullman 1979, pp 36-41 e execução 2.18 página 51). Um 2NFA funciona como uma TM somente leitura em uma fita limitada à sua entrada, começando inicialmente pelo símbolo mais à esquerda e aceitando indo além da extremidade direita em um estado de aceitação.

Em cada um dos 6 casos, a prova é feita através da construção de um 2NFA que imita os cálculos restritos de entrada, mas com algumas transições extras para garantir que ele possa iniciar na célula mais à esquerda e aceitar o idioma saindo do extremo direito em uma aceitação. Estado. Para o Nos idiomas, o estado de aceitação original da TM é alterado para estados que levam a um cálculo de não aceitação interrompido. Em dois casos, pode ser necessário adicionar uma célula extra com um novo símbolo de guarda à esquerda para detectar cálculos de MT que terminariam na extremidade esquerda, para fazê-los terminar na extremidade direita.$K_{??\to ??}$

Essas línguas são definidos para todas as combinações de estados e q da máquina de Turing originais. Eles representam tudo o que pode ser observado (daqui conhecido e computado) da entrada pela TM.$p$$q$

Se é o número de estados, definimos 4 k 2 idiomas K ? ? → ? ? e 2 k idiomas A ? ? , portanto, um total de 4 k 2 + 2 k idiomas. Na verdade, alguns desses idiomas podem ser iguais.$k$$4k^2$$K_{??\to ??}$$2k$$A_{??}$$4k^2+2k$

Estes são os únicos cálculos possíveis de entrada restrita da TM, começando em uma extremidade da entrada. Portanto, os cálculos induzidos por cada sequência de entrada (fora da seção de entrada da fita) são caracterizados pelo conjunto desses idiomas aos quais a entrada pertence ou não, portanto, por uma interseção de cada um desses idiomas de ou seu complemento em Σ ∗ . Todas essas interseções são intersecções finitas de idiomas regulares r 4 k 2 + 2 k , ou seu complemento também regular e, portanto, regular.$4k^2+2k$$\Sigma^*$$4k^2+2k$

$\mathcal P$$\Sigma^*$$2^{4k^2+2k}$

$u$$v$$\mathcal P$$u$$v$$\mathcal P$

Para ser bem completo, pulamos o caso da string de entrada vazia. Nesse caso, temos apenas uma TM normal, que pode ler ou escrever em qualquer lugar. Se atingir um estado de aceitação, a cadeia vazia está no idioma, caso contrário, não está. Mas isso tem pouco efeito no fato de a linguagem reconhecida ser regular.

Obviamente, não é decidido se uma classe de equivalência está ou não no idioma (o mesmo vale para a cadeia vazia). Esta é uma prova não construtiva.

QED

Máquinas de Turing com fitas somente leitura aceitam apenas idiomas regulares

Isso é incluído no resultado anterior. Ele é mantido, pois usa uma abordagem diferente, provavelmente menos elegante, e me ajudou a encontrar a prova anterior, entendendo o que importa. Mas pode muito bem ser ignorado pelos leitores. No entanto, uma vantagem dessa prova é que é uma prova construtiva que produz uma FSA aceitando o idioma. Um esboço de uma prova semelhante é dado por Hendrik Jan em sua resposta a uma pergunta semelhante anterior , que assume que toda a fita era somente leitura.

$\Box$

O primeiro passo da prova é mostrar que a cabeça nunca precisa sair da área de entrada da fita. Assim, analisamos o que acontece quando a cabeça se move para fora do símbolo de entrada mais à direita. A análise ao sair da mais à esquerda é idêntica.

$q$

1. o TM continua computando para sempre, sem que a cabeça volte à parte de entrada da fita;

2. a MT atinge um (a) aceitação ou (b) para em um estado de não aceitação;

3. $r$

$q$

$\Box$$1$$0$

$0$

Representamos a parte relevante do controle de estado finito por um gráfico direcionado em que os vértices são os estados da MT e as bordas são as transições em branco, com um peso +1 ou -1, dependendo do movimento da cabeça direita ou esquerda.

$A_R$$q$

$E_R$$(q,r)$$-1$$q$$r$

$\Box$

$q_A$

$p,a\mapsto R,q$$p,a\mapsto R,q_A$$q\in A_R$

$p,a\mapsto R,q$$(q,r)\in E_R$$p,a\mapsto S,r$$S$

$a$$F_a=\{(p,r)\mid \text{ there is a dummy transition } p,a\mapsto S,r\}$$F_a^*$$F_a$$r,a\mapsto L,s$$(p,r)\in F_a^*$$p,a\mapsto L,s$

$+1$$-1$

$q_A$

Agora temos que fazer algumas mudanças cosméticas, de modo a fazer com que essa TM se comporte exatamente como um NDA bidirecional (a aceitação é apenas saindo da entrada à direita para um estado de exceção). Então, podemos confiar na equivalência de conhecimento entre 2-NDA e FSA (veja, por exemplo, Hopcroft + Ullman 1979, página 40) para obter a prova de que o idioma é regular.

QED

Mover para a esquerda ou para a direita não é um problema, pois os autômatos finitos bidirecionais reconhecem exatamente os idiomas regulares (isso não é óbvio). No entanto, se a sua TM puder escrever fora da parte da fita da palavra de entrada, acho que você poderá usar essa parte da fita para reconhecer em idiomas comuns. Talvez eu não entenda claramente a pergunta.