Bonjour,
dans mon cours, on a vu la définition d'un langage décidable : sa fonction caractéristique est calculable, et celle d'un langage semi-décidable : sa fonction caractéristique RESTREINTE (càd qu'elle n'est pas définie pour un mot x n'appartenant à au langage L) était calculable.
Je viens de voir (et ce n'est pas marqué dans mon cours), qu'un langage semi-décidable pouvait être décidable ou indécidable. Est-ce vrai ?
Si oui, qu'est-ce qu'un langage non semi-décidable ? Car je m'imaginais qu'un langage était soit décidable, soit indécidable, mais apparemment ce n'est pas le cas