Existe-t-il un algorithme qui existe de manière prouvée même si nous ne savons pas ce que c'est?

21

En mathématiques, il existe de nombreuses preuves d'existence non constructives, nous savons donc qu'un certain objet existe bien que nous ne sachions pas comment le trouver.

Je recherche des résultats similaires en informatique. En particulier: y a-t-il un problème que nous pouvons prouver qu'il est décidable sans lui montrer d'algorithme? C'est-à-dire que nous savons qu'il peut être résolu par un algorithme, mais nous ne savons pas à quoi ressemble l'algorithme?

Erel Segal-Halevi
la source
5
Il y a une réponse triviale. Prenez toute question oui / non dont la réponse est inconnue, comme "est aléatoire", alors la question est décidable, seulement nous ne savons pas encore lequel des deux algorithmes possibles est correct. π
Hendrik Jan
6
il existe
vzn
1
@babou En effet: une question avec une réponse unique est décidable. Ici, l'ignorance est le point qu'il semble, c'est un cas de "ne sais pas" de la question, bien que seulement "ne sais pas maintenant ". Une fois que nous avons découvert si est aléatoire ou non, nous devons chercher un autre exemple. Votre réponse ci-dessous est bien sûr meilleure! C'est une forme de «ne sait pas» qui est intrinsèquement «ne sait jamais». π
Hendrik Jan
1
@HendrikJan: Et cette procédure est ce que nous appelons un algorithme dans CS. Mais en prenant le problème d'arrêt comme exemple, nous ne pouvons même pas prouver qu'un algorithme existe!
MSalters
1
Des exemples plus intéressants peuvent être trouvés ici: cstheory.stackexchange.com/questions/4777/…
Erel Segal-Halevi

Réponses:

14

Le cas le plus simple que je connaisse d'un algorithme qui existe, bien que l'on ne sache pas quel algorithme, concerne les automates à états finis.

Le quotient d'une langue L 1 par une langue L 2 est défini comme L 1 / L 2 = { x y L 2  tel que  x y L 1 } .L1/L2L1L2L1/L2={xyL2 such that xyL1}

Il est facile de prouver que les ensembles réguliers sont fermés sous quotient par un ensemble arbitraire. En d'autres termes, si est régulier et L 2 est arbitraire (pas nécessairement régulier), alors L 1 / L 2 est régulier aussi.L1L2L1/L2

La preuve est assez simple. Soit un FSA acceptant l'ensemble régulier R , où Q et F sont respectivement l'ensemble des états et l'ensemble des états accepteurs, et soit L un langage arbitraire. Soit F = { q Q y LM=(Q,Σ,δ,q0,F)RQFL l'ensemble des étatspartir desquels un état final peut être atteint en acceptant une chaîne de L .F={qQyLδ(q,y)F}L

L'automate , qui diffère de M seulement dans son ensemble F ' d'états finaux reconnaît précisément R / L . (Ou voir Hopcroft-Ullman 1979, page 62 pour une preuve de ce fait.)M=(Q,Σ,δ,q0,F)MFR/L

Cependant, lorsque l'ensemble n'est pas décidable, il peut ne pas y avoir d'algorithme pour décider quels états ont la propriété qui définit F ' . Ainsi, alors que nous savons que l'ensemble F ' est un sous-ensemble de Q , nous n'avons pas d'algorithme pour déterminer quel sous-ensemble. Par conséquent, alors que nous savons que R est accepté par l'un des 2 | Q | possible FSA, nous ne savons pas de quoi il s'agit. Bien que je dois avouer que nous savons dans une large mesure à quoi cela ressemble.LFFQR2|Q|

Ceci est un exemple de ce que l'on appelle parfois une preuve presque constructive , c'est-à-dire une preuve qu'un nombre fini de réponses est la bonne.

Je suppose qu'une extension de cela pourrait être une preuve que l'un d'un ensemble énumérable de réponses est la bonne. Mais je n'en connais pas. Je ne connais pas non plus de preuve purement non constructive qu'un problème est décidable, par exemple en utilisant uniquement la contradiction.

babou
la source
1
RLL
Merci. C'est ma réponse préférée car le langage décidable est infini.
Erel Segal-Halevi
@babou, mon erreur, j'ai mal lu ce que tu as écrit. Ma faute - désolé pour ça. J'ai édité votre message pour faire la partie que j'ai mal comprise, espérons-le.
DW
@DW Je suis amusé que vous ayez eu un problème, mais ça m'arrive aussi. Mais j'aurais peut-être dû être plus clair. Ce n'était pas intentionnel. Dire cela parce que certains mathématiciens pensent qu'il est plus élégant d'être cryptique. Merci pour l'édition.
babou
12

Pour développer le commentaire original de Hendrick, considérez ce problème

n0nπ

Ce problème est décidable, car l'un des deux cas peut obtenir:

  1. NπN
  2. nπn

Dans le cas (1), un algorithme de décision pour le problème serait l'un des

n>N

et dans le cas (2) l'algorithme serait

Répondez "oui".

Il est clair que chacun d'eux est un algorithme de décision; nous ne savons simplement pas lequel. Cela suffit, cependant, puisque décidabilité ne nécessite que l' existence d'un algorithme, et non la spécification qui algorithme à utiliser.

Rick Decker
la source
+1 Ceci est un exemple simple que je me souviens avoir utilisé par mon professeur en calculabilité et logique. C'est mon exemple, car il ne nécessite pas beaucoup de connaissances dans le domaine, il est donc facile à transmettre.
Joshua Taylor
1
Pour des formulations alternatives, voir également ici .
Raphael
2

Voici une non-réponse. Je poste parce que je pense que c'est instructif, parce que j'avais à l'origine affirmé le contraire et huit personnes étaient suffisamment d'accord pour voter avant que @sdcwc ne signale l'erreur. Je ne voulais pas juste modifier ma première réponse parce que je ne suis pas sûr que beaucoup de gens l'auraient votée s'ils savaient que c'était faux.

SS

HH

David Richerby
la source