Existem propriedades indecidíveis de autômatos completos sem turing?

15

Existem propriedades indecidíveis de autômatos limitados lineares (evitando o truque de linguagem de conjunto vazio)? Que tal um autômato finito determinístico? (deixe de lado a intratabilidade).

Gostaria de obter um exemplo (se possível) de um problema indecidível definido sem o uso explícito de máquinas de Turing .

A integridade de um modelo de Turing é necessária para suportar problemas incontestáveis?

computability automata undecidability Hernan_eche
fonte

"Existe uma solução para este sistema de equações diofantinas?" É isso que você está perguntando? Não está claro para mim o que você quer. Mas, o problema que dei é indecidível e não menciona a MT; portanto, estritamente falando, parece satisfazer os requisitos do seu segundo parágrafo.

Rrig # 6/12

Decidir se dois autômatos de pushdown reconhecem as mesmas palavras é indecidível, além de outros problemas sobre autômatos de pushdown . Não consigo pensar em problemas indecidíveis envolvendo DFAs.

Jmad

11

A resposta para a pergunta "É possível construir um problema indecidível para um autômato menos poderoso que uma máquina de Turing" é sim . De fato, para todo tipo de autômato sempre é possível identificar um problema indecidível.

Amelio Vazquez-Reina

11

Dada a resposta aceita, reformulei a pergunta para perguntar o que o OP (aparentemente) quer.

Raphael

15

Problemas indecidíveis sobre gramáticas livres de contexto e, portanto, também aceitadores de empilhamento, que são TMs restritas da Wikipedia ...

Dado um CFG, ele gera o idioma de todas as strings sobre o alfabeto dos símbolos terminais usados em suas regras?
Dados dois CFGs, eles geram o mesmo idioma?
Dados dois CFGs, o primeiro pode gerar todas as strings que o segundo pode gerar?

Existem muitos outros sobre CFGs / PDAs, bem como CSGs / LBAs e muitos outros modelos "mais simples que a TM".

David Lewis
fonte

+1, obrigado, eu ainda estou tentado a perguntar sobre um mais simples do CFG, e assim por diante .. para descobrir qual é o primeiro (mais simples) conhecido autômatos + problema a ser indecidível

Hernan_eche

3

Para encontrar um problema "mais simples" ou "mais simples" indecidível ou com qualquer propriedade, você precisará de uma definição precisa de "simples", dos quais muitos são possíveis. Mas o clássico em autômatos e linguagens formais é "o nível da hierarquia de Chomsky" (o que não é realmente muito hierárquico, matematicamente falando - foi originalmente proposto para gramáticas da linguagem natural). A FSA é a mais baixa, e tenho certeza de que qualquer problema indecidível para as FSAs teria que se referir de alguma maneira "essencial" a formalismos "menos simples" (todos precisando de definição precisa). CFL / CFG é o próximo mais alto, então eu escolhi isso.

David Lewis

+1 Concordo, encontrar o mínimo é indecidível também, surpreendentemente, não é possível construir um problema indecidível para FSA, então é possível para CFG, está apenas tentando encontrar algo no meio, graças

Hernan_eche

11

@ Hernan_e - existe uma estrutura muito rica de modelos e idiomas sub-CFL - por exemplo, o pda / família de 1 contador, que usa um "contador" inteiro positivo em vez de um pda; o nda turn pda, que permite apenas um turno de aumentar para diminuir a pilha, e generalizações desses. E há muitas questões indecidíveis sobre essas questões, bem como questões em aberto sobre as estruturas, por exemplo: existe uma CFL não regular "mínima" em alguma noção precisa de "mínima". Mas esse material geralmente está no nível de graduação e / ou pesquisa.

David Lewis

7

Não está claro o que você está perguntando na parte posterior da pergunta, principalmente porque "um problema sobre um modelo de máquina" não está definido.

Gostaria de obter um exemplo (se possível) de problema indecidível sem precisar da Turing Machine

Seja uma classe de máquinas e vamos usar como o código de . Podemos interpretar também como o código de th TM e depois pedir que dada faz o th parada TM? E esse problema sobre s é indecidível. $\{M_i\}$ $i$ $M_i$ $i$ $i$ $M_i$ $i$ $M_i$

Uma linguagem é apenas um conjunto de strings, que interpretação você atribui às strings não afeta a decidibilidade do idioma. A menos que você defina formalmente o que quer dizer com modelo de máquina e um problema nessas máquinas, suas perguntas posteriores não poderão ser respondidas.

Turing completa o maquinário mínimo para suportar um problema indecidível?

Novamente, o ponto que mencionei acima se aplica. Uma pergunta mais razoável seria: todas as provas de indecidibilidade passam por algo semelhante à indecidibilidade de interromper o problema das MTs? (A resposta é: existem outras maneiras).

Outra questão possível é: qual é o menor subconjunto de TMs em que o problema de interrupção para eles é indecidível. Obviamente, essa classe deve conter problemas que não são interrompidos (caso contrário, o problema é trivialmente decidível). Podemos facilmente criar subconjuntos artificiais de TMs onde o problema de parada não é decidível sem poder calcular algo útil. Uma pergunta mais interessante é sobre grandes conjuntos decidíveis de TMs, onde a parada é decidida por eles.

Aqui está outro ponto: assim que você tiver uma capacidade muito pequena de manipular bits (por exemplo, um tamanho polinomial ), poderá criar uma máquina com três entradas: , e modo que produza 1 se é um parando de aceitar o cálculo de TM na entrada . Então você pode perguntar os problemas como: existe um st é 1? que é um problema indecidível. $\mathsf{CNF}$ $N$ $e$ $x$ $c$ $c$ $M_e$ $x$ $c$ $N(e,x,c)$

Kaveh
fonte

5

Existe um problema indecidível muito simples para autômatos de estados finitos. Quebrar o alfabeto em duas metades , onde as letras em são "barrados" cópias. Agora, dado um autômato de estado finito, sobre decide se aceita uma string de modo que a parte não barrada seja igual à parte barrada (se ignorarmos as barras). Por exemplo, cadeia seria ok (ambas as partes soletrar ). $\Sigma \cup \bar\Sigma$ $\bar\Sigma$ $A$ $\Sigma\cup\bar\Sigma$ $a a \bar a \bar a b\bar b \bar aa$ $aaba$

Sim, este é um problema de correspondência posterior oculto em um autômato de estado finito. A completude de Turing está longe de ser óbvia na questão. Ela está lá, em segundo plano, enquanto as duas cópias (sem restrições e barradas) juntas codificam uma fila, que por si só é do poder de Turing.

Hendrik Jan
fonte

você tem uma referência a isso? não é imediatamente óbvio como converter PCP para isso. Além disso, também existem alguns problemas indecidíveis com os "transdutores" FSM.

vzn 22/10/12

11

(1) Você está certo, está de fato relacionado a um problema de duas fitas , as barras indicando a segunda fita. (2) Relação com PCP da seguinte maneira. A instância PCP consiste em duas listas de palavras

,

. Agora, o idioma regular que codifica PCP é

, onde

é a cópia barrada de

(u_{1}, \dots, u_{n})

$(u_1,\dots,u_n)$

(v_{1}, \dots, v_{n})

$(v_1,\dots,v_n)$

{u_{1} {\bar{v}}_{1}, \dots, u_{n} {\bar{v}}_{n}}^{+}

$\{ u_1\bar v_1, \dots, u_n\bar v_n \}^+$

\bar{v}

$\bar v$

. Receio não ter uma referência.

v

$v$

Hendrik Jan

3

"É possível criar um problema indecidível para um autômato menos poderoso que uma máquina de Turing?"

Sim. Um autômato é uma formulação axiomática consistente da teoria dos números (por exemplo, veja (1) ) e, portanto, pelo 1º teorema da incompletude de Gödel, ele deve incluir proposições indecidíveis.

Exemplo:

Qualquer problema que seja indecidível para uma TM também é indecidível para qualquer autômato que uma TM possa simular. Por quê? Como se um autômato menos poderoso que uma TM pudesse decidir uma linguagem que uma TM não pode decidir, uma TM deveria ser capaz de decidir simulando o autômato com uma contradição.

Amelio Vazquez-Reina
fonte

2

A questão de saber se um LBA é interrompido ou não também é decidível para uma TM, portanto não fazia parte dos exemplos que forneci em minha resposta. Qualquer problema indecidível para uma TM também é indecidível para um LBA.

Amelio Vazquez-Reina

11

{T | T M T h a l t s o n i n p u t T}

$\{T|TM T halts on input T\}$ que claramente não é decidível, mas é artificial. Provavelmente isso pode ser formalizado.

David Lewis

11

{T | TM T (T) halts}

$\{T|\text{ TM } T(T) \text{ halts}\}$

11

O @DavidLewis roseck não está afirmando que um problema indecidível sobre TMs ainda é indecidível se você o reinterpretar como sendo sobre LBAs. roseck simplesmente afirma que, se houver um problema que não pode ser decidido pelas TMs, o mesmo problema sem reinterpretação também não pode ser decidido por qualquer coisa que uma TM possa simular. O problema de parada da TM e o problema da parada do LBA são dois problemas diferentes.

Ben

11

@ Ben - se assim for, então "... indecidível para qualquer autômato que ..." teria que ser " por ". Mas essa é uma afirmação trivial.

David Lewis

1

Emil Post queria encontrar a resposta exatamente para esta pergunta: Existe um conjunto não recursivo (não computável) que não resolve o problema da parada. Ele conseguiu apenas em parte, mas o que ele fez foi criar o que é chamado de conjuntos simples .

Da Wikipedia:

Um subconjunto dos naturais é chamado de simples se for co-infinito e recursivamente enumerável, mas todo subconjunto infinito de seu complemento falha em ser enumerado recursivamente. Conjuntos simples são exemplos de conjuntos recursivamente enumeráveis, que não são recursivos. Dê uma olhada no artigo da Wikipedia para obter mais informações e referências, conjunto simples .

Pål GD
fonte

Existem propriedades indecidíveis de autômatos completos sem turing?

Respostas: