정지문제란?

1
2

"프로그램과 초기 입력 값이 주어겼을 때, 이 프로그램에 입력값을 넣고 실행한다면,
이 프로그램이 계산을 끝내고 멈출지 아니면 영원히 계속 계산 할지 판정하라"

튜링

1

기계적인 방식으로 모든 수학적인 증명이 가능한가? - 결정 문제

힐버트

튜링머신

• 테이프에 기록될 수 있는 기호 및 튜링 머신의 상태와 행동표의 새수는 모두 유한해야 하며 서로 구분되어야 한다.
  • 예) 현재 상태가 1인데 기호 A를 읽었다면 C를 기록하고 정지

1

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

정지문제

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

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

1
2
3
4
5

function check(string s)
    if(halt(s,s) == false)
        return true
    else
        loop forever

why ?

• Q) halt 함수의 두 번째 인자는 프로그램 아닌가요?
• A) 프로그램으로 받아햐 하지만, 프로그램도 다르게 말하면 문자열 표현중 하나(바이너리 코드) 라고 볼 수 있기 때문에 문자열 또한 입력이 가능합니다.

튜링동치

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

튜링완전성

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

현대 컴퓨터와 튜링 머신

• 현대 컴퓨터의 모체는 튜링머신이기 때문에 튜링머신은 현대의 모든 컴퓨터가 할 수 있는 일을 할 수 있다.
• 현대의 컴퓨터와 튜링머신은 튜링 동치이다.
• 즉, 정지문제는 현대까지 유효하다.