Quelle est la relation entre les problèmes et les langues?

Je veux demander exactement quelle est la relation entre les problèmes et les langues. Nous savons que l'ensemble de toutes les langues est innombrable. L'ensemble des problèmes est-il également indénombrable? Chaque problème peut-il être défini par une langue? Une langue peut-elle résoudre plus d'un problème et vice versa? Existe-t-il une correspondance individuelle entre le problème et les langues?

Les problèmes de décision et les langues ne sont que les deux faces d'une même médaille: chaque problème peut être reformulé comme le problème d'appartenance à une langue. Le problème, par exemple, de déterminer si un nombre est premier est exactement le problème d'appartenance à la langue des nombres premiers.

Formellement, une langue est un ensemble de chaînes finies sur un alphabet fini fixe (parfois, les chaînes peuvent être infinies; c'est un scénario différent mais lié). Les problèmes qui ne sont pas directement des questions sur les chaînes devront être codés sous forme de chaînes, par exemple, il aurait été plus précis d'écrire la dernière phrase du paragraphe précédent comme suit: "Si nous corrigeons un alphabet et un codage de nombres naturels en tant que chaînes sur cet alphabet, le problème, par exemple, de déterminer si un nombre est premier est exactement le problème d'appartenance de la langue des chaînes qui codent des nombres premiers. "

Pour parcourir rapidement vos sous-questions,

Nous savons que l'ensemble de toutes les langues est innombrable. L'ensemble des problèmes est-il également indénombrable?

Oui, car les problèmes et les langues sont essentiellement la même chose.

Chaque problème peut-il être défini par une langue?

Des problèmes de décision, oui. Les problèmes d'optimisation (quel est le plus petit X avec la propriété Y) et les problèmes de comptage (combien de X ont la propriété Y) peuvent être reformulés comme des problèmes de décision (le Z est-il le plus petit X avec la propriété Y?; Existe-t-il des NX avec la propriété Y?), Bien que ce n'est généralement pas la façon la plus naturelle de les traiter.

Une langue peut-elle résoudre plus d'un problème et vice versa?

Oui et oui, car vous devez utiliser des encodages pour traduire entre problèmes et langages. Par exemple, les langues$\{10,11,101,111,1011,\dots\}$ et $\{2,3,5,7,11, \dots\}$les deux codent le problème de primalité (en binaire et décimal, respectivement). Inversement, mais peut-être un peu artificiellement, la langue$\{0, 10, 110, 1110, \dots\}$ code le problème de déterminer si un nombre binaire est de la forme $2^k-2$ pour certains $k$et le problème de déterminer si une chaîne de 1 et de 0 a exactement un 0, qui est son caractère final. (Peut-être que quelqu'un peut trouver un meilleur exemple d'une langue qui code naturellement deux problèmes sans que l'un soit une reformulation aussi banale de l'autre.)

Existe-t-il une correspondance individuelle entre le problème et les langues?

Non, car cette question n'est que le complément de la précédente. :-)