정지문제

정지문제란 "프로그램과 초기 입력값이 주어졌을 때, 이 프로그램에 입력값을 넣고 실행한다면 이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산할지 판정하라" 라는 엘런 튜링이 제시한 문제로 유명하다.

이런 문제를 고안한 이유는 기계적인 방식으로 모든 수학적인 증명이 가능한지를 묻는 결정문제로부터 출발한다. 

결정문제를 실제 기계로 구현하기 위해 튜링머신이라는 것을 고안했는데, 튜링 머신은

1. 테이프에 기록될 수 있는 기호 및 튜링 머신의 상태와 행동표의 개수는 모두 유한해야 하며 서로 구분되어야 한다.

2. 현재 상태가 1인데 기호 A를 읽었다면 C를 기록하고 정지

3. 현재 상태가 1인데 기호 B를 읽었다면 오른쪽으로 한 칸 이동하고 상태 2로 변경

4. 현재 상태가 2인데 기호 C를 읽었다면 왼쪽으로 한 칸 이동

-> 튜링머신이 유한한 시간안에 모든 무제를 푸는 방법이 있는지 없는지 알아낼 수 있는가?

기계적 방법(튜링머신)으론 결정문제로는 해결할 수 없다. -> 정지문제 때문.

정지문제의 가정

귀류법: 어떤 것이 오류로 귀착된다는 것을 보이는 증명 

가정1. : halt(a,b):

임의의 문자열 a와 임의의 프로그램 b에 대해, a를 입력으로 프로그램 b를 실행했을 경우를 계산하여 그 실행이 끝나면 참, 영원히 실행되면 거짓을 반환하는 알고리즘.

function Problem(string i):
	if halt(i, i') == false:
    	return true
    	else:
    		loop

i' -> 프로그램을 입력받아야 하지만, 프로그램도 결국 문자열의 연속(binary code)임으로 보통 문자열 또한 입력가능

problem(problem)? 종료:무한

problem(problem)의 실행이 끝난다고 가정

halt(problem, problem)가 false를 리턴하는 경우 실행이 끝나지만, 가정1에서 halt가 false를 반환하는 경우는 무한히 실행되는 경우라고 가정했기 때문에 모순

무한히 실행된다고 가정

halt(problem, problem)가 true를 리턴하는 경우 무한루프에 빠진다. 하지만 halt(problem, problem)이 true라는 것은 problem(problem)이 유한시간 내에 끝난다는 이야기로 무한히 실행된다는 가정에 모순

두 가정에 모두 모순이 발생한다.

튜링동치란?

만일 컴퓨터P와 Q가 있을 때, P가 할 수 있는 일을 Q가 모두 할 수 있고, Q가 할 수 있는 일을 모두 P가 흉내낼 수 있다면 두 컴퓨터는 튜링 동치이다.

튜링완전성

어떤 컴퓨터 P가 있어서 그 컴퓨터와 튜링 머신이 튜링 동치라면 P는 튜링 완전하다.

현대 컴퓨터와 튜링머신

현대 컴퓨터의 모체는 튜링머신이기 때문에 튜링머신은 현대의 모든 컴퓨터가 할 수 있는 일을 할 수 있다.

현대의 컴퓨터와 튜링머신은 튜링 동치이다.

즉, 정지문제는 현재까지 유효하다.