Domanda

Formare una lingua riconoscibile ma non riconoscibile. Ho problemi a trovare una lingua con queste proprietà. Una lingua riconoscibile è una lingua $ A sottoseteq sigma^*$ Iff $ A = l (m) $ Per una macchina Turing $ M $.

Il co-riconoscibile è esattamente lo stesso tranne il complemento di $ A $ deve essere riconoscibile.

La mia domanda è: come faccio a trovare una lingua che so sarà riconoscibile ma non riconoscibile?

Nessuna soluzione corretta

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a cs.stackexchange
scroll top