halting problem
(간단하게, 임의의 알고리즘과 임의의 input에 대해 그 알고리즘이 유한 시간 내에 종료될지, 종료되지 않을지를 결정하는 일.)
이는 귀류법을 써서, 케이스 분류 한 뒤에 증명하는 거긴 한데, 다음 유튜브에서 이해하기 쉽고 재밌게 시각적으로 잘 정리해 놓은 듯.
halting problem
(간단하게, 임의의 알고리즘과 임의의 input에 대해 그 알고리즘이 유한 시간 내에 종료될지, 종료되지 않을지를 결정하는 일.)
이는 귀류법을 써서, 케이스 분류 한 뒤에 증명하는 거긴 한데, 다음 유튜브에서 이해하기 쉽고 재밌게 시각적으로 잘 정리해 놓은 듯.