Post Correspondence Problem

상위 문서: Turing Machines

개요

해당 문서에서는 Post Correspondence Problem(PCP)에 대해서 설명한다.

Definition of PCP

PCP는 도미노 개념에 기반하여 조직된 문제이다. 도미노란 아래와 같은 “위 문자열(top string)”과 “아래 문자열(bottom string)” 쌍을 의미한다:

[math]\displaystyle{ [\frac{b}{ca}] }[/math]: 위 문자열은  "b", 아래 문자열은 "ca"

PCP는 도미노를 원하는 순서로 반복을 허용하여 나열했을 때, 위 문자열 전체가 아래 문자열 전체와 같은지(매치되는지) 확인하는 문제이다. 예를 들어:

[math]\displaystyle{ [\frac{a}{ab}], [\frac{b}{ca}], [\frac{ca}{a}], [\frac{a}{ab}], [\frac{abc}{c}] }[/math]

와 같은 도미노의 나열은 위, 아래 문자열이 "abcaaabc"로 같기 때문에 "매치(match)가 존재한다"가 문제의 답이다.

PCP Formulation as a Language

PCP의 인스턴스는 도미노들의 리스트이며, 아래와 같이 나타내어 진다:

[math]\displaystyle{ P=\{[\frac{t_1}{b_1}], [\frac{t_2}{b_2}], \cdots, [\frac{t_n}{b_n}]\} }[/math]

이때, 위와 같은 인스턴스를 문자열로 인코딩한 것은 [math]\displaystyle{ \langle P \rangle }[/math]과 같이 나타내어진다. 이러한 정의를 통해 PCP를 언어로 정의하면 아래와 같다:

PCP [math]\displaystyle{ = \{\langle P \rangle|P }[/math]는 매치가 존재하는 PCP 인스턴스이다.[math]\displaystyle{ \} }[/math]

이때, 위 튜링머신은 undecidable하다.

Encoding Turing Machine Using PCP

PCP 도미노로 튜링머신 계산을 인코딩하기 위해서 top을 항상 bottom보다 뒤처지게(lag) 만든다. 이는 튜링머신의 계산이 (tape의 내용, 상태)를 바탕으로 결과를 만들기 때문이다. 즉, Bottom은 “튜링머신이 실제로 생성해야 하는 올바른 다음 configuration(계산 기록)”을 의미하고, Top은 “그 bottom이 정말 올바른 계산을 통해 만들어졌는지 검증하기 위해 따라오는 줄”을 의미한다. 따라서 bottom이 먼저 확장되고, top이 그 확장을 ‘따라잡는’ 것이다. 예를 들어, 아래와 같은 PCP 도미노 나열은 튜링머신 계산 인코딩의 예를 보여준다:

[math]\displaystyle{ [\frac{\#}{\#q_00100\#}]\,\,[\frac{q_0}{2q_7}]\,\,[\frac{1}{1}]\,\,[\frac{0}{0}]\,\,[\frac{0}{0}]\,\,[\frac{\#}{\#}] }[/math]

위 예시에서 문자열들은 튜링머신의 계산 내용(현재 테이프, 상태 등)을 의미한다. 또한 위 예시는 매치를 이루기 위해서 추가적인 도미노를 요구한다. [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math]