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

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?

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.

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.$\omega$

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.$\omega$

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.$\Sigma^\omega$$\Sigma$$\Sigma = \{0,1\}$$\Sigma^\mathbb{N} = 2^\mathbb{N}$$2^{2^\mathbb{N}}$

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 .$M$$L \in \Sigma^*$$N$$x\in \Sigma^\omega$$M$$x$$N$$x$$L$

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.$k\in \mathbb{N}$$k$$k$$3$$6$

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

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.$L_i$$L = \cup_i L_i$$L$$L$$L$

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

5. $k$$k$

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 $x \mapsto \lg x$$x$$\lg x$ para nós.

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