Perplexe par le théorème de Rice

37

Résumé: Selon le théorème de Rice, tout est impossible. Et pourtant, je fais ce truc soi-disant impossible tout le temps!


Bien entendu, le théorème de Rice ne dit pas simplement "tout est impossible". Il dit quelque chose d'assez plus spécifique: "Chaque propriété d'un programme informatique est non-calculable."

(Si vous voulez diviser les poils, chaque propriété "non triviale". Autrement dit, les propriétés que tous les programmes possèdent ou ne possèdent pas sont trivialement calculables. Mais toute autre propriété n'est pas calculable.)

C'est ce que dit ou semble dire le théorème. Et vraisemblablement un grand nombre de personnes très intelligentes ont soigneusement vérifié l'exactitude de ce théorème. Mais cela semble complètement défier la logique! Il existe de nombreuses propriétés de programmes qui sont triviales à calculer! Par exemple:

  • Combien d'étapes un programme exécute-t-il avant de s'arrêter? Décider si ce nombre est fini ou infini est précisément le problème de Halting, qui est non calculable. Décider si ce nombre est supérieur ou inférieur à un fini est trivial! Il suffit d’exécuter le programme jusqu’à étapes pour voir s’il s’arrête ou non. Facile!nn

  • De même, le programme utilise-t-il plus ou moins de unités de mémoire dans ses premières étapes d'exécution? Trivialement calculable.nm

  • Le texte du programme mentionne-t-il une variable nommée ? Une analyse textuelle triviale révélera la réponse.k

  • Le programme appelle-t-il la commande ? Encore une fois, scannez le texte du programme à la recherche de ce nom de commande.σ

Je peux voir beaucoup de propriétés qui ne semblent pas non plus être calculables; Par exemple, combien d’additions une série complète du programme effectue-t-elle? Eh bien, c'est presque la même chose que de demander combien d' étapes le programme exécute, ce qui est pratiquement le problème de l'arrêt. Mais il semble y avoir de nombreuses propriétés de programme sur le bateau qui sont vraiment très faciles à calculer. Et pourtant, le théorème de Rice insiste sur le fait qu'aucun d'entre eux n'est calculable.

Qu'est-ce que j'oublie ici?

MathematicalOrchid
la source
8
"Selon le théorème de Rice, tout est impossible." -- Nan. "Chaque propriété d'un programme informatique est non-calculable." -- Nan. Vous n'êtes pas seul, cependant: la plupart des étudiants rencontrent cette idée fausse.
Raphaël

Réponses:

36

Pour les besoins de cette discussion, un "programme" est un morceau de code qui prend toujours un entier en tant qu'entrée et qui est exécuté à l'infini ou renvoie un entier. Nous disons que deux programmes et sont égal extensionnellement si elles calculent la même fonction, à savoir, pour chaque numéro soit à la fois et courir pour toujours, ou à la fois fin et sortie le même nombre.fgnf(n)g(n)

Une propriété d'extension de programmes est une propriété qui respecte l'égalité d'extension, c'est-à-dire que si et sont égaux sur le plan d'extension, ils ont tous les deux la propriété ou ne l'ont pas.PfgP

Voici quelques exemples de propriétés non extensibles:

  1. Le programme s'arrête en étapes. (Nous pouvons toujours modifier un programme en un programme identique qui dure plus longtemps.)n
  2. Le programme utilise moins de cellules de mémoire au cours des premières étapes d'exécution. (Nous pouvons toujours modifier un programme en un programme égal à celui-ci, de sorte qu'il utilise de la mémoire sans raison valable.)nm
  3. Le texte du programme mentionne une variable nommée k. (Nous pouvons renommer les variables.)
  4. Le programme appelle-t-il la commande ? Cela peut dépendre un peu de ce que est, mais si c’est quelque chose qui peut être simulé d’une manière ou d’une autre, alors nous pouvons échapper à tout en conservant un programme égal par extension au programme original.σσσ

Je suis sûr que vous avez remarqué que j'ai énuméré précisément vos supposés contre-exemples du théorème de Rice, qui dit:

Théorème (Rice): propriété d' extension calculable des programmes, qu'elle soit valable ou non.

Il existe une autre manière d’expliquer cela: vous devez faire la distinction entre un programme et la fonction qu’il calcule. De nombreux programmes différents calculent la même fonction (ils sont tous égaux par extension). Le théorème de Rice concerne les propriétés des fonctions et non les propriétés des programmes qui les calculent.

Andrej Bauer
la source
Je ne peux pas obtenir cette réponse .. (Désolé si je demande la même chose, mais ce serait bien de clarifier ce point). Il dit que vous pouvez modifier ces programmes en changeant leur syntaxe pour obtenir un équivalent en extension , mais comment vérifier que ceux-ci sont équivalents en extension en premier lieu? Vous ne pouvez pas utiliser un programme pour comparer si ces fonctions ont généralement cette propriété, donc quand vous dites "modifiez-le", je pense que c'est possible car il s'agit d'exemples simples (voudriez-vous ajouter "modifiez-le soigneusement"? Ou utilisez un "bon IDE for it "? ..) Je pense qu'une fois modifiée, vous ne pouvez pas vérifier en général , alors peut-être que Rice tient.
Hernan_eche
1
En général, vous vérifiez que deux programmes particuliers sont égaux sur le plan de l'extension en prouvant que c'est le cas. Vous opposez-vous au fait que pour tous les entiers, même si un ordinateur ne peut pas "vérifier" cette égalité pour toutes les valeurs? Heureusement non. Il y a une différence entre écrire un programme qui calcule une valeur booléenne et prouver qu'un certain énoncé a une certaine valeur de vérité. Il y a des choses que nous pouvons prouver mais que nous ne pouvons pas calculer (comme le fait que deux programmes particuliers sont égaux sur le plan de l'extension ou que l'addition est commutative). n+m=m+n
Andrej Bauer
De plus, vous vous engagez dans un raisonnement étrange dans votre raisonnement: puisque l'égalité en extension n'est pas décidable, le théorème de Rice pourrait être faux. Comment? Et ce n’est pas parce que l’égalité par extension est indécidable que nous ne pouvons en décider. Ceux que j'ai mentionnés - nous pouvons en décider.
Andrej Bauer
36

Malentendu fondamental:

Chaque propriété d'un programme informatique est non-calculable

Ce n'est pas ce dont parle le théorème de Rice. Il parle des propriétés des fonctions et du fait que l'ensemble des programmes calculant cette fonction n'est pas décidable. Formellement, étant donné l'ensemblePRE

{MfMP}

n'est pas décidable. Pour les propriétés que vous mentionnez, vous ne trouverez pas de approprié pour lequel l'ensemble de programmes comporte ce formulaire. Certains programmes d'une fonction peuvent avoir la propriété alors que d'autres (pour la même fonction) peuvent ne pas en avoir. Voir ici pour quelques exemples.P

Le théorème de Rice traite des propriétés sémantiques (propriétés de la fonction calculées par un programme, par exemple domaine ou plage de valeurs). Vous faites référence à des propriétés syntaxiques (propriétés du programme , telles que le temps d’exécution ou le nombre de variables utilisées).

Pas grand chose semble être connu pour les propriétés syntaxiques; voir cette question .

Raphaël
la source
1
Je me suis perdu après environ la première phrase. Désolé. Quelqu'un peut-il préciser la différence entre une propriété sémantique et une propriété syntaxique?
MathematicalOrchid
@ MathematicalOrchid: Vous pouvez ignorer cette phrase en toute sécurité; le premier paragraphe contient toutes les informations dont vous avez besoin. Je vais élaborer, de toute façon.
Raphaël
2
Sémantique = à propos de ce que fait le programme. Syntactic = à quoi ressemble le programme.
reinierpost