튜링머신

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

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