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
scroll top