Le lingue finite sono decidabili - contraddizione [duplicato
Domanda
Questa domanda ha già una risposta qui:
Diciamo che definisco la lingua $ l $ rispetto all'alfabeto $ {0, 1 } $ per essere una lingua contenente solo una parola, $ w $, dove:
$$ w = inizio {casi} 1 & text {se l'ipotesi del continuum è vera} 0 & text {altrimenti.} end {casi} $$
$ L $ è finito, quindi esiste una macchina Turing che può decidere se la parola $ 1 $ è in $ l $. Al contrario, l'ipotesi di continuum è indipendente da $ ZFC $, il che significa che non può essere dimostrato né smentito dalla teoria standard di Zermelo - Fraenkel. Di conseguenza, non possiamo sapere se $ 1 $ o $ 0 $ è in $ l $. Quindi, come possiamo costruire una macchina Turing che può decidere $ l $?
Nessuna soluzione corretta
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange