Undecidable Problems
Introduit| English | Sens |
|---|---|
| cannot/ˈkænɒt/ | ne peut pas |
| decidable/dɪˈsaɪdəbl/ | décidable |
| undecidable/ˌʌndɪˈsaɪdəbl/ | indécidable |
| limit/ˈlɪmɪt/ | limite |
| inefficient/ɪnɪˈfɪʃənt/ | inefficient : inefficace |
Tous les problèmes ne sont pas résolubles
- Tous les problèmes ne peuvent pas être résolus par un ordinateur, même en principe.
- Pour comprendre pourquoi, nous classons les problèmes en deux catégories.
- Une catégorie que l'ordinateur peut toujours répondre ; l'autre qu'il ne peut pas.
- C'est un fait prouvé en informatique, pas une lacune que nous pourrions combler un jour.
A decidable problem is one where:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
"Is n even?" is decidable — always answerable.
Problèmes décidables
- Un problème décidable possède un algorithme qui donne toujours une réponse correcte oui ou non pour chaque cas.
- "Ce nombre est-il pair ?" est décidable — un test simple répond toujours correctement.
- "Ce nombre est-il premier ?" est aussi décidable, même si c'est lent pour les très grands nombres.
- S'il existe un algorithme correct pour chaque cas, le problème est décidable.

Problèmes décidables et indécidables
Decidable or undecidable?
A decidable problem has an algorithm that always answers correctly for every case; an undecidable one has no such algorithm — being impossible, not merely slow.
An undecidable problem:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Some cases defeat every possible program.
Deciding in general whether any given program will ever stop running is:
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
No single algorithm answers this correctly for every program.
Undecidability marks a hard ______ on what computation can achieve.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Some questions simply have no general algorithm.
Problèmes indécidables
- Un problème indécidable n'a aucun algorithme capable de résoudre correctement tous les cas.
- Peu importe à quel point le programme est ingénieux, certains cas le défieront.
- L'exemple classique : décider, en général, si un programme donné s'arrêtera jamais.
- L'indécidabilité est une limite à ce que le calcul peut accomplir — certaines questions n'ont tout simplement pas d'algorithme général.
Undecidable and merely inefficient (slow) mean the same thing.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
Inefficient can be solved slowly; undecidable cannot be solved for every case at all.
Testing whether a number is prime is undecidable because it can be slow for huge numbers.
Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui
False. Primality is decidable: an algorithm always gives an answer. Being slow is not the same as being impossible.
Indécidable n'est pas seulement lent
- Ne pas confondre indécidable avec simplement peu efficace.
- Un problème peu efficace peut être résolu, mais lentement. Un problème indécidable ne peut pas être résolu pour tous les cas du tout.
Premier vs Halting. Tester si un nombre est premier est décidable — un algorithme répond toujours, même si c'est lent pour les très grands nombres. Mais décider en général si n'importe quel programme s'arrêtera est indécidable : aucun algorithme unique ne répond correctement pour chaque programme. Lent n'est pas la même chose qu'impossible.
Un problème décidable a un algorithme qui répond toujours correctement ("n est-il pair ?", "n est-il premier ?"). Un problème indécidable n'a aucun tel algorithme pour tous les cas (un programme s'arrêtera-t-il ?) — une réelle limite du calcul. Indécidable signifie qu'il ne peut pas 不能 être résolu du tout, pas simplement inefficace (lent).