| English | 의미 |
|---|---|
| cannot/ˈkænɒt/ | 불가능함 |
| decidable/dɪˈsaɪdəbl/ | 판정 가능함 |
| undecidable/ˌʌndɪˈsaɪdəbl/ | 판정 불가함 |
| limit/ˈlɪmɪt/ | 한계 |
| inefficient/ɪnɪˈfɪʃənt/ | 비효율적임 |
모든 문제가 해결 가능한 것은 아니다
- 모든 문제를 컴퓨터로 해결할 수 있는 것은 아니며, 원칙적으로도 그렇지 않습니다.
- 그 이유를 이해하기 위해 문제들을 두 가지 유형으로 분류해 보겠습니다.
- 한的类型은 컴퓨터가 항상 답할 수 있지만, 다른 유형은 할 수 없습니다.
- 이는 컴퓨터 과학에서 입증된 사실이며, 언젠가 채워질 수 있는 빈틈이 아닙니다.
해결 가능한 문제는 다음과 같은 문제입니다:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
"n이 짝수인가?"는 해결 가능함 — 항상 답 가능함.
결정 가능한 문제
- 결정 가능한(decidable) 문제는 모든 경우에서 올바른 예/아니오 답변을 всегда 제공하는 알고리즘이 존재하는 문제입니다.
- "이 숫자가 짝수인가?"는 판별 가능(decidable)합니다—간단한 테스트가 항상 정확하게 답을 내립니다.
- "이 숫자가 소수인가?" 역시 판별 가능하지만, 거대한 숫자일 경우 속도가 느릴 수 있습니다.
- 모든 경우에 대한 올바른 알고리즘이 존재하면 해당 문제는 결정 가능합니다.
해결 가능 여부 또는 해결 불가능 여부?
해결 가능한 문제는 모든 경우에 대해 항상 올바른 답을 제공하는 알고리즘이 있는 문제이며, 해결 불가능한 문제는 그러한 알고리즘이 없으며, 단순히 느린 것이 아니라 불가능합니다.
해결 불가능한 문제:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
특정 사례들이 모든 가능한 프로그램을 무력화시킴.
주어진 프로그램이 언제까지 실행될지 여부를 일반적으로 판단하는 것은:
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
모든 프로그램에 대해 이를 올바르게 답하는 단일 알고리즘은 없습니다.
해결 불가능성은 컴퓨팅이 달성할 수 있는 것에 대한 단단한 ______를 표시합니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
일부 질문들은 일반적으로 알고리즘이 존재하지 않습니다.
결정 불가능한 문제
- 결정 불가능한(undecidable) 문제는 모든 경우를 올바르게 해결할 수 있는 알고리즘이 없는 문제입니다.
- 프로그램이 얼마나 영리하더라도 일부 경우에는 해결할 수 없습니다.
- 고전적인 예시: 임의의 프로그램이 언제까지 실행될지, 즉 멈출지를 일반적으로 판단하는 것입니다.
- 결정 불가능성은 계산이 달성할 수 있는 한계를 의미하며, 어떤 질문들은 일반적인 알고리즘이 아예 존재하지 않습니다.
해결 불가능함과 비효율적(느림)은 같은 의미입니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
비효율적은 느리게 해결할 수 있으나, 해결 불가능한 것은 모든 경우에 대해 아예 해결할 수 없습니다.
수소가 소수인지 테스트하는 것은 해결 가능하지만, 거대한 숫자에는 느릴 수 있습니다.
난이도 1/5 · 100 코인 + 오늘 첫 완료 시 소액 보너스
알고리즘은 항상 답을 제공하며, 느림은 불가능과 다릅니다.
결정 불가능함은 단순히 느림이 아니다
- 결정 불가능함을 단순히 비효율적인 것과 혼동하지 마십시오.
- 비효율적인 문제라도 해결할 수는 있으나 느립니다. 반면 결정 불가능한 문제는 모든 경우를 절대 해결할 수 없습니다.
소수 vs 정지 문제. 숫자가 소수인지 테스트하는 것은 결정 가능합니다—알고리즘은 항상 답을 내며,非常大的 numbers에는 느릴 뿐입니다. 하지만 임의의 프로그램이 정지할지를 일반적으로 판단하는 것은 결정 불가능합니다—모든 프로그램에 대해 옳게 답하는 단일 알고리즘은 존재하지 않습니다. 느림과 불가능함은 다릅니다.
판별 가능한(decidable) 문제는 모든 경우에서 정확하게 답을 내리는 알고리즘이 있는 문제("n이 짝수인가?", "n이 소수인가?")입니다. 판불 가능(undecidable) 문제는 모든 경우에 대해 그러한 알고리즘이 존재하지 않는 문제(프로그램이 멈출 것인가?)이며, 이는 컴퓨팅의 실질적인 한계입니다. 판불 가능이라는 것은 단순히 비효율적(느림)인 것이 아니라 아예 해결할 수 없음을 의미합니다.