알고리즘 & Halting Problem

 

---

알고리즘 & Halting Problem

---

 

 

 

0. 알고리즘이란?

 

다음은 위키백과에 수록되어있는 알고리즘의 정의이다.

 

알고리즘, 셈법은 수학과 컴퓨터과학, 전산언어학 등에서 사용되는,
문제 해결 방법을 정의한 일련의 단계적 절차이다.

 

알고리즘에 대해서 보기 전에, 한 가지 짚고 넘어가야 하는 점이 있다. 여기서 '문제'란 무엇일까?

특히 알고리즘에서 문제(Problem)을 논할 때는, Computational Problem을 논한다.

 

알고리즘에서의 Computational Problem이란 input과 output으로 구성됩니다. 그리고 이 input과 output 사이의 관계를 나타내는 것을 문제의 정의(definition)이라고 한다. 

알고리즘의 문제에 대한 대표적인 예시는 정렬 문제(Sorting Problem)이 있다. 앞서 얘기한 정의에 따라 설명하면 다음과 같다.

• input: n개 정수의 유한한 배열
• output: 특정 기준에 따라 배열된 입력으로 주어진 n개의 정수의 유한한 배열 (ex. 오름차순)

 

이러한 문제들을 해결할 수 있는 방법 및 단계적 절차를 알고리즘(Algorithm)이라고 한다. 알고리즘에서는 크게 두 가지를 고려한다.

• 유한성(Finiteness) : 특히나 현실적인 Computational Problem에서는 보통 사용할 수 있는 자원이 한정되어있다. 따라서 알고리즘은 유한한 단계 안에 문제가 해결되어야 한다. 알고리즘에서는 특히 어떤 것이 최적해인지에 대한 논의가 이루어진다.
• 정확성(Correctness) : 알고리즘은 정확한 결과를 제공해야 한다. 유한성이 알고리즘의 효율성을 이야기한다면, 정확성은 말그대로 알고리즘의 '정확성'을 이야기한다.

 

 

 

 

1. 알고리즘과 계산 문제의 관계

 

알고리즘과 계산 문제(Computational Problem)의 집합은 다음과 같이 표현된다.

• 모든 알고리즘의 집합: 계수 가능 무한 집합 (countably infinite)
• 모든 계산 문제(Computational Problem)의 집합: 셀 수 없는 무한한 집합 (uncountable)

참고로 Countably infinite와 uncountable은 이산수학에서 Cardinality에 대해서 배울 때 배우는 개념이다. 모르면 구글링 해보면 나온다.

 

아무튼, Computational Problem의 집합이 훨씬 더 크다는 것을 알 수 있다. 즉 알고리즘과 계산 문제는 1대1 대응관계가 아니다. 

이를 고려했을 때, Computational Problem은 다음 두 가지 분류로 나뉜다.

• Algorithmically Solvable Problems : 해결 가능한 문제
• Halting Problems : 해결 불가능한 문제

 

Algorithmically Solvable Problem의 경우 어느 정도 파악이 되지만, Halting Problem의 경우 어느 정도 설명이 필요하다.

 

 

 

 

2. Halting Problem

 

Halting Problem은 위에서 이야기 한 것처럼 computational problem의 일종이다. 따라서 다음과 같이 input과 output이 나뉜다.

• input: a computer program P, an input x for P
• output
  • true if P(x) halts
  • false otherwise

 

위 설명으로는 부족할 수 있어 부연설명을 추가하자면, "주어진 프로그램이 해결하고자 하는 문제가 해결 가능한지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?" 에 대한 정답을 찾는 문제이다.

 

 

Naive하게 생각했을 때, "개쩌는 슈퍼컴퓨터라면 어떤 문제든 풀 수 있지 않을까?" 라는 생각을 할 수도 있다. 결론부터 이야기하자면 위에서 이야기했듯, 이 문제는 해결 불가능하다.

 

 

잘 모르겠다면 아래 영상을 보자. 100%를 다루고 있지는 않지만, 잘 설명되어있다: https://www.youtube.com/watch?v=VyHbd6sx5Po 

 

 

 

 

위 영상에서도 간략하게 소개되었지만, 이는 귀류법을 통해 증명된다. 증명 과정은 다음과 같다.

 

다시 타이핑하기 귀찮아서ㅎㅎ

 

 

 

끝!