Classe de idiomas reconhecíveis pelas TMs de três estados de fita única

9

I têm durante algum tempo sido curioso sobre máquinas de Turing com exactamente uma fita e exactamente três estados (ou seja, o estado inicial q0 , o estado aceitar qaccept , e o estado rejeitar qreject ). Observe que eu permito alfabetos de fita arbitrários (finitos) (ou seja, o alfabeto da fita não está restrito a igual ao alfabeto de entrada).

Por conveniência, chame a classe de idiomas reconhecíveis por essas TMs C3 . Eu tenho várias perguntas sobre esta classe:

  1. Tem C3 sido previamente estudada?
  2. É C3 conhecido para igualar quaisquer outras classes complexidade / computabilidade de interesse?
  3. A classe C3 robusta às mudanças no modelo. Por exemplo, se as TMs usadas podem permanecer no local durante uma única transição (em vez de sempre se mover para a esquerda ou direita) ou se a fita é feita para ser infinita nas duas direções, em vez de apenas para a direita, a classe de idiomas reconhecíveis pela alteração de TMs com 1 fita e 3 estados?
  4. Como é que C3 referem-se à classe de linguagens regulares, Regular ? (Em particular, é toda linguagem regular em C3 ?)

Uma pesquisa (bastante superficial) trouxe apenas essa postagem cs.stackexchange que é relevante, mas não responde minhas perguntas e este artigo , que não li em detalhes o suficiente para garantir que se refere exatamente à classe vez de uma classe semelhante mas diferente (as reivindicações de papel para provar que (1) cada idioma em C 3 é determinável e (2) que C 3 e R e g u l a rC3C3C3Regularsão classes distintas com interseção não vazia). Conforme apontado nos comentários da publicação cs.stackexchange, esses tipos de TMs podem ser considerados autômatos celulares muito específicos, então talvez alguém que conheça a literatura sobre a teoria dos autômatos celulares possa ajudar.

Mikhail Rudoy
fonte
11
Se você tiver apenas um estado sem terminação e uma fita (fita de entrada), sua máquina não poderá se lembrar de nada que tenha lido. Portanto, ele pode aceitar ou rejeitar exatamente as entradas que contêm símbolos definidos do alfabeto de entrada.
David G
4
A máquina não consegue se lembrar do que leu, mas pode reescrever o que leu com outra coisa. Então, eu realmente não vejo por que a caracterização que você dá estaria correta. (ou seja, consigo pensar em uma máquina simples que aceita e rejeita 011 ; aqui o comportamento não é determinado inteiramente por quais símbolos estão na entrada). 01011
Mikhail Rudoy 01/08/19
11
Você está certo, minha intuição estava errada.
David G

Respostas:

7

A fera é extremamente poderosa , por exemplo, podemos construir uma TM que aceita todas as sequências do formulárioM

LY={r0n1mAmn}

e rejeita todas as strings do formulário

LN={r0n1mAm>n}

A idéia é transformar o primeiro em R e, em seguida, deixar a cabeça chegar ao meio da corda e fazer um zig-zag "sem estado"; se atingir A antes de R , aceita.rRAR

Descrição informal:

  • em escreva R e mova para a direita (prepare-se para rejeitar)rR
  • em escreva ce mova-se para a direita (movendo-se em direção ao centro)0c
  • em escreva > e mova para a esquerda (marque 1 , prepare-se para o próximo cruzamento da esquerda para a direita e vá para a esquerda)1>1
  • em escreva < e mova para a direita (marque 0 , prepare-se para o próximo cruzamento da direita para a esquerda e vá para a direita)c<0
  • em write > e vá para a esquerda (cruzamento da esquerda para a direita, prepare-se para o próximo da direita para a esquerda)<>
  • em escreva < e vá para a direita (cruzamento da direita para a esquerda, prepare-se para o próximo da esquerda para a direita)><
  • em aceitar, em R rejeitarAR
  • em branco rejeitarb

Exemplo:

  :r 0 0 0 1 1 A
   R:0 0 0 1 1 A
   R c:0 0 1 1 A
   R c c:0 1 1 A
   R c c c:1 1 A
   R c c:c > 1 A
   R c c <:> 1 A
   R c c < <:1 A
   R c c <:< > A
   R c c:< > > A
   R c:c > > > A
   R c <:> > > A
   ...
   R c < < < <:A ACCEPT

Essa técnica de zig-zag é usada na menor máquina de Turing Universal de dois estados (possui 18 símbolos) construída por Rogozhin (Rogozhin 1996. TCS, 168 (2): 215-240).

Alguma atenção deve ser prestada para provar que pára em todas as entradas (observe que ele rejeita na entrada em branco e todos os símbolos sem interrupção "convergem" para < ou > que não podem levar a um loop infinito).M<>

Como comentado por DavidG, a linguagem reconhecidos por M é um subconjunto de G Y (isto é, L YG ( M ) ), mas que não contém qualquer cadeia de L N (ou seja, G ( M ) L N = ) e - como comentado por MikhailRudoy - isso é suficiente para provar que L ( M ) não é regular.L(M)MLYLYL(M)LNL(M)LN=L(M)

De fato, se é regular, também L ( M ) { r 0 1 A } = L Y = { r 0 n 1 m A m n } seria regular (o que não é uma aplicação simples do lema de bombeamento); levando a uma contradição.L(M)L(M){r01A}=LY={r0n1mAmn}

Então não é regular .L(M)

... Mas como todos os super-heróis tem calcanhar de um Achille: ela não pode sequer reconhecem o normal:C3

L={12n}

Informalmente, ele pode usar apenas o mais à esquerda . . . ( b é o símbolo em branco) ou a névoa direita 1 b . . . como um gancho e "expandir" na outra direção; mas o último aceitar ou rejeitar não pode ser sobre o símbolo em branco do lado da frente, de modo que pode ser feita apenas na parte interna das 1 s e a partir de uma entrada de tempo suficiente que pode ser "fingiu" esticá-lo por um.b1...b1b...1

Finalmente - depois de ler o jornal - Posso confirmar que o TM um estado descrito no que corresponde ao seu class ... (assim nada de novo aqui :-) ... eo langauge utilizado pelo autor para provar que ele contém idiomas não regulares é muito parecido com o meu.C3

Marzio De Biasi
fonte
11
Eu gosto muito da resposta (+1). No entanto, a MT descrita descreve um idioma diferente. É, por exemplo, aceita também cordas rrrrr00011AAAA, r000000r0000r0000r00011A, r00011A11111111 (após um poderia ser qualquer coisa, em vez de uns) ...
David G
@DavidG: Você está certo! Eu não pensei muito nisso ... eu tento consertar.
Marzio De Biasi
4
Na verdade, mesmo através de não é o idioma reconhecido pela MT descrita, esse idioma definitivamente não é regular: se essa MT é M , então L ( M ) r 0 1 A = L, então uma breve prova por contradição (se G ( M ) é regular, então G ( M ) r 0 * 1 * A = G também será regular; contradição) pode mostrar que G ( H ) não é regular.LML(M)r01A=LL(M)L(M)r01A=LL(M)
Mikhail Rudoy 02/08/19
3
@MikhailRudoy: yes! Eu tive a mesma ideia. Abri a história para editar a resposta e vi seu comentário. Vamos ver se eu posso reescrever a resposta tendo em conta o seu comentário ...
Marzio De Biasi
5

Subestimei o poder do ... na verdade, não está muito longe da hipercomputação !C3

(Postei isso como uma resposta separada para melhor clareza)

Podemos construir uma máquina de Turing de estado único que aceite as cadeias de caracteres da forma:M

LY={a0n1mRm2n}

e rejeita cadeias de caracteres do formulário:

LN={a0n1mRm<2n}

A idéia e a construção são semelhantes às da resposta anterior: transforme o primeiro em A , deixe a cabeça chegar ao meio da corda e faça um zig-zag "sem estado", mas as transições "implementam" um "contador binário "na primeira metade desta maneira: em Z (Zero), gire a cabeça de volta para a direita e converta o Z em S (Um) na próxima vez que a cabeça alcançar o S , transforme-o em a ) e deixe a cabeça Mova para a esquerda; quando os alcances cabeça as ) transformá-lo em um Z . A segunda metade da corda se comporta como um contador unário.aAZZSS))Z

As transições são:

  • em escreva R e mova para a direita (prepare-se para rejeitar)rR
  • em escreva Z e mova para a direita (movendo-se em direção ao centro, ajuste o contador binário para 0 ..)0Z
  • em escreva > e mova para a esquerda (marque 1 e diminua o contador unário, prepare-se para a próxima travessia da esquerda para a direita e volte para o contador binário)1>1
  • em escreva < e vá para a direita (cruzamento da direita para a esquerda da segunda metade da string, prepare-se para a próxima esquerda para a direita)><
  • em write > e vá para a esquerda (cruzamento da esquerda para a direita da segunda metade da string, prepare-se para a próxima da direita para a esquerda)<>
  • em escreva S e mova para a direita (transforme o dígito em um e volte para a direita em direção ao contador unário)ZS
  • em write ) e mova para a esquerda (limpe o dígito e deixe a cabeça se mover para a esquerda como um "carry", prepare-se para a próxima esquerda para a direita da primeira parte)S)
  • on escreva Z e mova-se para a direita (defina o zero que causará o salto e deixe a cabeça se mover para a direita))Z
  • em aceitar, em R rejeitarAR
  • em branco rejeitarb

Exemplo:

 :a 0 0 0 1 1 1 1 1 1 1 1 R
  A:0 0 0 1 1 1 1 1 1 1 1 R
  A Z:0 0 1 1 1 1 1 1 1 1 R
  ...
  A Z Z Z:1 1 1 1 1 1 1 1 R
  A Z Z:Z > 1 1 1 1 1 1 1 R
  A Z Z S:> 1 1 1 1 1 1 1 R
  A Z Z S <:1 1 1 1 1 1 1 R
  A Z Z S:< > 1 1 1 1 1 1 R
  A Z Z:S > > 1 1 1 1 1 1 R
  A Z:Z ) > > 1 1 1 1 1 1 R
  A Z S:) > > 1 1 1 1 1 1 R
  A Z S Z:> > 1 1 1 1 1 1 R
  ...
  A Z S:Z > > > 1 1 1 1 1 R
  ...
  A Z S S < < <:1 1 1 1 1 R
  ...
  A S:) ) > > > > 1 1 1 1 R
  ...
 :A ) ) ) > > > > > > > > R ---> ACCEPT

Alguma atenção deve ser prestada para provar que em todas as entradas (observe que ela rejeita na entrada em branco e todos os símbolos sem interrupção "circulam" por ( , S , Z ou < , > que não podem levar a um loop infinito )M(,S,Z<,>

A linguagem é um subconjunto de G Y ( L YG ( M ) ) e que não contêm cadeias de L N ( G ( M ) L N = ).L(M)LYLYL(M)LNL(M)LN=

Suponha que seja livre de contexto e , ao fechar as propriedades das CFLs, cruze-a com a linguagem regular { r 0 1 A } produza uma linguagem CF:L(M){r01A}

L(M){r01A}={a0n1mRm2n}=LY

Mas por uma simples aplicação do Lema de Ogden para CFL podemos provar que : basta escolher um tempo suficiente s L Y e marcar todos os 0 s; pelo menos um zero pode ser bombeado e qualquer que seja o número de 1 s na coluna de bombeamento, o crescimento exponencial de 2 n leva a uma cadeia L Y ).LYCFLsLY01s2nLY

Então não é livre de contexto .L(M)

... agora estou me perguntando se essa é outra resposta "reinventando a roda" ou se é um novo (pequeno) resultado.

Marzio De Biasi
fonte
Bem, o idioma aqui é computável em classes tão baixas quanto coNLOGTIME, portanto, não requer exatamente hipercomputação. (Na verdade, e G N podem ser separados mesmo em dlogtime.)LYLN
Emil Jerabek
@ EmilJeřábek: Eu disse "não muito longe" ... não reprimir as ambições de que pequena classe ... :-)
Marzio De Biasi
2

Nesta resposta, assume-se que as máquinas de Turing possuem fitas infinitas nos dois sentidos. As reivindicações não se aplicam a fitas infinitas unidirecionais.

Deixe-me primeiro definir a classe de linguagens como a classe de todas as línguas decidível por uma fita de máquinas de Turing com 3 estados ( C 3 foi definida como a classe de linguagens reconhecíveis por máquinas de Turing de uma fita com 3 estados). Eu introduzi a classe C ' 3 porque, na minha resposta original, inconscientemente troquei as classes C 3 e C ' 3 (eu apenas considerei a classe C ' 3 ).C3C3C3C3C3C3

Esta resposta é mais um complemento para as respostas do @MarzioDeBiasi. Ele mostrou que as classes e C 3 não estão contidas em CFL e, portanto, contêm idiomas bastante interessantes. No entanto, como mostrarei neste post, cada idioma L em C 3 tem a propriedade que o conjunto { 1 n ; n N{ 0 } } é ou em L ou em seu complemento G C . Assim, C 3C3C3LC3{1n;nN{0}}LLCC3também é muito restritivo, por exemplo. ele contém apenas idiomas unários triviais , { ε } , { 1 n ; n N } e { 1 n ; n N{ 0 } } . A classe C 3 contém idiomas um pouco mais unários. No entanto, é vantajoso que se L C 3 e 1 nG para n 1 , então 1{}{ε}{1n;nN}{1n;nN{0}}C3LC31nLn1 para todos os m n . 1mLmnUm corolário simples é que nem todas as linguagens regulares estão em , nem em C ' 3 . Além disso, o idioma{1}não está na C 3 , nem em C ' 3 .C3C3{1}C3C3


Para a alegação (em negrito) sobre , basta provar que uma máquina de Turing M de uma fita com 3 estados que sempre interrompe ou aceita ou rejeita todas as seqüências de { 1 n ; n N{ 0 } } . Suponha-se que uma cadeia da forma 1 n , n N{ 0 } , é dado a M . Existem três casos:C3M{1n;nN{0}}1nnN{0}M

1) Quando lê 1, ele aceita ou rejeita.M

2) Quando lê 1, move a cabeça para a esquerda. MSe quisermos que pare nessa entrada, ele deve aceitar, rejeitar ou mover para a direita no símbolo em branco. Portanto, nunca visita a célula à direita da célula inicial da fita. Se assim fosse, seria executado para sempre na entrada 1.M

3) Quando lê 1, move a cabeça para a direita. MSegue-se que após passos, o conteúdo da fita é A n em que A é um símbolo do alfabeto da fita ea cabeça de M é no símbolo branco da esquerda para a direita da última A . Se quisermos que M pare nessa entrada, ele deve aceitar, rejeitar ou mover para a esquerda no símbolo em branco. Como no caso 2), o chefe de M agora nunca visitará a célula diretamente à esquerda do A mais à direita . Se assim fosse, M seria executado para sempre na entrada 1.nAnAMAMMAM

É claro que nos três casos aceita todas as cadeias do conjunto { 1 n ; n N{ 0 } } ou rejeita todos eles.M{1n;nN{0}}


A prova da reivindicação (em negrito) sobre segue a mesma linha tal como acima. Tomamos uma máquina de Turing M de três estados e fita única que aceita uma string 1 n para alguns n 1 . Suponha que M receba uma entrada 1 m para m n . Temos que provar que M aceita essa entrada. Temos 3 casos:C3M1nn1M1mmnM

1) Quando lê 1, ele aceita.M

2) Quando lê 1, move a cabeça para a esquerda. MComo aceita a entrada 1 n , ela deve aceitar ou mover para a direita no símbolo em branco. Por isso, nunca visitas os n º célula à direita da célula inicial. Se assim fosse, seria executado para sempre na entrada 1 n .M1nn1n

3) Quando lê 1, move a cabeça para a direita. MSegue-se que depois de etapas, o conteúdo da fita é uma m onde A é um símbolo do alfabeto da fita ea cabeça de M é no símbolo branco da esquerda para a direita da última A . Como M aceita a entrada 1 n , ele deve aceitar ou mover para a esquerda no símbolo em branco. Como no caso 2), o chefe de M agora nunca visitará a n- ésima célula à esquerda do A mais à direita . Isso ocorre porque na entrada 1 n , MmAmAMAM1nMnA1nM não visita a célula diretamente à esquerda da célula inicial, porque contém o símbolo em branco e, se o ler, será executado para sempre.

É claro que nos três casos aceita todas as seqüências do conjunto { 1 m ; m n } .M{1m;mn}

David G
fonte
Antes de tudo, em nenhum lugar da pergunta ele diz que M deve interromper todas as entradas, de modo que estraga parte da lógica nesta resposta. Além disso, a lógica em vários casos não faz sentido para mim. Por exemplo, no caso 3, se M se mover para a esquerda tanto em branco quanto em A, então M visitará a célula diretamente à esquerda do A mais à direita (em contraste direto com a reivindicação da resposta).
Mikhail Rudoy
Agradável; outra maneira de estado é: se (linguagem unária), então k  st  1 kL ( M ) L ( M ) = { 1 n | n > 0 } ...Σ={1}k s.t. 1kL(M)L(M)={1nn>0}
Marzio De Biasi
@MikhailRudoy, ​​para esclarecer primeiro o caso 3: se a cabeça se mover para a esquerda no símbolo A e em branco, ela se moverá para a esquerda para sempre e não parará. Se alguma vez (digamos, após 100 etapas) visitar a célula diretamente à esquerda do A mais à direita, no caso da entrada 1, ele nunca será interrompido (nesse caso, a célula diretamente à esquerda do A à direita conterá o símbolo em branco).
David G
@MikhailRudoy, ​​é verdade que eu assumi que uma máquina de Turing precisa parar. Vou editar a resposta para incluir também a possibilidade de que ela seja executada para sempre. O resultado é semelhante.
David G
3
@MikhailRudoy: Aliás, o problema do filhote é decidível para máquinas de Turing de 1 estado; veja Gabor T. Herman, O problema de parada uniforme para máquinas de turing de um estado generalizadas . O modelo descrito é um pouco diferente do seu: a TM aceita se termina em uma configuração mortal (não há Aceitar / Rejeitar); mas o resultado também se aplica ao seu modelo (basta interromper a TM nos símbolos que levam aos seus estados adicionais de Aceitar / Rejeitar).
Marzio De Biasi