Existe uma linguagem finita indecidível de palavras finitas?

10

Existe a necessidade de ser infinito para ser indecidível? $L\subseteq \Sigma^*$

Quero dizer, e se escolhermos um idioma seja uma versão finita limitada de , ou seja , ( ), com . É possível que seja uma linguagem indecidível? $L'$ $L\subseteq \Sigma^*$ $|L'|\leq N$ $N \in \mathbb{N}$ $L' \subset L$ $L'$

Vejo que existe um problema de "Como escolher as palavras que para as quais temos de estabelecer uma regra para escolher quais seriam os primeiros elementos de , uma espécie de estrela "finita" de Kleene Operação. O objetivo é encontrar uma linguagem indecidível sem a necessidade de um conjunto infinito, mas não consigo vê-lo. $N$ $\in$ $L' "$ $N$ $L'$

Editar nota:

Embora eu tenha escolhido uma resposta, muitas respostas e todos os comentários são importantes.

formal-languages computability undecidability Hernan_eche
fonte

Parece haver (pelo menos) três perguntas aqui. Por favor, concentre-se em um e edite os outros.

Raphael

Eu removi as referências ao conjunto de potência, pois não é relevante aqui;

P (S)

$\mathcal{P}(S)$ é finito se e somente se

S

$S$ for finito.

Raphael

@Raphael Está tudo bem, mas eu menciono o conjunto de potência porque às vezes eu leio "não há exceção de para , portanto , deve existir uma linguagem indecidível". $\mathbb{N}$ $\mathcal{P}(\mathbb{N})$ Gostaria de entender por que isso não funcionou com um conjunto finito , com com finito, em vez de precisar de , por isso coloquei

L^{'}

$L'$

| L^{'} | \leq N

$|L'|\leq N$

N

$N$

N

$\mathbb{N}$

P (S)

$\mathcal{P}(S)$

Hernan_eche

11

Até onde eu sei, a existência de linguagens indecidíveis não decorre imediatamente da inexistência de tal rejeição; você precisa de mais alguns pedacinhos. Ora, isso faria outra pergunta maravilhosa! Por que você não vai em frente e pergunta? A partir daí, você deve ver por que o argumento não é transferido para linguagens finitas.

Raphael

3

Linguagem finita é decidível, ponto final, fim da história. Há qualquer número de algoritmos para isso. Se você insiste no modelo clássico da Máquina de Turing, isso também pode ser feito dessa maneira, embora menos perspicazmente. Não há necessidade de invocar autômatos de estado finito ou linguagens regulares ou qualquer outro modelo de autômato, pois eles são de fato exagerados sem nenhuma clareza adicional em relação às Máquinas de Turing.

David Lewis

15

Sim, é necessário que seja infinito para ser indecidível. $L$

Para adicionar as respostas de Raphael e Sam, você deve pensar em "decidível" como algo que um programa de computador pode resolver. O programa requerido é muito simples, ele só precisa gerar "Sim" para elementos em ou, caso contrário, dizer não. $L$

Portanto, quanto mais "complexo" for, mais longo será o programa que você precisará escrever. Em outras palavras, quanto mais longo o programa você executar, poderá verificar mais coisas ... Portanto, se alguém fornecer um idioma que é finito, diga , você pode escrever o seguinte programa: $L$ $L$ $L=\{ a_1, a_2, \ldots, a_n\}$

if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;

Agora, se alguém lhe der um maior (ainda que finito), você apenas escreverá um programa mais longo. Isso sempre é verdade, e qualquer finito terá seu próprio programa. O único caso "interessante" é o que acontece quando é infinito - seu programa não pode ser infinito. $L$ $L$ $L$

A questão da "indecidibilidade" é ainda mais interessante: são aqueles (infinitos) que não possuem um programa que funcione corretamente para eles. Sabemos que essas linguagens devem existir, pois há muito mais (infinitas) linguagens que o número de programas de comprimento finito (mas ilimitado). $L$ $L$

Tocou.
fonte

+1 Esta é uma resposta muito clara. Gostaria que você expandisse um ponto, você disse "se alguém lhe der um maior (ainda que finito), você escreverá apenas um programa mais longo" *, mas acho que o oposto, dada a ** fixo ** conjunto finito de programas , e se você não pode escrever um programa mais longo Eu acho que algumas imputs um conjunto finito, vai para fora SIM, e alguns não . Como , então algumas das entradas corresponderão às funções indicadoras mas * a maioria $L$ $P$ $|P|=K$ $\in L$ $\mathcal{P}(P) \gt K$ $\in L$ $P$ não irá!, Porque idiomas possíveis

2^{K}

$2^K$

> K

$\gt K$ programas possíveis, haverá problemas indecidíveis. Estou errado? porque?

Hernan_eche

11

de fato, se você limitar o tamanho do programa a , existem no máximo programas diferentes que classificam corretamente no máximo idiomas diferentes (infinitos ou não). Portanto, para esse conjunto específico de programas , existem linguagens indecidíveis e até finitas. Mas essa é uma afirmação mais fraca, já que você considera apenas um conjunto limitado de programas (por exemplo, , você tem apenas 2 programas possíveis; é claro que eles não serão capazes de fazer muito e falharão em quase todos os idiomas )

| P | = k

$|P|=k$

O (2^{k})

$O(2^k)$

O (2^{k})

$O(2^k)$

| P | = 1

$|P|=1$

L

$L$

Ran G.

obrigado, eu sei que é uma declaração mais fraca, mas é ousado que possa haver Idiomas Indecidíveis finitos e infinitos, e acho que esse caso especial deve ser incluído em sua resposta, a parte "Sim, é necessário que L seja infinito em para ser indecidível. " parece não ser uma necessidade sob certas condições.

Hernan_eche

6

Não exatamente. O termo "indecidível" tem um significado específico: não é decidível por uma máquina de Turing padrão. Assim, para ser undecidable, deve ser infinito. O que você deseja não é senão um termo diferente, a saber, "não decidível por ". Chame o último indecidível. Então, para qualquer finito , não há necessidade de ser infinito para ser indecidível. Apenas não confunda (ou abuso) e -undecidable

L

$L$ undecidable

P

$P$

P

$P$

P

$P$

L

$L$

P

$P$ undecidable

P

$P$

Ran G.

10

Não sei se entendi bem a pergunta, mas toda linguagem finita é regular. Não há idiomas regulares que são indecidíveis e, portanto, não há idiomas finitos que são indecidíveis. Todas essas declarações são bem conhecidas e podem ser encontradas provas em Hopcroft e Ullman .

Sam Jones
fonte

8

Se o seu idioma for finito, você poderá executar uma pesquisa de tabela em uma tabela codificada contendo todas as palavras em . É difícil escrever como máquina de Turing, mas em outros modelos equivalentes isso é bastante claro. $L'$ $L'$

De fato, autômatos finitos são suficientes. Construa um autômato para seguinte maneira: $L'$

Para cada , crie uma cadeia linear de estados que aceite . $w \in L'$ $w$
Crie um novo estado inicial . $q_0$
Conecte aos estados iniciais de todos os autômatos construídos em 1. com transições . $q_0$ $\varepsilon$

$L'$ $L'$ $\mathrm{REG} \subsetneq \mathrm{RE}$

Observe que o raciocínio se aplica a co-finito , que é ; você apenas codifica os elementos que não estão em . $L'$ $\big|\overline{L'}\big| < \infty$ $L'$

Rafael
fonte

2

Para ser de todo interessante (para o propósito de pensar sobre computabilidade), um problema de decisão precisa ter infinitamente muitas respostas "sim" e infinitamente muitas respostas "não". Tais problemas de decisão correspondem exatamente aos idiomas que contêm infinitas seqüências de caracteres sobre o alfabeto e também excluem infinitamente muitas seqüências de caracteres sobre o alfabeto.

Qualquer outra coisa é trivialmente capaz de ser codificada em apenas uma quantidade finita de informações (na pior das hipóteses, simplesmente em uma grande lista de cadeias de caracteres na linguagem ou não) e, portanto, computável por DFAs simples / expressões regulares. Eu espero que seja óbvio que, para qualquer lista finita de strings, você possa escrever imediatamente uma expressão regular que simplesmente ORs todas as strings.

Um espirituoso do meu professor de Teoria da Computação era que o problema de "Deus existe?" é computável - é computado por uma máquina que aceita imediatamente ou por uma máquina que rejeita imediatamente; nós simplesmente não sabemos qual!

Ben
fonte

Existe uma linguagem finita indecidível de palavras finitas?

Respostas: