Existe alguma linguagem decidível incontável de Turing?

17

Existem muitos (e eu digo muitos) idiomas contáveis ​​que são decidíveis por Turing. Qualquer idioma incontável pode ser Turing decidível?

Jyotirmoy Pramanik
fonte
1
Se o idioma de todas as palavras possíveis for incontável (o que requer um alfabeto incontável), ele imediatamente fornecerá um exemplo de um idioma incontável decidível de Turing (trivialmente). Se não é (isto é, é contável), as sub-línguas também não são incontáveis.
Marc van Leeuwen

Respostas:

24

Todo idioma em um alfabeto finito (ou mesmo contável) é contável. Supondo que o alfabeto da sua máquina de Turing seja finito, qualquer idioma que ele possa aceitar é contável.

Yuval Filmus
fonte
E o conjunto de todos os idiomas de número finito de cadeias de caracteres com alfabeto infinitamente contável? É contável ou incontável? Também não consegui pensar em provas para "a linguagem sobre o alfabeto contável infinito é contável".
anir
Seu aparelho também é contável.
Yuval Filmus
Isso prova que "o conjunto de idiomas sobre o alfabeto finito é contável". Eu sinto que podemos provar que "o conjunto de idiomas que contém seqüências infinitas sobre o alfabeto finito é contável" seguindo a mesma abordagem de prova devido ao alfabeto finito. Mas não consigo imaginar como essa abordagem pode ser adaptada para um alfabeto infinitamente contável.
Anir 06/12/19
Você não pode provar isso, pois é falso. O número de infinitas seqüências binárias já é incontável.
Yuval Filmus
11

Só podemos ter idiomas incontáveis ​​se permitirmos palavras de tamanho infinito; veja, por exemplo , o idioma regular do Omega . Esses idiomas são chamados de idiomas . Outro exemplo será o idioma do subconjunto de reais que contém, digamos, expansões decimais de todos os números reais.ω

Existem alguns modelos nos quais as máquinas de Turing são modificadas para aceitar os idiomas . Alguns desses modelos usam a condição Buchi para aceitação. Como você não pode ver toda a entrada em tempo finito, dizemos que a entrada é aceita se a Máquina de Turing entrar no estado de aceitação infinitamente várias vezes. Se pudermos provar isso analisando a entrada (não executando-a), dizemos que a entrada é aceita.ω

Shreesh
fonte
1
Por que o alfabeto precisa ser contável?
leftaroundabout
2
Todo modelo em estudo possui um alfabeto finito. Se o alfabeto também se tornar infinito (contável ou incontável), é difícil ter um modelo razoável.
Shreesh 16/02
@Shreesh Bem, se o alfabeto é incontável, um mapeamento ingênuo de um FSM (com inúmeras transições entre um número finito de estados) pode ser bastante poderoso?
21716 Yakk
1
É verdade que esses são os tipos de extensões, que podem ter classes de idiomas que podem ser superclasses de RE ou idiomas recursivos. Mas eles não são bem estudados, se estudados. O maior problema é, na minha opinião, como podemos fornecer uma representação finita da máquina. Então você deve escrever o símbolo em uma célula de fita. Mesmo a célula humilde pode precisar de memória infinita para armazenar a descrição do símbolo da fita que está sendo gravada.
Shreesh 16/02
Esta é uma ótima explicação. Eu acrescentaria que, mesmo que um critério usual de aceitação / rejeição seja usado, você poderia dizer que ainda existem algumas linguagens que uma máquina de Turing poderia decidir e que tecnicamente teria inúmeras seqüências, mas apenas porque a grande maioria dos personagens é " inútil "para o idioma.
Owen
4

A computabilidade clássica discute funções sobre cadeias finitas de um alfabeto finito. Como resultado, todos os idiomas, decidíveis ou indecidíveis, são contáveis.

Para considerar linguagens incontáveis , temos que olhar para cadeias infinitas no lugar de cadeias finitas. (AFAIK, ter um alfabeto infinito não é muito interessante e não corresponde a um modelo realista de computação por si só.)

Existem modelos de computação em que podemos lidar com seqüências infinitas que nos permitem representar objetos de domínios incontáveis, como números reais. Estes são frequentemente representados como cálculos de tipo superior. Um modelo que usa máquinas de Turing é o modelo TTE. Nesse modelo, a entrada pode ser uma sequência infinita e as máquinas podem acessar qualquer item na sequência desejada. A máquina não precisa terminar, no entanto, existem condições para garantir que a saída da máquina converja.

Vamos supor que a entrada da nossa máquina seja de , ou seja, seqüências infinitas do alfabeto Σ , por exemplo, Σ = { 0 , 1 } . Então existem Σ N = 2 N strings. Portanto, existem 2 2 N idiomas possíveis. O número de máquinas TTE Turing ainda é contável. Portanto, a maioria desses idiomas é indecidível.ΣωΣΣ={0 0,1}ΣN=2N22N

Mas há algo ainda mais interessante aqui: se você deseja que a máquina sempre pare, ela poderá ler apenas uma parte inicial finita da entrada. Como resultado, temos o seguinte: Seja uma máquina TTE que sempre para (em tempo finito). Em seguida, há uma linguagem livre de prefixo G Σ * e máquina de Turing N tal que para qualquer x Σ co , H aceita x sse N aceita a parte inicial de X que é em L .MeuΣNxΣωMxNxeu

Em termos simples, o cálculo das máquinas TTE Turing que sempre param é determinado pelo cálculo de uma máquina de Turing em cadeias finitas.


Deixe-me dar um exemplo de linguagens decidíveis e indecidíveis de seqüências infinitas:

  1. Para qualquer o idioma das seqüências infinitas cuja k é a posição 0 é decidível. O mesmo acontece com k posição th sendo 1. intersecção de quaisquer duas línguas decidíveis é determinável, por exemplo, cadeias cujo 3 th posição é 0 e 6 th posição é 1.kNkk36

  2. A união de quaisquer dois idiomas decidíveis é decidível. Por exemplo, strings que começam com ou 10 .0 010

  3. Seja uma lista computacionalmente enumerável de linguagens decidíveis. Em seguida, L = i L i é semi-determinável, ou seja, não é uma máquina que pára e aceita sempre que um cordas em G e não aceita quando as cordas não é em L . Se não estiver em L, a máquina poderá não parar. Qualquer idioma semi-decidível pode ser obtido através da união de uma lista enumerável de idioma do formulário fornecido no item 1 acima.euEueu=EueuEueueueu

  4. Um idioma é decidível se o idioma e seu complemento forem semi-decidíveis.

  5. kk


Isso pode fazer você pensar que o TTE não é um modelo interessante. Mas acontece que o cálculo sobre seqüências infinitas usando o modelo TTE é realmente bastante interessante. É baseado na intuição de que, para obter qualquer parte finita da saída, você pode ler apenas uma parte finita da entrada. Em outras palavras, qualquer informação finita sobre a saída depende apenas da quantidade finita de informações sobre a entrada. Acontece que as funções que estamos interessadas em computar seguem esta regra, caso contrário não poderíamos calculá-las. Por exemplo, considere números de leitura codificados como cadeias binárias e a função xlgxxlgx para nós.


f{0 0,1}f-1(1)". Existem também muitas outras referências no site para Computabilidade e Complexidade na Rede de Análise .

Kaveh
fonte
1
" Como resultado, todos os idiomas são finitos " - você quer dizer contável?
Anton Trunov
Eu acho que sim, Sr. Trunov.
Jyotirmoy Pramanik
Este é um bom post, mas não consigo ver o que seu volume tem a ver com a pergunta específica feita aqui. Talvez você queira criar um par de perguntas e respostas?
Raphael