프로그램

정지 문제: 모든 프로그램을 만들 수 있을까?

컴퓨터에게 일을 시키기 위해 컴퓨터가 해야 할 일을 매우 논리적으로 정리한 것을 프로그램이라고 한다. 컴퓨터는 프로그램을 읽고, 프로그램대로 작업을 실행한 후 프로그램에 따라 결과를 보여준다. 컴퓨터 덕에 우리는 이전에 상상도 못 할 정도의 일을 순식간에 처리할 수 있게 되었다. 하지만 우리는 컴퓨터로 모든 문제를 풀 수 있는가? 우리는 무엇이든 원하는 모든 것을 프로그램으로 작성하여 컴퓨터에게 시킬 수 있는가? 이번 글에서 컴퓨터가 풀 수 없는 문제. 정지 문제에 대해 다루고자 한다. 정지 문제 주어진 프로그램이 해결하고자 하는 문제를 해결할 수 있는지 판별하는 프로그램을 만들 수 있는가? 프로그램은 하나의 함수로 생각할 수 있다. 예를 들어 하나의 정수를 입력으로 받아 제곱을 하는 프로그램은 다음 함..

원주율의 근사방법

원주율이란, 원에서 지름과 반지름의 길이비로 정의된다. 모든 원에서 이 값은 일정하며, 따라서 상수이다. 원주율이 무리수라는 증명은 이미 존재하는데, 이는 곧 원주율은 원을 하나 그리고, 원주와 반지름의 길이를 실측해서 나타낼 수 없음을 의미한다. 따라서 여타 다른 무리수, 이를테면 $\sqrt{2}$와 같이 $\pi$도 근사를 통해 그 값을 구해야 한다. #include #include #include #include #define BATCH 999999 #define WILL_TRY 1400000 #define SQUARE 14000 #define RND(M) rand()%M #define DOUBLE_SIZE sizeof(double) clock_t start_p, end_p; void approx..