Dimostrare che l'insieme di tutte le lingue nel corso di un alfabeto finito è incalcolabile

Question

Cercando di fare qualche revisione, ma non sono sicuro su questo:

  

Dimostrare che l'insieme di tutte le lingue nel corso di un alfabeto fi nite è incalcolabile.

Ho la sensazione che sarà necessario utilizzare il metodo Cantor Diagonalizzazione - ma io sono non sicuro di come lo si dovrebbe utilizzare per questo problema.

Answer 1

ho trovato nella mia teoria computazione note di classe questa prova, spero che sia utile per voi

| N | <| Lingue (N) |

supose che | N | > = | Lingue (N) |. Pertanto, ciascuno degli elementi di lingue (N) può essere correlato ad uno degli elementi di N. In modo che possano essere messi in ordine:

lingue (n) = {S_1, S_2, S_3, ...}

definire un insieme D come:

D = {n in N / n non in S_n}

D è valido e D è un sottoinsieme di N, quindi D appartiene lingue (N). Quindi, deve esistere un k per cui D = S_k

1) Se k appartiene a D per definizione di D, k non appartiene a S_k. E k non appartiene a D Perché D = S_k (Troviamo una contraddizione)

2) Se k non appartiene a D allora: k appartiene alla S_k (per definizione di D) e k appartiene a D perché D = S_k (contraddizione nuovo)

Una sequenza come quella assunta non può esistere. Quindi una funzione iniettiva che assegna un elemnt di N per ogni elemento di lingue (N) non è possibile. Concludendo che | lingue (N) | ! <= | N |, in modo | lingue (N) | > | N |