Undecidable Problems · Problèmes Indécidables
| English | Français |
|---|---|
| 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/ | inefficace |
Not every problem is solvable
- Not every problem can be solved by a computer, even in principle.
- To see why, we sort problems into two kinds.
- One kind a computer can always answer; the other it cannot.
- This is a proven fact of computer science, not a gap we might one day fill.
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: · Un problème décidable est un problème pour lequel :
"Is n even?" is decidable — always answerable. · "n est-il pair ?" est décidable — toujours répondable.
Decidable problems
- A decidable 可判定 problem has an algorithm that always gives a correct yes-or-no answer for every case.
- "Is this number even?" is decidable — a simple test always answers correctly.
- "Is this number prime?" is decidable too, even if slow for huge numbers.
- If a correct algorithm exists for every case, the problem is decidable.
Problèmes décidables
- Un problème décidable 可判定 possède un algorithme qui donne toujours une réponse oui/non correcte 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.
Decidable or undecidable? · Décidable ou indécidable ?
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. · Un problème décidable possède un algorithme qui répond toujours correctement pour chaque cas ; un problème indécidable n'en a pas — c'est impossible, pas simplement lent.
An undecidable problem: · Un problème indécidable :
Some cases defeat every possible program. · Certains cas défient tous les programmes possibles.
Deciding in general whether any given program will ever stop running is: · Décider en général si un programme donné s'arrêtera ou non est :
No single algorithm answers this correctly for every program. · Aucun algorithme unique ne répond correctement pour chaque programme.
Undecidability marks a hard ______ on what computation can achieve. · L'indécidabilité marque une limite ______ sur ce que le calcul peut accomplir.
Some questions simply have no general algorithm. · Certaines questions n'ont tout simplement pas d'algorithme général.
Undecidable problems
- An undecidable 不可判定 problem has no algorithm that solves every case correctly.
- No matter how clever the program, some cases will defeat it.
- The classic example: deciding, in general, whether any given program will ever stop running.
- Undecidability is a limit 极限 on what computation can achieve — some questions simply have no general algorithm.
Problèmes indécidables
- Un problème indécidable 不可判定 n'a aucun algorithme qui résolve tous les cas correctement.
- 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 极限 de ce que le calcul peut atteindre — certaines questions n'ont tout simplement pas d'algorithme général.
Undecidable and merely inefficient (slow) mean the same thing. · Indécidable et simplement inefficace (lent) ne signifient pas la même chose.
Inefficient can be solved slowly; undecidable cannot be solved for every case at all. · Inefficace peut être résolu lentement ; indécidable ne peut pas être résolu pour tous les cas du tout.
Testing whether a number is prime is decidable, even if it is slow for huge numbers. · Tester si un nombre est premier est décidable, même si c'est lent pour de très grands nombres.
An algorithm always answers; slow is not the same as impossible. · Un algorithme répond toujours ; lent n'est pas la même chose qu'impossible.
Undecidable is not just slow
- Do not confuse undecidable with merely inefficient 低效.
- An inefficient problem can be solved, just slowly. An undecidable one cannot 不能 be solved for every case at all.
Prime vs halting. Testing whether a number is prime is decidable — an algorithm always answers, even if slow for huge numbers. But deciding in general whether any program will halt is undecidable: no single algorithm answers correctly for every program. Slow is not the same as impossible.
Indécidable n'est pas seulement lent
- Ne pas confondre indécidable avec simplement inefficace 低效.
- Un problème inefficace peut être résolu, juste 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.
A decidable problem has an algorithm that always answers correctly ("is n even?", "is n prime?"). An undecidable problem has no such algorithm for every case (will a program halt?) — a real limit of computing. Undecidable means it cannot be solved at all, not merely inefficient (slow).
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).