Inscription / Connexion Nouveau Sujet
Niveau école ingénieur
Partager :

Langage semi-décidable ?

Posté par
AladdinSane
25-07-16 à 16:50

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

Posté par
Recomic35
re : Langage semi-décidable ? 25-07-16 à 17:52

Ce que je comprends, c'est :
Pour un langage semi-décidable, si un mot est dans le langage, ton algorithme va te le dire au bout d'un temps fini. S'il n'est pas dans le langage, l'algorithme tournera sans donner de réponse. Donc : tu peux être sûr qu'un mot est dans le langage, tu ne peux pas être sûr qu'il n'y est pas.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1674 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !