Representações finitas e linguagens de programação

Eu estou revisando algumas das matemáticas pré-requisitas sobre a teoria dos autômatos e as representações finitas.

Eu li o seguinte:

Se ∑ é um alfabeto finito, o conjunto de todas as cadeias de caracteres sobre o alfabeto (∑ *) é infinitamente contável .
O conjunto de todos os idiomas possíveis sobre um alfabeto ∑ é incontávelmente infinito .

Como o conjunto de idiomas possível de ∑ pode ser infinitamente infinito , mas a possível aplicação desse alfabeto a um idioma pode ser infinitamente contável ?

Posso pedir aos que responderem que não usem muita notação complexa, pois não sou um especialista em matemática.

discrete-mathematics Andrew S
fonte

Você entende a diferença entre infinito contável e infinito incontável, ou existe apenas um tipo de infinito em sua mente? Você tem uma vaga idéia de como essa distinção surgiu (cf. Cantor)?

Obrigado. Eu meio que tenho a ideia do infinito. Essencialmente, é um conjunto que não pode ser indexado, como um conjunto de números reais, porque, digamos, o número possível de etapas incrementais entre, digamos, 1.0 e 2.0, é imensuravelmente infinito.

Andrew S

"Imensuravelmente infinito" não é um termo técnico AFAIK (se houver, desconsidere o seguinte). Se com isso você quer dizer que existe um número infinito de etapas (contável ou não) entre 1 e 2, você caiu na armadilha de subestimar o infinito. O intervalo numérico real [1; 2] é realmente incontável, mas os racionais no mesmo intervalo são contáveis, apesar de haver um número (infinitamente) infinito deles e nenhuma etapa discreta!

Respostas:

Aqui está uma situação mais simples, destacando a diferença. O conjunto de cadeias binárias finitas é contável. O conjunto de cadeias binárias infinitas é incontável.

Outro exemplo: o conjunto de números com expansão decimal finita é contável. O conjunto de números com expansão decimal infinita é incontável.

A razão pela qual o número de idiomas é incontável é que você tem infinitas opções: para cada palavra, você pode decidir se está no idioma ou não. É por isso que é como aquela sequência binária infinita considerada acima.

Yuval Filmus
fonte

Os dois primeiros argumentos não são convincentes, um conjunto infinito de seqüências binárias é contável apenas infinitamente, 0, 1, 10, 11, ..... infinito (corretamente, se estou errado, o que provavelmente estou). No entanto, eu gosto do seu último exemplo.

Andrew S

O conjunto de todas as strings finitas é contável - ou seja, 0, 1, 10, 11, ... O conjunto de todas as strings infinitas é incontável. Você não pode nem escrever nenhum deles, pois todos são infinitos. Exemplos podem ser

0^{ω}

$0^\omega$ (infinitamente muitos zeros),

(01)^{ω}

$(01)^{\omega}$ (um padrão repetitivo),

1010^{2} 10^{3} 10^{4} 10^{5} \dots

$1010^210^310^410^5\dots$ (um padrão não repetitivo) e muitos, muitos mais. Incontavelmente mais. Mais do que você pode descrever.

Yuval Filmus

@ AndrewS, você está considerando seqüências binárias finitas . Confira o argumento diagonal da Cantor para ver a diferença crucial.

vonbrand

Muito obrigado pessoal, agora vou dormir hoje à noite (bem um pouco).

Andrew S

Não acho que essa resposta forneça uma intuição valiosa. 1) Não são conjuntos contáveis não triviais de cordas infinitas, como por exemplo representado por máquinas de Turing ou Büchi autómatos. 2) Os números racionais contêm tais que têm expansões decimais infinitas, mas o conjunto é contável. 3) A propriedade de "ter infinitas opções" é vaga demais para ser útil.

Raphael

Perguntas como "como pode" são sempre difíceis de responder, pois pedem intuição. A intuição aqui é: incontável significa "muitos" demais. Por que existem "muito mais" objetos de um tipo do que do outro tipo? Bem, eles simplesmente são.

Certifique-se de entender os fatos.

Dado um conjunto finito $\Sigma$ , construa a joia para $\mathbb{N}$ para o conjunto de todas as strings (finitas) sobre $\Sigma^*$ .

Dica: $\Sigma^n$ é finito, combinando uma numeração generalizada de $\Sigma^n$ com $n$ Deveria trabalhar.\
Mostre que o conjunto de todas as tuplas de naturais, ou seja, $\mathbb{N}^+ = \bigcup_{i \geq 1} \mathbb{N}^i$ , é contável.

Dica: Construa a bijeção para $\mathbb{N}^i$ primeiro (cf. Cantor) e combine-os, novamente usando $i$ .
Mostre que o conjunto de potência de $\mathbb{N}$ , ie $2^{\mathbb{N}}$ , é incontável.

Dica: use a diagonalização.

Se você fez isso, tem todas as ferramentas para mostrar, por exemplo, que

todos os conceitos algorítmicos (ou, de maneira mais geral, finitamente representados) são contáveis, mas
o conjunto de todas as funções sobre naturais ou reais ou ... é incontável.

Rafael
fonte